Find the sum of all positive integers k less than 1 0 0 0 for which 1 1 k ≡ 1 ( m o d 1 0 0 )
This is a part of the set 11≡ awesome (mod remainders)
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Well, actually it's related to order of 1 1 modulo 1 0 0 . And very easy using the concept of order . In fact, this question is directly the definition of order, for coprime integers.
To know more what it is, read it in my note
Order of 1 1 modulo 1 0 0 is 1 0 , because see the trend in powers of 11 modulo 1 0 0
1 1 0 ≡ 1 ( m o d 1 0 0 ) 1 1 1 ≡ 1 1 ( m o d 1 0 0 ) 1 1 2 ≡ 2 1 ( m o d 1 0 0 ) 1 1 3 ≡ 3 1 ( m o d 1 0 0 ) 1 1 4 ≡ 4 1 ( m o d 1 0 0 ) ⋯ 1 1 9 ≡ 9 1 ( m o d 1 0 0 ) 1 1 1 0 ≡ 1 ( m o d 1 0 0 )
By this, we calculate that order of 1 1 mod 1 0 0 is 1 0 .
Thus we conclude 1 1 1 0 k ≡ 1 ( m o d 1 0 0 ) and then you got it right !
Log in to reply
Me too same done here!! :D...Though I felt this was more bashy! :P
Is this not correct?
As ( 1 1 , 1 0 0 ) = 1 , we have, by euler's totient function, 1 1 4 0 ≡ 1 ( m o d 1 0 0 ) and so for all k , we have 1 1 4 0 k ≡ 1 ( m o d 1 0 0 ) .
Thus, sum = 4 0 + 8 0 + 1 2 0 + . . . + 1 0 0 0 = 1 3 0 0 0
Log in to reply
Unfortunately, no. Yes, 1 1 4 0 ≡ 1 ( m o d 1 0 0 ) is true. But that doesn't mean that the smallest positive integer m such that 1 1 m ≡ 1 ( m o d 1 0 0 ) is 40.
As shown above by Aditya Raut, m = 1 0 , and not m = 4 0 .
Another way to see it is that after knowing that 1 1 4 0 ≡ 1 ( m o d 1 0 0 ) , does it also mean that 1 1 2 0 ≡ ( m o d 1 0 0 ) ? If yes, how about 1 1 1 0 ≡ 1 ( m o d 1 0 0 ) ? If yes again, how about 1 1 5 ≡ 1 ( m o d 1 0 0 ) ?
Log in to reply
@Pi Han Goh – Thanks for clearing my doubt. Now i understood my mistake.
Did quite the same... Nice problem :) @Aditya Raut
Or its simple logic that 1 1 1 0 k always ends in "1" and the others end in 11 , 21,31,..and the pattern continues
Exactly Same Way using Binomial Theorem.
One who is not careful will accidentally include 1000
1
1
1
0
≡
1
(
m
o
d
1
0
0
)
.
Hence the values of
k
are 10, 20, 30 ,..............., 980, 990.
Sum of all these values equals to
4
9
5
0
0
.
We can use Pascal's triangle to check for powers of 11: http://www.mathsisfun.com/pascals-triangle.html
(I am supplying this link because I found it troublesome to print the Pascal's triangle here).
If we actually check the triangle, we find that the last two digits of each successive power (starting from 11) are: 11,21,31.41.51,.... If we go on, we find that in the 10th row, the last two digits are 01. So, we conclude
1 1 1 0 ≡ 1 ( m o d 1 0 0 ) . (A)
Now we use the property that if a ≡ b ( m o d m ) , then a k ≡ b k ( m o d m ) in equation (A), to find that
1 1 k ≡ 1 ( m o d 1 0 0 ) , for k=10,20,30,......,990.
the sum of all these values is
1 0 × 2 n ( n + 1 ) , where n=99. Therefore, we get the answer as 49500.
The rest of 11^k/100 must be the same as 1/100. That said, any power of 11 that ends with X01 is a valid solution for our problem. Analysing the behavior of powers of 11 you will notice that the powers 10,20,30... follow the pattern that we wanted. From that point, we will need from 11^10 to 11^990 (notice the "last than 1000" in the question) giving us a sum of 10(1+2+3+4+...+99) = 10 49.5 100 = 49500.
Thats a good one! De boa
Problem Loading...
Note Loading...
Set Loading...
I ain't certain that my solution is error-free, but that's what I did:-
1 1 k = ( 1 0 + 1 ) k , and 1 0 0 ∣ 1 1 k − 1 means 1 0 0 ∣ ( 1 0 + 1 ) k − 1 . Now, all terms in the expansion of ( 1 0 + 1 ) k will have 1 0 0 in it except the last and the second last terms, which are 1 and 1 0 respectively. So, opening the brackets and removing all the multiples of 1 0 0 and canceling positive and negative ones, we get 1 0 0 ∣ 1 0 k , or k = 1 0 a , where a is a natural number less than 1 0 0 . So sum of all possible values of k is 1 0 + 2 0 + 3 0 + . . . . . . . . . . . . + 9 8 0 + 9 9 0 , which is an AP summing up to 4 9 5 0 0 .