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?

Solution 1:

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.

Solution 2:

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

Solution 3:

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.