Find the last two digits of 707^1991
\(\begin{array}{rcll} 707^{1991} \pmod {100} &=& \ ? \end{array}\)
\(\small{ \begin{array}{lrcll} 1. & gcd(707,100) &=& 1 \qquad | \qquad 707 \text{ and } 100 \text{ are relatively prim } \\ 2. & \text{prim factorisation of } 100 &=& 2^2\cdot 5^2 \\ 3. & \phi() \text{ is Euler's totient function, Euler's phi function }\\ & \phi(100) &=& 100\cdot(1-\frac12)\cdot(1-\frac15) \\ & \phi(100) &=& 100\cdot \frac12 \cdot \frac25 \\ & \phi(100) &=& {\color{red}40} \\ 4. & 707^{\phi(100)} &\equiv& 1 \pmod{100} \\ & 707^{{\color{red}40}} &\equiv& 1 \pmod{100} \\ &\text{ Let } \phi(n) \text{ denote the totient function. } \\ &\text{Then } a^{\phi(n)}=1 \pmod {n} \text{ for all } a \text{ relatively prime to } n. \\ \end{array} }\)
\(\begin{array}{rcll} 5. & 1991 &=& {\color{red}40}\cdot 49 + 31 \\ & 707^{1991 } \pmod{100} &=& 707^{ {\color{red}40}\cdot 49 + 31 } \pmod{100} \\ & &=& ( 707^{ {\color{red}40} } )^{49}\cdot 707^{31} \pmod{100} \\ & &\equiv& ( 1 )^{49}\cdot 707^{31} \pmod{100} \\ & &\equiv& 707^{31} \pmod{100} \qquad | \qquad 707^1 \equiv 7 \pmod {100}\\ & &\equiv& 7^{31} \pmod{100} \qquad | \qquad 7^4 \equiv 1 \pmod {100}\\ & &\equiv& 7^{4\cdot 7+3} \pmod{100} \qquad | \qquad 31 = 4\cdot 7 + 3\\ & &\equiv& (7^{4})^7 \cdot 7^3 \pmod{100} \\ & &\equiv& (1)^7 \cdot 7^3 \pmod{100} \\ & &\equiv& 7^3 \pmod{100} \\ & &\equiv& 343 \pmod{100} \\ & &\equiv& 43 \pmod{100} \\ \end{array}\)
The last two digits of \(707^{1991}\) is \(\mathbf{43}\)
