Euler function

We've already seen that if p is a prime number and a not a multiple of p then

a^{p − 1} ≡ 1 (mod p)

Euler's theorem is a generalization of this result to arbitrary modules n not only prime modules.

a^φ(n) ≡ 1 (mod n)

We now focus on finding this function φ(n), that in the case of n prime number bust be equal to p −1.

Definition 4.9.1. For all n ≥ 1, denote by φ(n) the number of positive integers smaller than n that are coprime to n. The function φ: ℕ → ℕ defined in this way is called Euler function φ-function, or the totient function. □

As we saw the set of invertible residue classes modulo n by (ℤ/n)* is

(ℤ/n)* = {x ∈ ℤ/n | gcd (x,n) = 1}

so φ(n) = |(ℤ/n)*|.

Thus φ(3) = 2, φ(4) = 2, φ(5) = 4 (as 1,3,4 are coprime to 5), φ(6) = 2, φ(7) = 6.

φ(12) = 4 because the numbers less than 12 coprime to 12 are 1, 5, 7, 11.
φ(20) = 8 because the numbers less than 20 are 1, 3, 7, 9, 11, 13, 14, 17.

Euler discovered that, by using this function φ(n), he could generalize Fermat’s little theorem to include composite numbers n. For example, we observe that 5 is relatively prime to 12 and that 5^φ(12) ≡ 1 (mod 12); that is, 5⁴ ≡ 1 (mod 12), which we can easily verify, since 5⁴ = (5²)² = (25)² ≡ 1² = 1 (mod 12).

The following propositions allow us to calculate the Euler function for every integer n of which its factorisation is known.

Proposition 4.9.2. Let n = p₁^h₁ p₂^h₂ ··· p_s^h_s, the factorisation of n with p_i distinct prime numbers for i = 1, ..., s,. Then

φ(n) = φ(p₁^h₁) φ(p₂^h₂) ··· φ(p_s^h_s) (4.9.1)

Proof. We have to prove that φ is multiplicative i.e.

φ(mn) = φ(m)φ(m) ∀ m,n such that (m,n) = 1

We now from Proposition 4.26 that

f: ℤ_mn → ℤ_m × ℤ_n

defined by

f(x̄_mn) = (x̄_m, ȳ_n),

is a bijection so must be the map

F: U_mn → U_m × U_n

Where U_k denotes the set of invertible congruence classes in ℤ_k, consequently |U_mn| = φ(mn) = |U_m| ⋅ |U_n| = φ(n) ⋅ φ(m).□

Proposition 4.9.3. If p is a prime number, then

φ(p^h) = p^h − p^h−1

Proof. It is sufficient to note that the only numbers that are not coprime with p^h are the multiples of p, which are of the form

p · i, with 1 ≤ i ≤ p^h−1

so there are p^h−1 of them. □

The last two proposition allow us to compute Euler function for every integer n for which the prime decomposition is known. For instance,

φ(72) = φ(2³ · 3²) = φ(2³) φ(3²) = (2³ − 2²) (3² − 3) = 24

φ(108) = φ(2² · 3³) = φ(2²) φ(3³) = (2² − 2)(3³− 3²) = 36.

Even though we are able to calculate φ(n) when the factorisation is known, for large numbers to find all primes that divide n becomes a challenging task.

We prove now Euler's thorem. The proof that we provide now is not very elegant, but once we would have studied groups we shall provide another proof of the Euler's theorem

4.9.4 Euler’s Theorem. If (a,n) = 1, then

a^φ(n) ≡ 1 (mod n).

Proof. We first prove that

a^{φ(p^k)} ≡ 1 (mod p^k) (4.9.2)

We use induction on k. For k = 1

a^φ(p) = a^{p − 1} ≡ 1 (mod p).

this is Fermat's little theorem we already proved. Assuming (4.9.2) true for k we prove it for k + 1. Equation (4.9.2) can be written as

a^φ(p^k) = 1 + hp^k

for some h ∈ ℤ. Not also that

φ(p^{k + 1}) = p^{k + 1} − p^k = p(p^k − p^{k − 1}) = p · φ(p^k)

then

