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(modn)$ 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(mod7)$ are $3,2,6,4,5,1$ so the order of $3(mod7)$ is $6$.

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

Theorem: Let $p$ be a prime. Then $a^p=a(modp)$ 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 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^{\varphi (n)}=1(modn)$.

This reduces to Fermat’s Little Theorem when $n$ is prime.

Proof: Let $m=\varphi (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^{\varphi (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 $\varphi (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 $\varphi (n)$.

These statements are in fact trivial corollaries of Lagrange’s Theorem from group theory. Of course 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 $ab$?

Suppose $(ab{)}^k=1$. Raising both sides to $x$ shows

Since $b$ has order $y$ we see that $y\mid kx$.

Suppose $x,y$ are coprime. Then we must have $y\mid k$. Similarly $x\mid k$, hence $k$ must be a multiple of $xy$. On the other hand, we have $(\mathrm{ab}{)}^{xy}=1$. Hence the order of $ab$ is precisely $xy$: 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\mid ky$ and $y\mid kx$ 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=xy/d$, then $(ab{)}^z=1$. All we can say at the moment is that the order of $ab$ is a multiple of $xy/d^2$ and divides $xy/d$.

Suppose we are given positive integers $e,N$, and $a^e(modN)$ for some unit $a$. How can we recover $a$?

One strategy is to find an integer $d$ such that $a^{de}=a(modN)$. By Euler’s Theorem, $d$ will satisfy this equation if $de=k\varphi (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 $\varphi (N)$ from $N$ without factoring $N$, and it is not known how to factor large numbers efficiently.