0
$\begingroup$

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

But I have no idea how to proceed.

  • 0
    Have you looked at the first link on the right-hand side? http://math.stackexchange.com/questions/12846/using-fermats-little-theorem2012-03-26

4 Answers 4

7

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. $

2

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

2

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 $

2

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}$