Who likes 11 so much?

Find the sum of all positive integers k k less than 1000 1000 for which 1 1 k 1 ( m o d 100 ) 11^k \equiv 1 \pmod{100}


This is a part of the set 11≡ awesome (mod remainders)


The answer is 49500.

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.

4 solutions

Satvik Golechha
Sep 15, 2014

I ain't certain that my solution is error-free, but that's what I did:-

1 1 k = ( 10 + 1 ) k 11^k=(10+1)^k , and 100 1 1 k 1 100|11^k-1 means 100 ( 10 + 1 ) k 1 100|(10+1)^k-1 . Now, all terms in the expansion of ( 10 + 1 ) k (10+1)^k will have 100 100 in it except the last and the second last terms, which are 1 1 and 10 10 respectively. So, opening the brackets and removing all the multiples of 100 100 and canceling positive and negative ones, we get 100 10 k 100|10k , or k = 10 a k=10a , where a a is a natural number less than 100 100 . So sum of all possible values of k k is 10 + 20 + 30 + . . . . . . . . . . . . + 980 + 990 10+20+30+............+980+990 , which is an AP summing up to 49500 \boxed{49500} .

Well, actually it's related to order of 11 11 modulo 100 100 . 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 11 11 modulo 100 100 is 10 10 , because see the trend in powers of 11 modulo 100 100

1 1 0 1 ( m o d 100 ) 1 1 1 11 ( m o d 100 ) 1 1 2 21 ( m o d 100 ) 1 1 3 31 ( m o d 100 ) 1 1 4 41 ( m o d 100 ) 1 1 9 91 ( m o d 100 ) 1 1 10 1 ( m o d 100 ) 11^0 \equiv 1 \pmod{100}\\ 11^1 \equiv 11 \pmod{100} \\11^2 \equiv 21 \pmod{100} \\ 11^3 \equiv 31\pmod{100} \\ 11^4 \equiv 41 \pmod{100} \\ \cdots \\ 11^9 \equiv 91 \pmod{100} \\ 11^{10} \equiv 1 \pmod{100}

By this, we calculate that order of 11 11 mod 100 100 is 10 10 .

Thus we conclude 1 1 10 k 1 ( m o d 100 ) 11^{10k} \equiv 1 \pmod{100} and then you got it right !

Aditya Raut - 6 years, 8 months ago

Log in to reply

Me too same done here!! :D...Though I felt this was more bashy! :P

Krishna Ar - 6 years, 8 months ago

Is this not correct?

As ( 11 , 100 ) = 1 (11, 100) = 1 , we have, by euler's totient function, 1 1 40 1 ( m o d 100 ) 11^{ 40 } \equiv 1 \pmod{100} and so for all k k , we have 1 1 40 k 1 ( m o d 100 ) 11^{ 40k } \equiv1 \pmod{100} .

Thus, sum = 40 + 80 + 120 + . . . + 1000 = 13000 = 40 + 80 + 120 + ... + 1000 = 13000

Priyanshu Mishra - 5 years, 7 months ago

Log in to reply

Unfortunately, no. Yes, 1 1 40 1 ( m o d 100 ) 11^{40} \equiv 1 \pmod{100} is true. But that doesn't mean that the smallest positive integer m m such that 1 1 m 1 ( m o d 100 ) 11^m \equiv 1 \pmod{100} is 40.

As shown above by Aditya Raut, m = 10 m = 10 , and not m = 40 m=40 .

Another way to see it is that after knowing that 1 1 40 1 ( m o d 100 ) 11^{40} \equiv 1 \pmod{100} , does it also mean that 1 1 20 ( m o d 100 ) 11^{20} \equiv \pmod{100} ? If yes, how about 1 1 10 1 ( m o d 100 ) 11^{10} \equiv 1 \pmod{100} ? If yes again, how about 1 1 5 1 ( m o d 100 ) 11^{5} \equiv 1 \pmod{100} ?

Pi Han Goh - 5 years, 6 months ago

Log in to reply

@Pi Han Goh Thanks for clearing my doubt. Now i understood my mistake.

Priyanshu Mishra - 5 years, 6 months ago

Did quite the same... Nice problem :) @Aditya Raut

Krishna Ar - 6 years, 9 months ago

Or its simple logic that 1 1 10 k 11^{10k} always ends in "1" and the others end in 11 , 21,31,..and the pattern continues

Krishna Ar - 6 years, 9 months ago

Log in to reply

actually its amazing mammaiya >>>>> :-)

ashutosh mahapatra - 6 years, 8 months ago

Exactly Same Way using Binomial Theorem.

Kushagra Sahni - 5 years, 2 months ago

One who is not careful will accidentally include 1000

Mohammad Farhat - 2 years, 8 months ago
Saurav Pal
Mar 1, 2015

11 10 1 ( m o d 100 ) { 11 }^{ 10 }\equiv 1\quad (mod\quad 100) . Hence the values of k are 10, 20, 30 ,..............., 980, 990.
Sum of all these values equals to 49500 \boxed {49500} .

Raghav Chaudhary
Sep 29, 2014

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

11 10 1 ( m o d 100 ) { 11 }^{ 10 }\equiv 1(mod\quad 100) . (A)

Now we use the property that if a b ( m o d m ) a\equiv b(mod\quad m) , then a k b k ( m o d m ) { a }^{ k }\equiv { b }^{ k }(mod\quad m) in equation (A), to find that

11 k 1 ( m o d 100 ) { 11 }^{ k }\equiv 1(mod\quad 100) , for k=10,20,30,......,990.

the sum of all these values is

10 × n ( n + 1 ) 2 10\times \frac { n(n+1) }{ 2 } , where n=99. Therefore, we get the answer as 49500.

André Meneghetti
Sep 28, 2014

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

Ivan Martinez - 6 years, 8 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...