# 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

$(x + y)^p = x^p + y^p \pmod {p}.$

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

$(x + y)^p = x^p + y^p + p(...) = x^p + y^p \pmod{p}$

By induction we have

$(x_1 +...+ x_n)^p = x_1^p + ... + x_n^p$

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

$a^p = (1 + ... + 1)^p = 1^p + ... + 1^p = 1 + ... + 1 = a.∎$

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

$a u_1 ... a u_m = u_1 ... u_m.$

Rearranging yields

$a^{\phi(n)} = a^m = (u_1 ... u_m)(u_1 ... u_m)^{-1} = 1 .∎$

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

$d = m x + n y$

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

$a^d = a^{m x + n y} = (a^x)^m (a^y)^n = 1$

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

$b^{k x} = 1^k b^{k x} = (a^x)^k b^{k x} = (a b)^{k x} = 1 .$

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

$d = e^{-1} \pmod{\phi(N)}$

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.

Ben Lynn blynn@cs.stanford.edu 💡