Maths and Computing:Euler's Totient Function

Euler's Totient Function

Euler's Totient Function φ(n)

Euler's totient function is equal to the number of positive integers less than or equal to a given number n that are coprime to it.

If two natural numbers are coprime then they share no prime factors

If a is coprime to b then the greatest common factor of a and b is 1 (GCF(a,b) = 1)

Example: p = 7

1, 2, 3, 4, 5 and 6 are coprime to 7

There are 6 positive integers that are less than or equal to 7 and coprime to 7

φ(7) = 6

Example: p = 12

1, 5, 7 and 11 are coprime to 12

There are 4 positive integers that are less than or equal to 12 and coprime to 12.

φ(12) = 4

Example: p = 1

1 is coprime to 1 (GCF(1,1) = 1)

There is one positive integer that is less than or equal to 1 and coprime to 1

φ(1) = 1

Properties of φ(n)

Multiplication rule

If a and b are coprime: φ(ab) = φ(a) × φ(b)

Example: a = 3, b = 4

1 and 2 are coprime to 3. φ(3) = 2

1 and 3 are coprime to 4. φ(4) = 2

φ(12) = φ(3) × φ(4)

φ(12) = 2 × 2 = 4

Sum of values of φ(d) for each divisor of n

	φ(d) = n
Σ
d\|n

Example: n = 12

1, 2, 3, 4, 6 and 12 all divisors of 12

φ(1) = 1, φ(2) = 1, φ(3) = 2 φ(4) = 2, φ(6) = 2, φ(12) = 4

φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12

Eulers Theorem

If x and n are coprime then x^φ(n) ≡ 1 (mod n)

Example: φ(5) = 4

1⁴ = 1 ≡ 1 (mod 5)
2⁴ = 16 ≡ 1 (mod 5)
3⁴ = 81 ≡ 1 (mod 5)
4⁴ = 256 ≡ 1 (mod 5)

Euler's totient function φ(n), calculates the number of positive integers less than n that are coprime to n.

Alternatively φ(n) = n - m where m is the numbers of values less than or equal to n that share a prime factor with n

Let p and q be distinct prime values

Calculating the value of φ(p)

The only value less than or equal to p that shares a prime factor with p is p.

φ(p) = p - 1.

Calculating the value of φ(p^r)

Values less than or equal to p^r that share a prime factor with p^r are the multiples of p

There are p^r-1 multiples of p that are less then or equal to p^r
φ(p^r) = p^r - p^r-1.

φ(p^r) = p^r-1(p - 1).

Calculating the value of φ(pq)

There are q multiples of p that are less than or equal to pq

There are p multiples of q that are less than or equal to pq

There is just one mulitple of pq that is less than or equal to pq

φ(pq) = pq - (p + q - 1).

φ(pq) = (p - 1)(q - 1).

or φ(pq) = φ(p)φ(q).

Calculating the value of φ(p^uq^v)

There are p^u-1q^v multiples of p that are less than or equal to p^uq^v

There are p^uq^v-1 multiples of q that are less than or equal to p^uq^v

There are p^u-1q^v-1 multiples of pq that are less than or equal to p^uq^v

φ(p^uq^v) = p^uq^v - (p^u-1q^v + p^uq^v-1 - p^u-1q^v-1).

φ(p^uq^v) = p^u-1q^v-1(p - 1)(q - 1).

φ(p^uq^v) = (p - 1)p^u-1(q - 1)q^v-1.

or φ(p^uq^v) = φ(p^u)φ(q^v).

General Formula

To calculate φ(n), express n as the product of prime factors

n = p₁^k₁p₂^k₂ ... p_r^k_r where p₁, p₂, p₃ ... p_r are distinct primes

φ(n) = (p₁-1)p₁^k₁-1 (p₁-1)p₂^k₂-1... (p_n-1)p_n^k_r-1

or φ(n) = φ(p₁^k₁)φ(p₂^k₂) ... φ(p_r^k_r)

Enter a value for n

Euler's Theorem

x and n are coprime

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

Fermat's Little Theorem

A subset of Euler's theorem when n is a prime number p

x^p-1 ≡ 1 (mod p)

Maths and Computing:

Euler's Totient Function

Euler's Totient Function φ(n)

Euler's totient function is equal to the number of positive integers less than or equal to a given number n that are coprime to it.

If two natural numbers are coprime then they share no prime factors

If a is coprime to b then the greatest common factor of a and b is 1 (GCF(a,b) = 1)

Example: p = 7

1, 2, 3, 4, 5 and 6 are coprime to 7

There are 6 positive integers that are less than or equal to 7 and coprime to 7

φ(7) = 6

Example: p = 12

1, 5, 7 and 11 are coprime to 12

There are 4 positive integers that are less than or equal to 12 and coprime to 12.

