MathGoldMedalist
Sign InRegister

Toolkit 51

Euler's Totient Function φ(n)

φ(n)=∣{1≤i≤n∣gcd⁡(i,n)=1}∣\varphi(n)=|\{1\le i\le n\mid\gcd(i,n)=1\}|

φ(n)\varphi(n) is the number of integers from 11 to nn that are relatively prime to nn.

If n=p1α1p2α2⋯pkαkn=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k},

φ(n)=n(1−1p1)(1−1p2)⋯(1−1pk)\varphi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right)
Back to Toolkit