Units, Order and Fermat's Little Theorem

Modular Arithmetic in $\mathbb{Z}_n$

Recall that $\mathbb{Z}_n = \{0, 1, 2, \ldots, n-1\}$ represents the integers modulo $n$. In this system, all arithmetic operations are performed modulo $n$.

In SageMath, we use Mod(a, n) to work with elements of $\mathbb{Z}_n$. This allows us to perform modular arithmetic easily.

Units Modulo $n$

Definition (Unit)

An element $a \in \mathbb{Z}_n$ is called a unit modulo $n$ if there exists an element $b \in \mathbb{Z}_n$ such that $ab \equiv 1 \pmod{n}$. In this case, we say $b$ is the multiplicative inverse of $a$ modulo $n$.

Examples:

In $\mathbb{Z}_7$, the element $5$ is a unit because $5 \cdot 3 = 15 \equiv 1 \pmod{7}$.
In $\mathbb{Z}_{12}$, the element $5$ is a unit because $5 \cdot 5 = 25 \equiv 1 \pmod{12}$.
In $\mathbb{Z}_{12}$, the element $6$ is not a unit (no integer $b$ satisfies $6b \equiv 1 \pmod{12}$).

Again, SageMath can compute inverses.

The following lemma characterizes exactly which elements are units.

Lemma

An element $a$ is a unit modulo $n$ if and only if $\gcd(a, n) = 1$.

Proof:

Observe there exists a solution to the congruence equation $ax \equiv 1 \pmod{n}$ if and only if there is some integer $y$ such that $1 - ax = ny$ which happens if and only if there is a solution to the linear diophantine equation (LDE) $ax + ny = 1$. By previous work, we know this LDE has a solution if and only if $\gcd(a,n) = 1$.

□

Order of Elements

Exploration: Patterns in Powers Modulo $n$

Before we define order formally, let's explore what happens when we compute successive powers of an integer modulo $n$.

Notice that for $2^k \pmod{7}$, we eventually get back to $1$. This leads us to the concept of order.

Definition (Order)

Let $a$ be a unit modulo $n$. The order of $a$ modulo $n$, denoted $\text{ord}_n(a)$, is the smallest positive integer $k$ such that $a^k \equiv 1 \pmod{n}$.

Important Note: The order of $a$ modulo $n$ exists if and only if $a$ is a unit modulo $n$ (i.e., $\gcd(a, n) = 1$). If $a$ is not a unit, then $a^k$ can never equal $1$ modulo $n$ for any positive integer $k$. (Exercise: provide a proof of this!)

Examples:

From our computation above, $\text{ord}_7(2) = 3$ because $2^3 = 8 \equiv 1 \pmod{7}$ and this is the smallest such power.
For $3$ modulo $10$, notice that $\gcd(3, 10) = 1$, so $3$ is a unit. What is it's order?

Order Modulo Primes

When $n$ is a prime number, something special happens. Let's explore this pattern. We can compute $\text{ord}_n(a)$ in Sage as Mod(a,n).multiplicative_order(), but the following code does this by hand (it also uses power_mod, which is another option to compute powers in $\mathbb{Z}_n$).

Observation: When $p$ is prime, the order of every unit modulo $p$ divides $p - 1$. This is a special case of a more general theorem (Lagrange's theorem in group theory), but we can prove a key lemma that helps explain this pattern.

Lemma

Let $a$ be a unit modulo $n$ with order $d = \text{ord}_n(a)$. If $a^k \equiv 1 \pmod{n}$, then $d \mid k$.

Proof:

Suppose $a^k \equiv 1 \pmod{n}$. By the division algorithm, we can write: $$k = qd + r$$ where $0 \leq r < d$.

Now, since $a^d \equiv 1 \pmod{n}$ (by definition of order), we have: $$a^k = a^{qd + r} = (a^d)^q \cdot a^r \equiv 1^q \cdot a^r \equiv a^r \pmod{n}$$ But we also know that $a^k \equiv 1 \pmod{n}$, so: $$a^r \equiv 1 \pmod{n}$$

Since $d$ is the smallest positive integer such that $a^d \equiv 1 \pmod{n}$, and we have $0 \leq r < d$ with $a^r \equiv 1 \pmod{n}$, we must have $r = 0$.

Therefore, $k = qd$, which means $d \mid k$. □

Fermat's Little Theorem

The observations we made about orders modulo primes lead us to one of the most important theorems in number theory.

Theorem (Fermat's Little Theorem)

Let $p$ be a prime number, and let $a$ be an integer such that $\gcd(a, p) = 1$. Then: $$a^{p-1} \equiv 1 \pmod{p}$$

Equivalently, for any integer $a$: $$a^p \equiv a \pmod{p}$$

Remarks:

This theorem tells us that for any unit $a$ modulo a prime $p$, raising $a$ to the power $p-1$ always gives us $1$ modulo $p$.
Combined with our lemma above, this explains why all orders modulo $p$ must divide $p-1$: since $a^{p-1} \equiv 1 \pmod{p}$ for all units $a$, and the order $d$ divides any exponent $k$ where $a^k \equiv 1 \pmod{p}$, we must have $d \mid (p-1)$.
This theorem has important applications in cryptography, particularly in the RSA algorithm.

Example: Let $p = 7$ and $a = 2$. Then: $$2^{7-1} = 2^6 = 64 \equiv 1 \pmod{7}$$

Indeed, $64 = 9 \cdot 7 + 1$, so $2^6 \equiv 1 \pmod{7}$.