# Fermat's little theorem

Obtain residue class of $7^{9999}$ modulo 100 using the Little Fermat theorem.

But I have no idea how to proceed.

-
I would rather use Euler's theorem: en.wikipedia.org/wiki/Euler's_theorem – Beni Bogosel Mar 26 '12 at 15:27
It can be done using just basic tools. But I believe that if we are going to use something related to Fermat's Theorem, we really want to use Euler's generaliation of Fermat's Theorem. – André Nicolas Mar 26 '12 at 15:29
An hint on how to proceed with basic tools is to compute $7^4$ mod $100$ and then observe that... – Giovanni De Gaetano Mar 26 '12 at 15:34
Have you looked at the first link on the right-hand side? math.stackexchange.com/questions/12846/… – dls Mar 26 '12 at 15:34

First observe that $$7^{4}=2401\equiv1\bmod100.$$ Now write $9999=4\cdot2499+3$ so that $$7^{9999}=(7^4)^{2499}\cdot7^3\equiv7^3=343=43\bmod 100.$$

-

Note that $7^4 = 2401 \equiv 1 \bmod 100$. Now divide $9999$ by $4$ with remainder.

-

You could notice that $7^8 \equiv 1 \mod 100$. This makes the problem a lot easier $$7^{9999}\equiv 7^{9 \cdot 1111} \equiv 7^{7} \equiv 43 \mod 100$$

-

Hint $\rm\ \ 4\:|\:7^{\:\!2}-1,\ 25\:|\:7^{\!\:2}+1\ \Rightarrow\ 100\:|\:7^{\:\!4}-1\:|\:7^{\:4\!\:N}-1\ \Rightarrow\ 100\:|\:7^{\:4\!\:N+3}-7^{\:\!3}$

Or: $\rm\ mod\ 4,25\!:\ \ 7^{\:\!4} \equiv 1\ \Rightarrow\ mod\ 100\!:\ \ 7^{\:\!4}\equiv 1\ \Rightarrow\ 7^{\:\!3 +4\!\:N}\equiv\: 7^{\:\!3} (7^{\:\!4})^N\equiv\: 7^{\:\!3}$

-