The totient φ(n), pronounced “phi of n,” counts integers from 1 through n that are coprime to n. For n>1, this is also the number of invertible residues among 0,…,n-1. For example, the residues coprime to 10 are 1, 3, 7 and 9, so φ(10)=4.

Count the usable residues

A prime p has φ(p)=p-1: every nonzero residue is coprime to p.

For distinct primes p and q, a residue fails the test exactly when it is divisible by p or q. Among the pq residues, there are q multiples of p and p multiples of q. Their only overlap is 0, counted twice. Inclusion–exclusion gives:

With p=5 and q=11, this is 55-11-5+1=40. The other 15 residues share a factor with 55. The formula needs distinct primes: φ(25)=20, not (5-1)²=16.

The theorem and its mechanism

Euler's theorem says:

Multiplying every invertible residue by a produces the same set in a different order. If two products coincided, multiplication by a's inverse would show the originals were the same. Compare the product of the original set with the product of the permuted set: the latter gains φ(n) factors of a. Cancelling the invertible original product leaves a raised to φ(n) congruent to 1 modulo n. This is why the coprimality condition is essential.

For a prime modulus, the theorem becomes Fermat's little theorem: aᵖ⁻¹≡1 (mod p) when p does not divide a.

The bridge to RSA

Since gcd(7,55)=1, we know 7⁴⁰≡1 (mod 55). Our exponents satisfy 3×27=81=1+2×40, so:

That proves the round trip for 7 and other coprime messages. It does not prove the same statement for every message: 5 is not coprime to 55. RSA from first principles handles those messages by reasoning separately modulo each prime.