Coprimality and Euler's theorem

#coprime#Euler theorem#application

Statement

Compute $3^{100}\pmod{17}$ using Euler's theorem.

Hint

$\varphi(17)=16$ , $\gcd(3,17)=1$ .

Show solutionHide solution

Euler. $3^{16}\equiv1\pmod{17}$ .

Reduce. $100=6\cdot16+4$ , so $3^{100}\equiv3^4=81\equiv13\pmod{17}$ .

Conclusion. $3^{100}\equiv13\pmod{17}$ .