Congruences · Definition

Euler's totient function

elementary number theorycongruences

Before you start you need to know

It appears when studying invertible residues modulo n and is central to Euler's theorem. Its computation relies on the prime factorization of n.

Definition

Euler's totient function \(\varphi\) assigns to each positive integer \(n\) the number of integers between 1 and \(n\) that are coprime to \(n\).

\[\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right)\]

If \(\gcd(m,n)=1\), then \(\varphi(mn)=\varphi(m)\varphi(n)\), and for a prime \(p\) we have \(\varphi(p^k)=p^{k-1}(p-1)\). These rules, together with \(\varphi(1)=1\), let us compute the function from the factorization of n. The multiplicative property is the most useful in practice.

For \(n=36=2^2\cdot 3^2\), apply the prime formula: \(\varphi(36)=36\cdot\frac{1}{2}\cdot\frac{2}{3}=12\). Alternatively, count: from the 36 integers, remove the even ones and the multiples of 3, which leaves 12 integers coprime to 36.

A common mistake is writing \(\varphi(n)=n-1\) for every \(n\), a formula that only holds when \(n\) is prime. For \(n=9\), the correct value is 6, not 8, because the 3 and the 6 must also be excluded since they share factors with 9.

Think about it

Why does φ(n)=n-1 hold only when n is prime?

Because only when n is prime are all integers from 1 to n-1 coprime to n; if n is composite, a prime divisor of n excludes some of them.

Exercises 10

What comes next

Euler's theorem

References

David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 7
Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 2