I will now prove Euler's totient theorem. I will do that using group theory, since that proof is very simple.
The theorem: for relatively prime or coprime positive integer n and nonzero integer a, a^q = 1 mod n, where q = phi
, Euler's totient function, the count of all positive integers relatively prime to n.
The proof:
First, show that the positive integers relatively prime to n form a group under multiplication modulo n: Z*
.
Then use group theory to prove the theorem.
Z*
is the set of all positive integers a that are coprime to n, along with multiplication.
- Associativity? Multiplication is associative. Yes.
- Identity? Multiplication has an identity: 1, and that number is coprime with every positive integer.
- Inverse? That is more complicated, and it uses the finiteness of this putative group's set.
Z*(1) and Z*(2) have {1}, and it is the identity group. The others have at least one non-identity element. Select one of them and take powers k of them. There are at most q = phi
distinct values of a^k. So for some k1 and k2, a^(k1) = a^(k2) mod n. This gives us a^(k1)*(a^(k2-k1) - 1) = 0 mod n, and thus, a^(k2-k1) = 1 mod n, since a cannot be 0 and since all powers of a are relatively prime to n.
If m is the smallest positive integer that makes possible a^m = 1 mod n, then a generates a version of cyclic group Z(m). It also means that a^(m-1) is the inverse of a. Thus, every element has an inverse.
Since Z*
is a group, every subgroup of it must have a size that evenly divides q. This means that a^q = (a^m)^(q/m) = 1^(q/m) = 1, since q/m is an integer. Since this is true of all a coprime with n, that proves the theorem.