Solving 3^{20} $\pmod{100}$ Without FLT

[amcavoy]

3^{20}\equiv 1\pmod{100}

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?

Thanks.

 

[Tide]

Note that 3^{20} = 9^{10} = (10 - 1)^{10}. If you do a binomial expansion each term has the form 10^{r} \times (-1)^{n-r}. The last term is (-1)^{10} = 1 and the next to last term is \binom {10}{9} 10^1 \times (-1)^9. Since all the prior terms are multiples of 100 and \binom {10}{9} = 10 we conclude 3^{20} \equiv 1 \mod{100}

 

[neurocomp2003]

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.