Exercise 856Number theory › CongruencesL1Added 3 Nov 2026

Computing large powers mod $n$

#modular exponentiation#square-and-multiply#fast power

Statement

Compute $7^{128}\pmod{15}$ .

Hint

Use square-and-multiply, or Euler's theorem.

Show solutionHide solution

Euler. $\varphi(15)=8$ , $\gcd(7,15)=1$ . So $7^8\equiv1\pmod{15}$ .

Compute. $128=8\cdot16$ , so $7^{128}=(7^8)^{16}\equiv1\pmod{15}$ .

Check. $7^2=49\equiv4$ , $7^4\equiv16\equiv1$ , $7^8\equiv1$ , etc. Correct.

Conclusion. $7^{128}\equiv1\pmod{15}$ .