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

Homework Help: Number Theory

  1. Oct 2, 2005 #1
    [tex]3^{20}\equiv 1\pmod{100}[/tex]

    How can I show this? I can't see any use of Fermat's Little Theorem here (unless I'm just missing it).

    FLT is the only way I know how to do these. Does anyone have a suggestion on how to do it for something like this?

  2. jcsd
  3. Oct 2, 2005 #2


    User Avatar
    Science Advisor
    Homework Helper

    Note that [itex]3^{20} = 9^{10} = (10 - 1)^{10}[/itex]. If you do a binomial expansion each term has the form [itex]10^{r} \times (-1)^{n-r}[/itex]. The last term is [itex](-1)^{10} = 1[/itex] and the next to last term is [itex]\binom {10}{9} 10^1 \times (-1)^9[/itex]. Since all the prior terms are multiples of 100 and [itex]\binom {10}{9} = 10[/itex] we conclude [itex] 3^{20} \equiv 1 \mod{100}[/itex]
  4. Oct 2, 2005 #3
    i think the theory is called powers modulo something....and the method is successive squaring. FLT has nothing to do with your problem because you are not dealing with the concept of primes or pseudo primes(carmicheals i think).

    successive squarign tech(you can always check mathworld.com to see if i'm right)
    so you have a^c=x mod m
    x is your unknown.
    step one: expand c to its binary representation.
    step two: start iwth a^1 mod m.
    step three: square a^1 mod m ot get a^2 mod m
    step i: square the preivous mod m to get the next square
    step last: multiply all the squares mod m for which there is a 1 in the binary rep.

    but you can always do the above suggested technique.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook