1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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...