modular math problem

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 [tex]101^{100} (mod 1000)[/tex] and see what it is.
[tex]100=64+32+4[/tex]
[tex]101^4\equiv (101^2)^2 \equiv (201)^2 \equiv 401 (mod 1000)[/tex]
[tex]101^{32}\equiv (101^4)^8 \equiv (401)^8 \equiv (801)^4 \equiv 601^2 \equiv 201 (mod 1000) [/tex]
[tex]101^{64}\equiv (101^32)^2 \equiv (201)^2\equiv 401 mod (1000) [/tex]

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

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

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

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

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

[tex]\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}.[/tex]

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.