# Fermat: Last two digits of $7^{355}$

I am doing this problem mentioned above and I know the answer because I know Euler's Theorem that $$a^{\varphi{(m)}}\equiv{1}\pmod{m}.$$ I used 100 as my modulus and got that the last two digits of $7^{355}$ are $43$.

My question is this. What prime should I pick to solve this problem using Fermat's theorem $$a^{p-1}\equiv{1}\pmod{p}$$ As a precursor problem, the author (Dudley; Elementary Number Theory) asked to find the last digit of the number above; so using a modulus $5$, $7^4\equiv{1}\pmod{5}$ by Fermat. Since the answer is $7^{355}\equiv{3}\pmod{5}$, the last digit is either $3$ or $8$. Since $7$ is odd, the answer will clearly be odd, so $3$ is it. The book is working linearly, building from the previous chapters and Euler's Theorem isn't mentioned for another two chapters (I remembered Euler from a problem solving class in college).

So again, what prime would be best? How should I procede?

EDIT: I've seen a bunch of problems on the site and none that I looked at did it using Fermat. If there is one, that could be posted and I would be happy.

EDIT 2: it seems that the problem of finding of finding the last two digits using is rather difficult because of the implication that we need something mod 100. Is there a way around this , like adding a step or complexifying, in order to finish the problem with Fermat?

• Aug 20 '15 at 11:46

## Repeated Squaring

If Euler wasn't mentioned I would consider it a problem about repeated squaring: \begin{align} 7^2&\equiv 49\\ 7^4&\equiv 49^2\equiv 1\\ 7^8&\equiv 1^2\equiv 1\\ 7^{(2^n)}&\equiv 1\mbox{ for }n>1 \end{align} Now $355=101100011_2=2^8+2^6+2^5+2^1+2^0$ and so accordingly \large \begin{align} 7^{355}&=7^{2^8+2^6+2^5+2^1+2^0}\\ &\equiv7^{2^1+2^0}\\ &=343\\ &\equiv 43 \end{align}

## Chinese Remainder Approach

Knowing the Chinese Remainder Theorem then simplifies the size of the calculations since modulo 25 we have $7^2\equiv -1$ and $7^{4k}\equiv 1$ and therefore $7^{355}\equiv 7^3\equiv -7$ modulo 25.

At the same time we have $7^2\equiv 1$ modulo 4 so that $7^{355}\equiv 7\equiv 3$ modulo 4. Now $25\equiv 1$ modulo 4 and $-24\equiv 1$ modulo 25 so $$7^{355}\equiv 3\cdot 25-7\cdot (-24)$$ modulo 100 due to the Chinese Remainder Theorem. Finishing this calculation we get $$3\cdot 25-7\cdot(-24)=10\cdot 25-7=243$$ to see that $7^{355}\equiv 243\equiv 43$ modulo 100.

• Perhaps one might jump to the conclusion that the powers of all integers modulo 100 do not repeat in a manner that can be calculated by hand. However, it should be mentioned that 7 is a special case, together with a few other integers. Good answer! Jan 11 '14 at 0:45
• @String I think $355=101100011_2=2^9+2^7+2^6+2^1+2^0$ should be replaced by $355=101100011_2=2^8+2^6+2^5+2^1+2^0$. May 17 '14 at 3:44
• @learner: You are quite right about that! Jun 18 '14 at 13:29

Use the primes 2 and 5 and combine the results using the chinese remainder theorem to get the last digit.

• I need the last two digits... I got the last digit as 3 using fermat with $p=5$. Jan 10 '14 at 23:29
• Yeah, that was the question...I'm using Dudley's Elementary Number Theory and the chapter is dedicated to Fermat and Wilson ($(p-1)!\equiv{-1}\pmod{p}$)...I don't think Wilson applies here... Jan 10 '14 at 23:32
• why use 11 in particular? How to deduce that? Jan 10 '14 at 23:55
• Just noticed that it does not work, sorry. Jan 10 '14 at 23:55
• There must be some additional trick because the remainder with respect to any prime has nothing to do with the remainder with respect to 100. Jan 11 '14 at 0:17

Hint $\rm\ mod\ 100\!:\ \color{#c00}{7^4} \overset{\,}\equiv (50-1)^2 \equiv \color{#c00}1\$ so $\rm\ 7^N = 7^{\,4J+K}\!\equiv (\color{#c00}{7^4})^J 7^K\equiv \color{#c00}1^J7^K\!\equiv 7^K$

Said equivalently $\rm\ 7^{\large\color{#0a0}4}\equiv 1\, \Rightarrow\, 7^{\large N}\equiv 7^{\large K}\ (mod\ 100)\$ if $\rm\ K\,\equiv\, N\ \ (mod\ \color{#0a0}4).\,$ To make arithmetic simple, choose the smallest such $\rm\,K > 0,\$ namely $\rm\ \: K \,= (N\ \,mod\,\ \color{#0a0}4).\,$ See also this answer.

• right, but I'm looking for a solution using Fermat, which requires the modulus to be prime. Jan 10 '14 at 23:42
• @Chris It is a bit unnatural to try to deduce that $\,7^4 \equiv 1\pmod{100}$ using only little Fermat. Why force that limitation on yourself? Unless that was explicitly specified in the book, I suspect you are misjudging what was intended. Doing it as above requires only grade school arithmetic $7^4 = (-1+50)^2 = 1 -2(50)+50^2\equiv 1\pmod{100}$ Jan 10 '14 at 23:54
• Mainly because I think there is a way, and I like the challenge...in so many words! As I mentioned in the problem, I already know how to solve the problem, I was just trying to use Fermat since it seems possible... Jan 10 '14 at 23:56
• Fermat's "Little Theorem" is a special case of $a^{\psi (b)}\equiv 1 \pmod b$ when $a b\neq 0$ and $\gcd (a,b)=1.$ May 13 '16 at 16:40