Exercise 845Number theory › CongruencesL1Added 3 Nov 2026

Computing $\varphi(n)$

#Euler totient#computation#prime factorization

Statement

Compute $\varphi(36)$ .

Hint

$\varphi(n)=n\prod_{p\mid n}(1-1/p)$ .

Show solutionHide solution

Factorization. $36=2^2\cdot3^2$ .

Formula. $\varphi(36)=36(1-1/2)(1-1/3)=36\cdot\frac12\cdot\frac23=12$ .

Verification. Integers $\le36$ coprime to $36$ : $1,5,7,11,13,17,19,23,25,29,31,35$ . That is $12$ integers. Correct.

Conclusion. $\varphi(36)=12$ .