The Order of a Unit

Theorem: Let \(p\) be a prime. Then \(a^p = a \pmod{p}\) for any \(a \in \mathbb{Z}_p\).

This theorem is often equivalently stated as \(a^{p-1} = 1\) for nonzero \(a\).

Proof: We first show an identity sometimes referred to as the freshman’s dream: for a prime \(p\), we have

This is immediate from the binomial expansion, because \(p\) divides every term except for two terms, that is

By induction we have

Thus if we write \(a = 1 + ... + 1\) (where there are \(a\) 1s), we have

Fermat’s Theorem gives an alternative way to compute inverses. For \(a \in \mathbb{Z}_p^*\), \(a^{-1}\) can be computed as \(a^{p-2}\), since we have \(a \cdot a^{p-2} = 1\) by the theorem.

Theorem: If \(a \in \mathbb{Z}_n^*\) then \(a^{\phi(n)} = 1 \pmod{n}\).

This reduces to Fermat’s Little Theorem when \(n\) is prime.

Proof: Let \(m = \phi(n)\), and label the units \(u_1,...,u_m\). Consider the sequence \(a u_1,...,a u_m\) (we multiply each unit by \(a\)). If \(a u_i = a u_j\), then multiplying by \(a^{-1}\) (which exists since \(a\) is a unit) shows \(u_i = u_j\), hence the members of the sequence are distinct. Furthermore products of units must also be units, hence \(a u_1, ..., a u_m\) must be \(u_1,...,u_m\) in some order.

Multiplying all the units together gives

Rearranging yields

Similarly Euler’s Theorem also gives an alternative way to compute inverses. For \(a \in \mathbb{Z}_n^*\), \(a^{-1}\) can be computed as \(a^{\phi(n)-1}\). This is efficient as we may use repeated squaring, but Euclid’s algorithm is still faster (why?) and does not require one to compute \(\phi(n)\).

These theorems do not tell us the order of a given unit \(a\in\mathbb{Z}_n^*\) but they do narrow it down: let \(x\) be the order of \(a\). If we know \(a^y = 1\) by Euclid’s algorithm we can find \(m, n\) such that

where \(d = \gcd(x, y)\). Then

thus since \(d \le x\) we must have \(d = x\) (since \(x\) is the smallest positive integer for which \(a^x = 1\)), and hence \(x\) must be a divisor of \(y\). Thus by Euler’s Theorem, the order of \(a\) divides \(\phi(n)\).

These theorems are special cases of Lagrange’s Theorem from group theory. (Fermat and Euler died long before group theory was discovered.)

Let \(x\) be the order of \(a\in\mathbb{Z}_n^*\), and \(y\) be the order of \(b\in\mathbb{Z}_n^*\). What is the order of \(a b\)?

Suppose \((a b)^k= 1\). Raising both sides to \(x\) shows

Since \(b\) has order \(y\) we see that \(y | k x\).

Suppose \(x, y\) are coprime. Then we must have \(y | k\). Similarly \(x | k\), hence \(k\) must be a multiple of \(x y\). On the other hand, we have \((ab)^{x y} = 1\). Hence the order of \(a b\) is precisely \(x y\): for elements with coprime orders, the order of their product is equal to the product of their orders.

More generally, let \(d = \gcd(x,y)\). Then \(x | k y\) and \(y | k x\) implies that \(k\) must be a multiple of \((x/d)(y/d)\). If \(z\) is the least common multiple of \(x\) and \(y\), which we can compute by \(z = x y / d\), then \((a b)^z = 1\). All we can say at the moment is that the order of \(a b\) is a multiple of \(x y / d^2\) and divides \(x y / d\).

Suppose we are given positive integers \(e, N\), and \(a^e \pmod{N}\) for some unit \(a\). How can we recover \(a\)?

One strategy is to find an integer \(d\) such that \(a^{d e} = a \pmod{N}\). By Euler’s Theorem, \(d\) will satisfy this equation if \(d e = k \phi(N) + 1\) for some \(k\). In other words, we compute

and compute \((a^e)^d\) to recover \(a\).

However it is not known how to compute \(\phi(N)\) from \(N\) without factoring \(N\), and it is not known how to factor large numbers efficiently.