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?
 A: Use the primes 2 and 5 and combine the results using the chinese remainder theorem to get the last digit.
A: 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.
A: 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.