φ(12) = 4

Example: p = 1

1 is coprime to 1 (GCF(1,1) = 1)

There is one positive integer that is less than or equal to 1 and coprime to 1

φ(1) = 1

Properties of φ(n)

Multiplication rule

If a and b are coprime: φ(ab) = φ(a) × φ(b)

Example: a = 3, b = 4

1 and 2 are coprime to 3. φ(3) = 2

1 and 3 are coprime to 4. φ(4) = 2

φ(12) = φ(3) × φ(4)

φ(12) = 2 × 2 = 4

Sum of values of φ(d) for each divisor of n

φ(d) = n

Σ

d|n

Example: n = 12

1, 2, 3, 4, 6 and 12 all divisors of 12

φ(1) = 1, φ(2) = 1, φ(3) = 2 φ(4) = 2, φ(6) = 2, φ(12) = 4

φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12

Eulers Theorem

If x and n are coprime then xφ(n) ≡ 1 (mod n)

Example: φ(5) = 4

Euler's totient function φ(n), calculates the number of positive integers less than n that are coprime to n.

Alternatively φ(n) = n - m where m is the numbers of values less than or equal to n that share a prime factor with n

Let p and q be distinct prime values

Calculating the value of φ(p)

The only value less than or equal to p that shares a prime factor with p is p.

φ(p) = p - 1.

Calculating the value of φ(pr)

Values less than or equal to pr that share a prime factor with pr are the multiples of p

There are pr-1 multiples of p that are less then or equal to pr φ(pr) = pr - pr-1. φ(pr) = pr-1(p - 1).

φ(pr) = pr - pr-1.

φ(pr) = pr-1(p - 1).

Calculating the value of φ(pq)

There are q multiples of p that are less than or equal to pq

There are p multiples of q that are less than or equal to pq

There is just one mulitple of pq that is less than or equal to pq

φ(pq) = pq - (p + q - 1).

φ(pq) = (p - 1)(q - 1).

or φ(pq) = φ(p)φ(q).

Calculating the value of φ(puqv)

There are pu-1qv multiples of p that are less than or equal to puqv

There are puqv-1 multiples of q that are less than or equal to puqv

There are pu-1qv-1 multiples of pq that are less than or equal to puqv

φ(puqv) = puqv - (pu-1qv + puqv-1 - pu-1qv-1).

φ(puqv) = pu-1qv-1(p - 1)(q - 1).

φ(puqv) = (p - 1)pu-1(q - 1)qv-1.

or φ(puqv) = φ(pu)φ(qv).

General Formula

To calculate φ(n), express n as the product of prime factors

n = p1k1p2k2 ... prkr where p1, p2, p3 ... pr are distinct primes

φ(n) = (p1-1)p1k1-1 (p1-1)p2k2-1... (pn-1)pnkr-1

or φ(n) = φ(p1k1)φ(p2k2) ... φ(prkr)

Enter a value for n

Euler's Theorem

x and n are coprime

xφ(n) ≡ 1 (mod n)

Fermat's Little Theorem

A subset of Euler's theorem when n is a prime number p

xp-1 ≡ 1 (mod p)

Contents Copyright 2026 Andy Abraham

Please email comments to info@mathsandcomputing.co.uk

If x and n are coprime then x^φ(n) ≡ 1 (mod n)

Calculating the value of φ(p^r)

Values less than or equal to p^r that share a prime factor with p^r are the multiples of p

There are p^r-1 multiples of p that are less then or equal to p^r
φ(p^r) = p^r - p^r-1.

φ(p^r) = p^r-1(p - 1).

φ(p^r) = p^r - p^r-1.

φ(p^r) = p^r-1(p - 1).

Calculating the value of φ(p^uq^v)

There are p^u-1q^v multiples of p that are less than or equal to p^uq^v

There are p^uq^v-1 multiples of q that are less than or equal to p^uq^v

There are p^u-1q^v-1 multiples of pq that are less than or equal to p^uq^v

φ(p^uq^v) = p^uq^v - (p^u-1q^v + p^uq^v-1 - p^u-1q^v-1).

φ(p^uq^v) = p^u-1q^v-1(p - 1)(q - 1).

φ(p^uq^v) = (p - 1)p^u-1(q - 1)q^v-1.

or φ(p^uq^v) = φ(p^u)φ(q^v).

n = p₁^k₁p₂^k₂ ... p_r^k_r where p₁, p₂, p₃ ... p_r are distinct primes

φ(n) = (p₁-1)p₁^k₁-1 (p₁-1)p₂^k₂-1... (p_n-1)p_n^k_r-1

or φ(n) = φ(p₁^k₁)φ(p₂^k₂) ... φ(p_r^k_r)

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

x^p-1 ≡ 1 (mod p)