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?
Best Answer
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.