Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular math problem

  1. May 11, 2004 #1

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

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

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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.)
     
    Last edited: May 11, 2004
  4. May 11, 2004 #3

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
  5. Jun 30, 2004 #4
    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.
     
    Last edited: Jun 30, 2004
  6. Jun 30, 2004 #5

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  7. Jun 30, 2004 #6
    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).
     
    Last edited: Jun 30, 2004
  8. Jun 30, 2004 #7
    gokul- this almost looks like the exact same material that i am studying... hmmm, weird no?
     
  9. Jun 30, 2004 #8

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Actually, I found this problem in a practice test paper for a B-School Entrance Exam.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Modular math problem
  1. Modular math problem (Replies: 7)

  2. New math problem book (Replies: 2)

Loading...