\begin{aligned} a^{ϕ (p^{k + 1})} = a^{p \cdot ϕ (p^{h})} = (1 + h p^{k})^{p} \\ = 1 + (\binom{p}{1}) h p^{k} + (\binom{p}{2}) (h p^{k})^{2} + \dots \\ + (\binom{p}{p - 1}) (h p^{k})^{p - 1} + (h p^{k})^{p} \\ \equiv 1 + (\binom{p}{1}) h p^{k} \equiv 1 (mod p^{k + 1}) \end{aligned}

Because $(\binom{p}{1}) h p^{k}$ is a multiple of p^{k + 1} and the other terms are all ≡ 0 (mod p^k+1).

Now we prove the general case. Let (a,n) = 1 and let

n = p₁^h₁ p₂^h₂ ··· p_s^h_s

For what we proved in the first part for all i we have

a^{φ(p_i^k_i)} ≡ 1 (mod p_i^k_i) i = 1, 2, ..., s (4.9.3)

From the multiplicative property of φ follows

φ(p_i^k_i) | φ(n) ∀i

raising both hands of (4.9.3) by the power φ(n)/φ(p_i^k_i) we have

a^φ(n) ≡ 1 (mod p_i^k_i) i = 1, 2, ..., s

which implies

a^φ(n) ≡ 1 (mod p₁^k₁ p₂^k₂ ··· p_s^k_s) i = 1, 2, ..., s

and thus

a^φ(n) ≡ 1 (mod n).□

The Euler function will be, very important for other aspect we shall in encounter in the next chapters. At present we remark that, as ℤ_n = {[0], [1], ... , [n − 1]}, the multiplicative group U(ℤ_n) of invertible elements of ℤ_n consists of all classes [a], with 0 < a < n such that a is coprime to n (see Corollary 4.5.9. So U(ℤ_n) has order φ(n).

Proposition 4.9.5. In ℤ_n the onbly invertible elements are those classes such as (a,n) = 1. They are φ(n). In particular in ℤ_p with p prime, every non-null class is invertible.

Proof. The invertible classes ā in ℤ_n are those resolving the congruence relation

ax ≡ 1 (mod n)

This conguence admits solution (and unique) if and only if (a,n) = 1. The invertible classes ā are thus such that 1 ≤ a < n and (a,n) = 1; consequently φ(n) is the number of invertible elements. In particular if n = p, then every non-null class ā is such that (a,n) = 1, thus, invertible and their number is p − 1 = φ(p). □

Example 4.9.6. Let us see some examples of U(ℤ_n) for some n:

ℤ₄ = {0̄, 1̄, 2̄, 3̄}, U(ℤ₄) = {1̄, 3̄},
ℤ₆ = {0̄, 1̄, 2̄, 3̄, 4̄, 5̄}, U(ℤ₆) = {1̄, 5̄},
ℤ₈ = {0̄, 1̄, 2̄, 3̄, 4̄, 5̄, 6̄, 7̄}, U(ℤ₈) = {1̄, 3̄, 5̄, 7̄}.

Notice that φ(4) = |U(ℤ₄)| = 2, φ(6) = |U(ℤ₆)| = 2, and φ(8) = |U(ℤ₈)| = 4. ■

Exercise 4.9.7. Find the last two decimal digits of the decimal number 9²⁰¹.

Solution. The last 2 digits of a number will be the remainder when it is divided by 100. This is equivalent to finding the least non-negative residue of 9²⁰¹. Now 9 is coprime to 100, so Euler's theorem (with a = 9 and n = 100, and φ(100) = φ(25⋅4) = φ(2²)φ(5²); φ(2²) = 4 − 2; φ(5²) = 25 − 5 = 40; so φ(100) = 40. We have thus

9⁴⁰ ≡ 1 mod 100

9²⁰¹ = 9^{(40⋅5 + 1)} = (9⁴⁰)⁵ ⋅ 9 ≡ 1⁵ ⋅ 9 mod 100 ≡ 1 ⋅ 9 = 9 mod 100

So the last two digits are 09. You can write 9 as 9 = 0⋅10¹ + 9. ■

«Chinese remainder theorem Index Primality test; Wilson's Theorem »