Question

Find the remainder when \(67^{101}\) is divided by 65.

Answer 1

Hint \[67\equiv 2\pmod{65}\]

Answer 2

I thought 65 was a prime number, applied Fermat's little theorem and failed miserably...

Answer 3

Thats typical
but you may apply euler's theorem for composite moduli

Answer 4

\(\phi(65)=\phi(5\times 13)=(5-1)(13-1)=48,\)therefore
\[a^{48}\equiv 1\pmod{65}\]
for all \(a\) relatively prime to \(65\)