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.