Exercise 1582Number theory › CongruencesL1Added 3 Nov 2026

Euler's theorem applied

#Euler theorem#totient#computation

Statement

Compute $5^{1000}\pmod{36}$ .

Hint

$\gcd(5,36)=1$ and $\varphi(36)=12$ .

Show solutionHide solution

Euler. $5^{12}\equiv1\pmod{36}$ .

Reduce exponent. $1000=12\cdot83+4$ , so $5^{1000}=(5^{12})^{83}\cdot5^4\equiv5^4\pmod{36}$ .

Compute. $5^2=25$ , $5^4=625\equiv625-17\cdot36=625-612=13\pmod{36}$ .

Conclusion. $5^{1000}\equiv13\pmod{36}$ .