# The Order of a Unit

The discrete log problem may be hard, but we do know some facts about the powers of a unit \(a \in\mathbb{Z}_n^*\). Firstly, \(a^k = 1\) for some \(k\): since there are finitely many units, we must have \(a^x = a^y\) for some \(x < y\) eventually, and since \(a^{-1}\) exists we find \(a^{y-x} = 1\).

Let \(a \in\mathbb{Z}_n^*\). The smallest positive integer \(x\) for which
\(a^x = 1 \pmod{n}\) is called the *order* of \(a\).
The sequence \(a, a^2, ...\) repeats itself as soon as it reaches \(a^x = 1\).
(since \(a^{x+k} = a^k\)), and we have \(a^k = 1\) precisely when \(k\) is a multiple
of \(x\).

**Example**: The powers of \(3 \pmod{7}\) are
\(3, 2, 6, 4, 5, 1\) so the order of \(3 \pmod {7}\) is \(6\).

The following theorems narrow down the possible values for the order of a unit.

## Fermat’s Little Theorem

**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.

## Euler’s 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.)

## Multiplication and Order

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\).

## The RSA Problem

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.

*blynn@cs.stanford.edu*💡