Modular Math Problem: What Is the Largest n?

[Gokul43201]

What is the largest n for which 10^n divides [(101^100) - 1] ? Clearly n=2, is one solution. What then ?

 

[NateTG]

Well, you could caculate 101^{100} (mod 1000) and see what it is.
100=64+32+4
101^4\equiv (101^2)^2 \equiv (201)^2 \equiv 401 (mod 1000)
101^{32}\equiv (101^4)^8 \equiv (401)^8 \equiv (801)^4 \equiv 601^2 \equiv 201 (mod 1000)
101^{64}\equiv (101^32)^2 \equiv (201)^2\equiv 401 mod (1000)

so
101^{100}\equiv101^{64+32+4)\eqiuv 101^{64} \times 101^{32} \times 10^4 \equiv
401\times401\times201\equiv 801 \times 201 \equiv 1
so 101^{100}-1 is divisible by 10^3

Alternatively consider 101 mod 2^n and mod 5^n:
In base 2, 101 is written:
110011
and in base 5
41
Now, we know that for 101^{100}-1 to be divisible by 10^n that 101^{100} \equiv 1 (mod 2^n) and 101^{100} \equiv 1 (mod 5^n)
Now, \phi(5^3)=5^2\times(5-1)=100 so x^{100} \equiv 1(mod 125)
and \phi(2^3)=2^2\times(201)=4 so x^{100} \equiv (x^{25})^4) \equiv 1 (mod 8)
but
\phi(5^4)=5^3\times(5-1)=600 does not divide 100 so you need to check it.
similarly
\phi(2^4)=2^3\times(2-1)=8 does not divide 100, and it's probably a faster one to check:
100 \equiv 4 (mod 8)
and 101 \equiv 5 (mod 16)

so 101^{100} \equiv 5^{4}\equiv 625 \equiv 9 \nequiv 1 (mod 16)
so 16 does not divide 100^{101}-1 therefore 10000 also does not.

so 101^{100} \equiv 5^{4}\equiv 625 \equiv 1 (mod 16)
(Corrected.I probably shouldn't be doing this in my head.)

 

[Gokul43201]

Wait a second : 101 == 5 (mod 16)
=> 101^2 ==25==9(mod 16) or 101^4 ==81==1(mod 16).
So 16 divides 101^100 - 1

 

[robert Ihnot]

This is a question of the binominal formula for (100+1)^100 the leading term is going to be 100^100 and the last three terms are (100^2)x100x99/2 + 100x100 +1. So subtracting off 1 we have 100x100 as the smallest term in powers of 100, and the answer is 10,000 will divide the expression.

 

[Gokul43201]

This proves that 10,000 divides the number. How can I be sure there isn't another larger divisor ? It seems unlikely but not impossible...yet.

 

[Muzza]

How can I be sure there isn't another larger divisor ?

Evaluate 101^100 - 1 modulo 10^5. By the binomial theorem, we have that

(100 + 1)^{100} = \sum_{k = 0}^{100} \binom{100}{k} 100^k = \sum_{k = 0}^{100} \binom{100}{k} 10^{2k} .

Now, when the exponent of 10 is bigger than 5 (i.e k > 2), the terms in the sum are congruent to 0 mod 10^5. So

\sum_{k = 0}^{100} \binom{100}{k} 10^{2k} \equiv \binom{100}{0} 10^{0} + \binom{100}{1} 10^{2} + \binom{100}{2} 10^{4} \pmod{10^5}.

That's pretty easy to evaluate (you can do it in your head), but I'll spare you the calculations. It's 49510001. So 101^100 - 1 = 49510001 - 1 != 0 (mod 10^5).

 

[1+1=1]

gokul- this almost looks like the exact same material that i am studying... hmmm, weird no?

 

[Gokul43201]

Actually, I found this problem in a practice test paper for a B-School Entrance Exam.