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?

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