Euler's Totient Function φ(n)
Lesson · Intermediate
Number Theory
φ(n) is the number of integers from 1 to n that are relatively prime to n.
If
Let
An integer 1 ≤ m ≤ n is relatively prime to n exactly when it is divisible by none of
Let Aᵢ be the set of integers from 1 to n divisible by pᵢ.
Since
Similarly,
and in general,
By Inclusion–Exclusion, the number divisible by none of the pᵢ's is
Factor out n:
The expression in parentheses is precisely the expansion of
Therefore,
By definition
If gcd(m,n) = 1, then
Since gcd(m,n) = 1, all pᵢ's and qᵢ's are distinct
Then,
Suppose
From the totient formula,
There are two cases.
If n has an odd prime factor pᵢ, then pᵢ − 1 is even. Therefore the expression for φ(n) contains an even factor, so
is even.
If n has no odd prime factor, then
Since n > 2, we have a ≥ 2. Thus
which is even.
Therefore, in all cases,
Find
Since
we have
Thus
Find all positive integers n such that
How many fractions
are already in lowest terms?
We need
Therefore the answer is
Since
The number of integers
such that
where d | n, is
Since
we must have
So write
Also, since
write
where
Then
Therefore,
if and only if
Since
we have
so
Thus m can be any integer from 1 to q that is relatively prime to q.
By definition, there are
such integers.
Since
the number of possible k is
Consider the integers
We group them according to their greatest common divisor with n.
For each divisor d | n, consider the integers k satisfying
The number of such k is
As d runs through the divisors of n, so does
Therefore,