Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

But I have no idea how to proceed.

share|improve this question
    
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
1  
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
add comment

4 Answers

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.