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

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.

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

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.