# The primitive root theorem

The primitive root theorem identifies all the positive integers for which primitive roots exist. The list of such integers is a restrictive list. This post along with two previous posts give a complete proof of this theorem using only elementary number theory. We prove the following theorem.

Main Theorem (The Primitive Root Theorem)

There exists a primitive root modulo $m$ if and only if $m=2$, $m=4$, $m=p^t$ or $m=2p^t$ where $p$ is an odd prime number and $t$ is a positive integer.

The theorem essentially gives a list of the moduli that have primitive roots. Any modulus outside this restrictive list does not have primitive roots. For example, any integer that is a product of two odd prime factors is not on this list and hence has no primitive roots. In the post Primitive roots of powers of odd primes, we show that the powers of an odd prime have primitive roots. In the post Primitive roots of twice the powers of odd primes, we show that the moduli that are twice the power of an odd prime have primitive roots. It is easy to verify that the moduli $2$ and $4$ have primitive roots. Thus the direction $\Longleftarrow$ of the primitive root theorem has been established. In this post we prove the direction $\Longrightarrow$, showing that if there exists a primitive root modulo $p$, then $p$ must be one of the moduli in the list stated in the theorem.

___________________________________________________________________________________________________________________

LCM

The proof below makes use of the notion of the least common multiple. Let $a$ and $b$ be positive integers. The least common multiple of $a$ and $b$ is denoted by $\text{LCM}(a,b)$ and is defined as the least positive integer that is divisible by both $a$ and $b$. For example, $\text{LCM}(16,18)=144$. We can also express $\text{LCM}(a,b)$ as follows:

$\displaystyle \text{LCM}(a,b)=\frac{a \cdot b}{\text{GCD}(a,b)} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

where $\text{GCD}(a,b)$ is the greatest common divisor of $a$ and $b$. The above formula reduces the calculation of LCM to that of calculating the GCD. To compute the LCM of two numbers, we can simply remove the common prime factors between the two numbers. When the number $a$ and $b$ are relatively prime, i.e., $\text{GCD}(a,b)=1$, we have $\displaystyle \text{LCM}(a,b)=a \cdot b$.

Another way to look at LCM is that it is the product of multiplying together the highest power of each prime number. For example, $48=2^4 \cdot 3$ and $18=2 \cdot 3^2$. Then $\text{LCM}(16,18)=2^4 \cdot 3^2=144$.

The least common divisor of the numbers $a_1,a_2,\cdots,a_n$ is denoted by $\text{LCM}(a_1,a_2,\cdots,a_n)$ and is defined similarly. It is the least positive integer that is divisible by all $a_j$. Since the product of all the numbers $a_j$ is one integer that is divisible by each $a_k$, we have:

$\displaystyle \text{LCM}(a_1,a_2,\cdots,a_n) \le a_1 \cdot a_2 \cdots a_n \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

As in the case of two numbers, the LCM of more than two numbers can be thought as the product of multiplying together the highest power of each prime number. For example, the LCM of $48=2^4 \cdot 3$, $18=2 \cdot 3^2$ and $45=3^2 \cdot 5$ is $2^4 \cdot 3^2 \cdot 5=720$.

For a special case, there is a simple expression of LCM.

Lemma 1

Let $a_1,a_2,\cdots,a_n$ be positive integers.

Then $\displaystyle \text{LCM}(a_1,a_2,\cdots,a_n)=a_1 \cdot a_2 \cdots a_n$ if and only if the numbers $a_1,a_2,\cdots,a_n$ are pairwise relatively prime, i.e., $a_i$ and $a_j$ are relatively prime whenever $i \ne j$.

Proof of Lemma 1
$\Longleftarrow$
Suppose the numbers are pairwise relatively prime. Then there are no common prime factors in common between any two numbers on the list. Then multiplying together the highest power of each prime factor is the same as multiplying the individual numbers $a_1,a_2 \cdots,a_n$.

$\Longrightarrow$
Suppose $a_i$ and $a_j$ are not relatively prime for some $i \ne j$. As a result, $d=\text{GCD}(a_i,a_j)>1$. It follows that

$\displaystyle \text{LCM}(a_1,a_2,\cdots,a_n) \le \frac{a_1 \cdot a_2 \cdots a_n}{d} < a_1 \cdot a_2,\cdots a_n \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$

To give a sense of why the above is true, let’s look at a simple case of $d=\text{GCD}(a_i,a_j)=p^u$ where $p$ is a prime number and $u \ge 1$. Assume that $a_i=a_1$, $a_j=a_2$ and $p^u$ is part of the prime factorization of $a_1$. Furthermore, note that $\displaystyle \text{LCM}(\frac{a_1}{p^u},a_2,\cdots,a_n)$ is identical to $\displaystyle \text{LCM}(a_1,a_2,\cdots,a_n)$. The following derivation confirms (3):

$\displaystyle \text{LCM}(a_1,a_2,\cdots,a_n)=\text{LCM}(\frac{a_1}{p^u},a_2,\cdots,a_n) \le \frac{a_1}{p^u} \cdot a_2 \cdots a_n < a_1 \cdot a_2,\cdots a_n$

With the above clarification, the lemma is established. $\blacksquare$

___________________________________________________________________________________________________________________

Other Tools

We need to two more lemmas to help us prove the main theorem.

Lemma 2

Let $m$ and $n$ be positive integers that are relatively prime. Then $a \equiv b \ (\text{mod} \ m)$ and $a \equiv b \ (\text{mod} \ n)$ if and only if $a \equiv b \ (\text{mod} \ mn)$.
Lemma 3

The number $a$ is a primitive root modulo $m$ if and only if $\displaystyle a^{\frac{\phi(m)}{q}} \not \equiv 1 \ (\text{mod} \ m)$ for all prime divisors $q$ of $\phi(m)$.

Lemma 2 a version of the Chinese Remainder Theorem and is proved a previous post (see Theorem 2 in Primitive roots of twice the powers of odd primes or see Theorem 2 in Proving Chinese Remainder Theorem). Lemma 3 is also proved in a previous post (see Lemma 2 in More about checking for primitive roots).

___________________________________________________________________________________________________________________

Breaking It Up Into Smaller Pieces

The proof of the direction $\Longrightarrow$ of the primitive root theorem is done in the following lemmas and theorems.

Lemma 4

Let $\displaystyle m=p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$ be the prime factorization of the positive integer $m$. Let $a$ be a primitive root modulo $m$. Then the numbers $\phi(p_1^{e_1}), \phi(p_2^{e_2}),\cdots,\phi(p_t^{e_t})$ are pairwise relatively prime.

Proof of Lemma 4
Note that $a$ is relatively prime to $m$. So $a$ is relatively prime to each $p_j^{e_j}$. By Euler’s theorem, we have $\displaystyle a^{\phi(p_j^{e_j})} \equiv 1 \ (\text{mod} \ p_j^{e_j})$ for each $j$. Let $\displaystyle W=\text{LCM}(\phi(p_1^{e_1}),\phi(p_2^{e_2}),\cdots,\phi(p_t^{e_t}))$.

By definition of LCM, $\phi(p_j^{e_j}) \ \lvert \ W$ for each $j$. So $\displaystyle a^{W} \equiv 1 \ (\text{mod} \ p_j^{e_j})$ for each $j$. By the Chinese remainder theorem (Lemma 2 above), $\displaystyle a^{W} \equiv 1 \ (\text{mod} \ m)$. Since $a$ is a primitive root modulo $m$, it must be that $\phi(m) \le W$. Interestingly, we have:

$\displaystyle \phi(p_1^{e_1}) \phi(p_2^{e_2}) \cdots \phi(p_t^{e_t})=\phi(m) \le W \le \phi(p_1^{e_1}) \phi(p_2^{e_2}) \cdots \phi(p_t^{e_t})$

Thus $\displaystyle \text{LCM}(\phi(p_1^{e_1}),\phi(p_2^{e_2}),\cdots,\phi(p_t^{e_t}))=\phi(p_1^{e_1}) \phi(p_2^{e_2}) \cdots \phi(p_t^{e_t})$. By Lemma 1, the numbers $\phi(p_j^{e_j})$ are relatively prime. $\blacksquare$

The following theorems follow from Lemma 4. The main theorem is a corollary of these theorems.

Theorem 5

If there exists a primitive root modulo $m$, then $m$ cannot have two distinct prime divisors.

Proof of Theorem 5
Let $\displaystyle m=p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$ be the prime factorization of $m$ where $t \ge 2$.

If $p_i$ and $p_j$ are odd prime with $i \ne j$, then $\phi(p_i^{e_i})=p_i^{e_i-1}(p_i-1)$ and $\phi(p_j^{e_j})=p_j^{e_j-1}(p_j-1)$ are both even and thus not relatively prime. If there exists a primitive root modulo $m$, $\phi(p_i^{e_i})$ and $\phi(p_j^{e_j})$ must be relatively prime (see Lemma 4). Since we assume that there exists a primitive root modulo $m$, $m$ cannot have two distinct odd prime divisors. $\blacksquare$

Theorem 6

Suppose that there exists a primitive root modulo $m$ and that $m$ has exactly one odd prime factor $p$. Then $m$ must be of the form $p^e$ or $2p^e$ where $e \ge 1$.

Proof of Theorem 6
By Theorem 5, the prime factorization of $m$ must be $m=2^{e_1} p^{e_2}$ where $e_1 \ge 0$ and $e_2 \ge 1$.

We claim that $e_1=0$ or $e_1=1$. Suppose $e_1 \ge 2$. Then $\phi(2^{e_1})=2^{e_1-1}$ and $\phi(p^{e_2})=p^{e_2-1}(p-1)$ are both even and thus not relatively prime. Lemma 4 tells us that there does not exist a primitive root modulo $m$. So if there exists a primitive root modulo $m$, then it must be the case that $e_1=0$ or $e_2=1$.

If $e_1=0$, then $m=p^{e_2}$. If $e_1=1$, then $m=2p^{e_2}$. $\blacksquare$

Lemma 7

Let $n=2^k$ where $k \ge 3$. Then $\displaystyle a^{\frac{\phi(n)}{2}} \equiv 1 \ (\text{mod} \ n)$ for any $a$ that is relatively prime to $n$.

Proof of Lemma 7
We prove this by induction on $k$. Let $k=3$. Then $n=8$ and $\displaystyle \frac{\phi(8)}{2}=2$. For any odd $a$ with $1 \le a <8$, it can be shown that $a^2 \equiv 1 \ (\text{mod} \ 8)$.

Suppose that the lemma holds for $k$ where $k \ge 3$. We show that it holds for $k+1$. Note that $\phi(2^k)=2^{k-1}$ and $\displaystyle \frac{\phi(2^k)}{2}=2^{k-2}$. Since the lemma holds for $k$, we have $\displaystyle v^{2^{k-2}} \equiv 1 \ (\text{mod} \ 2^k)$ for any $v$ that is relatively prime to $2^k$. We can translate this congruence into the equation $v^{2^{k-2}}=1+2^k y$ for some integer $y$.

Note that $\phi(2^{k+1})=2^{k}$ and $\displaystyle \frac{\phi(2^{k+1})}{2}=2^{k-1}$. It is also the case that $(v^{2^{k-2}})^2=v^{2^{k-1}}$. Thus we have:

$\displaystyle v^{2^{k-1}}=(1+2^k y)^2=1+2^{k+1} y+2^{2k} y^2=1+2^{k+1}(y+2^{k-1} y^2)$

The above derivation shows that $\displaystyle v^{\frac{\phi(2^{k+1})}{2}} \equiv 1 \ (\text{mod} \ 2^{k+1})$ for any $v$ that is relatively prime to $2^k$.

On the other hand, $a$ is relatively prime to $2^{k+1}$ if and only if $a$ is relatively prime to $2^k$. So $\displaystyle a^{\frac{\phi(2^{k+1})}{2}} \equiv 1 \ (\text{mod} \ 2^{k+1})$ for any $a$ that is relatively prime to $2^{k+1}$. Thus the lemma is established. $\blacksquare$

Theorem 8

Suppose that there exists a primitive root modulo $m$ and that $m=2^e$ where $e \ge 1$. Then $m=2^e$ where $e=1$ or $e=2$.

Proof of Theorem 8
Suppose $m=2^e$ where $e \ge 3$. By Lemma 7, $\displaystyle a^{\frac{\phi(m)}{2}} \equiv 1 \ (\text{mod} \ n)$ for any $a$ relatively prime to $m$. Since $2$ is the only prime divisor of $m$, by Lemma 3, there cannot be primitive root modulo $m$. Thus if there exists a primitive root modulo $m$ and that $m=2^e$ where $e \ge 1$, then the exponent $e$ can be at most $2$. $\blacksquare$

___________________________________________________________________________________________________________________

Putting It All Together

We now put all the pieces together to prove the $\Longrightarrow$ of the Main Theorem. It is a matter of invoking the above theorems.

Proof of Main Theorem
Suppose that there exists a primitive root modulo $m$. Consider the following three cases about the modulus $m$.

1. $m$ has no odd prime divisor.
2. $m$ has exactly one odd prime divisor.
3. $m$ has at least two odd prime divisors.

$\text{ }$
Suppose Case 1 is true. Then $m=2^e$ where $e \ge 1$. By Theorem 8, $m=2$ or $m=4$.

Suppose Case 2 is true. Then Theorem 6 indicates that $m$ must be the power of an odd prime or twice the power of an odd prime.

Theorem 5 indicates that Case 3 is never true. Thus the direction $\Longrightarrow$ of the Main Theorem is proved. $\blacksquare$

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

# Defining Primitive Root

In this post, we define the notion of primitive root and prove some elementary results. Instead of jumping right into the definition, we take a leisurely approach by first looking at some of the related basic notions.

___________________________________________________________________________________________________________________

Setting Up the Scene

Two positive integers $a$ and $b$ are relatively prime if they do not share any prime factors, i.e., their greatest common divisor is one (the only positive integer that can divide both numbers is one). For example, $a=9$ and $b=14$ are relatively prime, as are $a=9$ and $b=35$. If $a$ and $b$ are relatively prime, we also say that $a$ is relatively prime to $b$ or $b$ is relatively prime to $a$. Our notation for greatest common divisor is $\text{GCD}(a,b)$.

In working with modular arithmetic where the modulus is the positive integer $m$, every integer is congruent modulo $m$ to exactly one number in the set $\left\{0,1,2,\cdots,m-1 \right\}$. The numbers in this set are called the least residues modulo $m$. In doing modulus $m$ calculation, for some purposes we only need to reduce the result to one number in this set. For convenience, we use the notation $\mathbb{Z}_m=\left\{0,1,2,\cdots,m-1 \right\}$.

An even more interesting set is the set of all integers $a$ in $\mathbb{Z}_m$ such that $a$ and the modulus $m$ are relatively prime. To facilitate the discussion, we describe this set as follows:

\displaystyle \begin{aligned} (\mathbb{Z}_m)^*&=\left\{a \in \mathbb{Z}_m: a \text{ is relatively prime to } m \right\} \\&=\left\{a \in \mathbb{Z}_m:\text{GCD}(a,m) =1 \right\} \end{aligned}

When the modulus $m$ is a prime number, $(\mathbb{Z}_m)^*=\left\{1,2,\cdots,m-1 \right\}$, the non-zero elements of $\mathbb{Z}_m$. The following theorem gives some indication why $(\mathbb{Z}_m)^*$ is an interesting set, which provides alternative characterizations of $(\mathbb{Z}_m)^*$.

Theorem 1

Let $a$ be an integer in $\mathbb{Z}_m$. The following conditions are equivalent.

1. $\text{GCD}(a,m)=1$.
2. There is a $b \in \mathbb{Z}_m$ such that $a \cdot b \equiv 1 \ (\text{mod} \ m)$.
3. Some positive power of $a$ modulo $m$ is $1$, i.e., $a^n \equiv 1 \ (\text{mod} \ m)$ for some positive integer $n$.

$\text{ }$

The proof of Theorem 1 can be found in the post Euler’s phi function, part 1.

The Euler’s phi function, denoted by $\phi(m)$, is the number of integers $a$ where $0 \le a \le m-1$ such that $a$ and the modulus $m$ are relatively prime. In light of the above discussion, $\phi(m)$ is the number of elements in the set $(\mathbb{Z}_m)^*$. It is also the case that $\phi(m)$ is the number of elements in $\mathbb{Z}_m$ that satisfies any one of the three conditions in Theorem 1.

___________________________________________________________________________________________________________________

Defining Primitive Root

When we are interested in the power of a number being one congruence modulo $m$, according to Theorem 1, the base has to be a number that is relatively prime to the modulus. We have already come across two such situations – Fermat’s little theorem and its generalization, Euler’s theorem.

Theorem 2 (Fermat’s little theorem)

Let the modulus $m$ be a prime number. Then $a^{m-1} \equiv 1 \ (\text{mod} \ m)$ for any integer $a$ that is relatively prime to $m$.

$\text{ }$

Theorem 3 (Euler’s theorem)

It is the case that $a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)$ for any integer $a$ that is relatively prime to $m$.

$\text{ }$

Theorem 2 follows from Theorem 3, which is proved in the post Euler’s phi function, part 1.

Definitions
We now define the notion of primitive root. Let $a$ be an integer in $\mathbb{Z}_m$ that is relatively prime to the modulus $m$. Based on the above theorems, $a^k \equiv 1 \ (\text{mod} \ m)$ for some positive integer $k$. By the order of $a$ modulo $m$, we mean the least positive integer $k$ such that $a^k \equiv 1 \ (\text{mod} \ m)$. The number $a$ is a primitive root modulo $m$ if the order of $a$ modulo $m$ is the number $\phi(m)$.

By Theorem 3, the order of $a$ modulo $m$ is always $\le \phi(m)$. We will see below that the order always divides $\phi(m)$ (see Theorem 4).

One comment. The notions of order and primitive roots are defined above for integers in $\mathbb{Z}_m$. In actuality, the two notations can be defined for all positive integers. It is just that we are interested in finding primitive roots among the residues, i.e., the elements of the set $\mathbb{Z}_m$. In some cases, it will be helpful to think of orders of numbers outside of $\mathbb{Z}_m$ and think of numbers outside of $\mathbb{Z}_m$ as primitive roots (e.g. in the proof of Theorem 6 below).

Suppose that the modulus $m$ is a prime number. Fermat’s little theorem tells us that $a^{m-1} \equiv 1 \ (\text{mod} \ m)$ for any $a$ that is relatively prime to $m$. Is $m-1$ the only exponent for which the power of $a$ is one? Take $m=11$. The following table gives the powers of $a$ modulus $m=11$ where $1 \le a \le 10$.

$\displaystyle \begin{bmatrix} a^1&a^2&a^3&a^4&a^5&a^6&a^7&a^8&a^9&a^{10} \\\text{ }&\text{ }&\text{ } \\ 1&1&1&1&1&1&1&1&1&1 \\ 2&4&8&5&10&9&7&3&6&1 \\ 3&9&5&4&1&3&9&5&4&1 \\ 4&5&9&3&1&4&5&9&3&1 \\ 5&3&4&9&1&5&3&4&9&1 \\ 6&3&7&9&10&5&8&4&2&1 \\ 7&5&2&3&10&4&6&9&8&1 \\ 8&9&6&4&10&3&2&5&7&1 \\ 9&4&3&5&1&9&4&3&5&1 \\ 10&1&10&1&10&1&10&1&10&1 \end{bmatrix}$

The above table shows that for $a=2,6,7,8$, the number $10$ is the least exponent for which the power of $a$ is one. In other words, the order for these $a$ is $\phi(11)=10$. The numbers $a=2,6,7,8$ are primitive roots modulo $m=11$. The other values of $a$ are not primitive roots. The order for $a=1$ is $1$. The order for $a=10$ is $2$. The order for $a=3,4,5,9$ is $5$.

Note that in the above table, for the numbers $a$ that are primitive roots, the set $\left\{a^1,a^2,a^3,\cdots,a^{\phi(11)} \right\}$ equals the set $\left\{1,2,3,\cdots,10 \right\}$. So a primitive root generates by powering all the least residues that are relatively prime to the modulus.

Let’s look at a modulus that is not prime. Take $m=10$. The following table gives the powers of $a$ modulus $m=10$ where $1 \le a \le 9$.

$\displaystyle \begin{bmatrix} a^1&a^2&a^3&a^4&a^5&a^6&a^7&a^8&a^9 \\\text{ }&\text{ }&\text{ } \\ 1&1&1&1&1&1&1&1&1 \\ 2&4&8&6&2&4&8&6&2 \\ 3&9&7&1&3&9&7&1&3 \\ 4&6&4&6&4&6&4&6&4 \\ 5&5&5&5&5&5&5&5&5 \\ 6&6&6&6&6&6&6&6&6 \\ 7&9&3&1&7&9&3&1&7 \\ 8&4&2&6&8&4&2&6&8 \\ 9&1&9&1&9&1&9&1&9 \end{bmatrix}$

Note that $\phi(10)=4$ since $(\mathbb{Z}_{10})^*=\left\{1,3,7,9 \right\}$ is the set of all the least residues that are relatively prime to $m=10$. In terms of powers of $a$, we should only focus on $\left\{1,3,7,9 \right\}$. The following is the reduced table.

$\displaystyle \begin{bmatrix} a^1&a^2&a^3&a^4&a^5&a^6&a^7&a^8&a^9 \\\text{ }&\text{ }&\text{ } \\ 1&1&1&1&1&1&1&1&1 \\ 3&9&7&1&3&9&7&1&3 \\ 7&9&3&1&7&9&3&1&7 \\ 9&1&9&1&9&1&9&1&9 \end{bmatrix}$

Note that $a^4 \equiv 1 \ (\text{mod} \ 10)$ for all four $a$. But only $a=3,7$ are primitive roots modulo $m=10$.

Also note that in the above table, for the numbers $a$ that are primitive roots, the set $\left\{a^1,a^2,a^3,a^4 \right\}$ equals the set $\left\{1,3,7,9 \right\}$. So a primitive root generates by powering all the least residues that are relatively prime to the modulus.

Not all moduli have primitive roots. Take $m=8$. The least residues that are relatively prime to $m=8$ are the set $\left\{1,3,5,7 \right\}$. Note that $a^2 \equiv 1 \ (\text{mod} \ 8)$ for every $a$ in this set. Thus no number $a$ in this set can have order = $\phi(8)=4$.

___________________________________________________________________________________________________________________

Elementary Results

One observation can be made about the above small tables for $m=11$ and $m=10$ is that all exponents for which the power of $a$ is one are the multiples of the order. We have the following theorem.

Theorem 4

Let $a$ be an integer where $0 \le a \le m-1$ such that $a$ is relatively prime to the modulus $m$. Suppose $k$ is the order of the number $a$ modulo $m$. Then $a^n \equiv 1 \ (\text{mod} \ m)$ if and only if $n$ is a multiple of $k$.

Proof of Theorem 4

$\Longleftarrow$
This direction is clear. If $n=q \cdot k$ for some integer $q$, then $a^n=(a^k)^q \equiv 1 \ (\text{mod} \ m)$.

$\Longrightarrow$
Suppose that $a^n \equiv 1 \ (\text{mod} \ m)$. By the division algorithm, we have $n=q \cdot k+r$ for some integers $q$ and $r$ where $0 \le r . We have the following:

$a^n=(a^k)^q \cdot a^r \equiv a^r \ (\text{mod} \ m)$

Since $r and $a^r \equiv 1 \ (\text{mod} \ m)$, it must be the case that $r=0$, implying that $n=q \cdot k$. $\blacksquare$

We have the following corollary.

Corollary 5

Let $a$ be an integer where $0 \le a \le m-1$ such that $a$ is relatively prime to the modulus $m$. Suppose $k$ is the order of the number $a$ modulo $m$. Then $\phi(m)$ is a multiple of $k$.

Another observation from the above small tables is that a primitive root, through powering, is a generator of the least residues that are relatively prime to the modulus.

Theorem 5

Let $a$ be an integer where $0 \le a \le m-1$ such that $a$ is relatively prime to the modulus $m$. The following conditions are equivalent.

1. The number $a$ is a primitive root modulo $m$.
2. The set $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$, where each $a^j$ is considered as the least residues modulo $m$, is precisely the set $(\mathbb{Z}_m)^*$.

$\text{ }$

Recall that $(\mathbb{Z}_m)^*$ is the set of all $a \in \mathbb{Z}_m=\left\{0,1,2,3,\cdots,m-1 \right\}$ such that $a$ is relatively prime to $m$.

Proof of Theorem 5

$1 \Longrightarrow 2$
Suppose that the number $a$ is a primitive root modulo $m$. The first step in showing condition 2 is to show that the $\phi(m)$ numbers in the set $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ are distinct congruent modulo $m$. Then it follows that their least residues modulo $m$ are distinct too.

Suppose $a^j \equiv a^i \ (\text{mod} \ m)$ where $i,j \le \phi(m)$. We want to show that $i=j$. Suppose $i. Then cancel out $a^i$ on both sides of the equation since $a^i$ is relatively prime to $m$. We have $a^{j-i} \equiv 1 \ (\text{mod} \ m)$. But $j-i<\phi(m)$. Since $a$ is a primitive root modulo $m$, we cannot have $a^{j-i} \equiv 1 \ (\text{mod} \ m)$. So it must be the case that $j=i$. So if $a^j \equiv a^i \ (\text{mod} \ m)$, then $i=j$. Equivalently, if $i \ne j$, $a^j \not \equiv a^i \ (\text{mod} \ m)$. Thus the least residues modulo $m$ of the values in $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ are distinct too.

Since $a^i$ is relatively prime to $m$, its least residue is also relatively prime to $m$. Now the least residues modulo $m$ of the values in $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ consist of $\phi(m)$ numbers inside $(\mathbb{Z}_m)^*$, which is also a set of $\phi(m)$ many numbers. So the two sets must equal.

$2 \Longrightarrow 1$
We show the contrapositive of $2 \Longrightarrow 1$. Suppose that the order of $a$ modulo $m$ is $j$ where $1 \le j<\phi(m)$. So $a^j \equiv 1 \ (\text{mod} \ m)$ and $a^{j+1} \equiv a \ (\text{mod} \ m)$. So $a$ and $a^{j+1}$ are two elements in the set $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ that are congruent to each other. This means that the least residues of $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ have less than $\phi(m)$ many values. In other words, the number $a$, through powering, cannot generate all the least residues that are relatively prime to the modulus $m$. $\blacksquare$

The following theorem and corollary give the number of primitive root modulo $m$ as long as it is known that there is a primitive root modulo $m$.

Theorem 6

Let $a$ be a primitive root modulo $m$. Then for any positive integer $k$, the least residue of $a^k$ is a primitive root modulo $m$ if and only if $k$ is relatively prime to $\phi(m)$.

Proof of Theorem 6

$\Longrightarrow$
Suppose that $k$ is not relatively prime to $\phi(m)$. So $d=\text{GCD}(k,\phi(m))>1$. Then we have:

$\displaystyle (a^k)^{\frac{\phi(m)}{d}}=(a^{\phi(m)})^{\frac{k}{d}} \equiv 1 \ (\text{mod} \ m)$

With $\displaystyle b=\frac{\phi(m)}{d}<\phi(m)$ and $(a^k)^b \equiv 1 \ (\text{mod} \ m)$, it follows that $a^k$ is not a primitive root modulo $m$. Hence the least residue of $a^k$ modulo $m$ is also not a primitive root. Thus if the least residue of $a^k$ is a primitive root modulo $m$, it must be that $\text{GCD}(k,\phi(m))=1$.

$\Longleftarrow$
Suppose $\text{GCD}(k,\phi(m))=1$. Let $\alpha$ be the order of $a^k$ modulo $m$. By the definition of order, $a^{k \cdot \alpha}=(a^k)^\alpha \equiv 1 \ (\text{mod} \ m)$. Based on the fact that the order of $a$ modulo $m$ is $\phi(m)$, we have $\phi(m) \ \lvert \ k \cdot \alpha$ (also using Theorem 4). Since $\text{GCD}(k,\phi(m))=1$, it must be the case that $\phi(m) \ \lvert \ \alpha$.

On the other hand, $(a^k)^{\phi(m)}=(a^{\phi(m)})^k \equiv 1 \ (\text{mod} \ m)$. Using the fact that the order of $a^k$ is $\alpha$ (and using Theorem 4), $\alpha \ \lvert \ \phi(m)$.

With $\phi(m) \ \lvert \ \alpha$ and $\alpha \ \lvert \ \phi(m)$, it follows that $\alpha = \phi(m)$. This implies that $a^k$ is a primitive root modulo $m$, and so is its least residue modulo $m$. $\blacksquare$

Corollary 7

Suppose that there exists a primitive root modulo $m$. Then there are exactly $\phi(\phi(m))$ many primitive roots modulo $m$.

Proof of Corollary 7

Let $a$ be a primitive root modulo $m$. By Theorem 6, the least residue of $a^k$ is a primitive roots modulo $m$ if and only if $k$ is relatively prime to the number $\phi(m)$. There are precisely $\phi(\phi(m))$ many such numbers $k$.

Furthermore, according to Theorem 5, the least residues of the values in $\left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}$ are all distinct. Thus the least residues of the powers $a^k$ for the $\phi(\phi(m))$ many $k$ are primitive roots modulo $m$. $\blacksquare$

___________________________________________________________________________________________________________________

An Algorithm

The theorems and corollaries in this post form an elementary algorithm for finding primitive roots of a modulus (if one is known to exist). The algorithm is described in the post An elementary algorithm for finding primitive roots. An example is given in the post Finding Primitive Roots.

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

# Euler’s phi function, part 1

This is our first post of an introductory discussion on Euler’s phi function. The next post on phi function is here.

___________________________________________________________________________________________________________________

Setting Up the Scene

The starting point of this discussion is the relative primality of two integers. Two positive integers $a$ and $b$ are relatively prime if $1$ is the only common divisor of $a$ and $b$. Note that $a$ and $b$ need not be prime. For example, $a=9$ and $b=14$ are relatively prime, as are $a=9$ and $b=35$. It is clear that $a$ and $b$ are relatively prime if and only if they share no common prime factors. The last point is equivalent to the condition that the greatest common divisor of $a$ and $b$ is $1$. Our notation for greatest common divisor is $\text{GCD}(a,b)$.

If $a$ and $b$ are relatively prime, we also say that $a$ is relatively prime to $b$ or $b$ is relatively prime to $a$. In the remainder of the blog post, $m$ is always a positive integer that is the modulus used for modular arithmetic.

In modular arithmetic where the modulus is $m$, we only need to focus on $m$ distinct numbers, namely the elements in the set $\left\{0,1,2,\cdots,m-1 \right\}$. Any integer is congruent modulo $m$ to exactly one element of this set (the elements of this set are also called the least residues modulo $m$). For convenience, we use the notation $\mathbb{Z}_m=\left\{0,1,2,\cdots,m-1 \right\}$.

An even more interesting set is the set of all integers $a$ in $\mathbb{Z}_m$ such that $a$ and the modulus $m$ are relatively prime. To facilitate the discussion, we describe this set as follows:

$(\mathbb{Z}_m)^*=\left\{a \in \mathbb{Z}_m:\text{GCD}(a,m) =1 \right\}$

When the modulus $m$ is a prime number, $(\mathbb{Z}_m)^*=\left\{1,2,\cdots,m-1 \right\}$, the non-zero elements of $\mathbb{Z}_m$. When the modulus is not prime, there are fewer least residues that are relatively prime to the modulus. The following shows $(\mathbb{Z}_m)^*$ for the first several integers.

$(\mathbb{Z}_{2})^*=\left\{1 \right\}$

$(\mathbb{Z}_{3})^*=\left\{1,2 \right\}$

$(\mathbb{Z}_{4})^*=\left\{1,3 \right\}$

$(\mathbb{Z}_{5})^*=\left\{1,2,3,4 \right\}$

$(\mathbb{Z}_{6})^*=\left\{1,5 \right\}$

$(\mathbb{Z}_{7})^*=\left\{1,2,3,4,5,6 \right\}$

$(\mathbb{Z}_{8})^*=\left\{1,3,5,7 \right\}$

$(\mathbb{Z}_{9})^*=\left\{1,2,4,5,7,8 \right\}$

$(\mathbb{Z}_{10})^*=\left\{1,3,7,9 \right\}$

$(\mathbb{Z}_{11})^*=\left\{1,2,3,4,5,6,7,8,9,10 \right\}$

The following theorem gives some indication why $(\mathbb{Z}_m)^*$ is an interesting set, which provides alternative characterizations of $(\mathbb{Z}_m)^*$.

Theorem 1

Let $a$ be an integer in $\mathbb{Z}_m$. The following conditions are equivalent.

1. $\text{GCD}(a,m)=1$.
2. There is a $b \in \mathbb{Z}_m$ such that $a \cdot b \equiv 1 \ (\text{mod} \ m)$.
3. Some positive power of $a$ modulo $m$ is $1$, i.e., $a^n \equiv 1 \ (\text{mod} \ m)$ for some positive integer $n$.

$\text{ }$

The number $b$ indicated in condition 2 is said to be the multiplicative inverse of $a$. Theorem 1 says that only the least residues that are relatively prime to the modulus have multiplicative inverses. Condition 3 tells us that to have a power congruent to one, which is of interest in many situations, the base must be relatively prime to the modulus.

We need the following lemma to prove Theorem 1.

Lemma 2

If $\text{GCD}(a,m)=1$, then for any positive integer $n$, $a^n$ is also relatively prime to $m$.

Proof of Lemma 2
Suppose $\text{GCD}(a,m)=1$. By the extended Euclidean algorithm, we have the following:

$ax+my=1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

for some integers and $x$ and $y$.

We prove by induction on $n$. When $n=1$, lemma is true. Suppose that $a^n$ is relatively prime to $m$ where $n \ge 1$. We show that $a^{n+1}$ is relatively prime to $m$. Multiple both sides of (1) by $a^n$. We have $a^{n+1} x+m (ya^n)=a^n$. Let $d=\text{GCD}(a^{n+1},m)$. Note that $d$ is a divisor of the left-hand side of $a^{n+1} x+m (ya^n)=a^n$. So $d$ is a divisor of $a^n$. Now we know that $d$ is a common divisor of $a^n$ and $m$. Then $d=1$, which means that $a^{n+1}$ is relatively prime to $m$. $\blacksquare$

Proof of Theorem 1

$\bold 3 \bold \Longrightarrow \bold 2$
Suppose that $a^n \equiv 1 \ (\text{mod} \ m)$ for some positive integer $n$. If $n=1$, then let $b=1$. If $n>1$, then let $b=a^{n-1}$. Either way, there is $b \in \mathbb{Z}_m$ such that $a \cdot b \equiv 1 \ (\text{mod} \ m)$.

$\bold 2 \bold \Longrightarrow \bold 1$
Suppose there is a $b \in \mathbb{Z}_m$ such that $a \cdot b \equiv 1 \ (\text{mod} \ m)$. Then we have

$ab+my=1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

for some integer $y$.

Let $d=\text{GCD}(a,m)$. Since $d$ divides both numbers in the left-hand side of (2), $d \ \lvert \ 1$. Then $d=1$.

$\bold 1 \bold \Longrightarrow \bold 3$
Suppose $\text{GCD}(a,m)=1$. Consider the $a^1,a^2,a^3,\cdots$ and then consider their least residues modulo $m$. By Lemma 2, each $a^n$ and $m$ are relatively prime. Hence the least residue of $a^n$ and $m$ are also relatively prime. But there are only finitely many least residues modulo $m$. So there exist positive integers $i the least residues of $a^i$ and $a^j$ are identical.

We have $a^j \equiv a^i \ (\text{mod} \ m)$. Since $a^i$ and $m$ are relatively prime, we can cancel out $a^i$ on both sides. Thus $a^{j-i} \equiv 1 \ (\text{mod} \ m)$. $\blacksquare$

___________________________________________________________________________________________________________________

Euler’s Phi Function

The Euler’s phi function, denoted by $\phi(m)$, is the number of integers $a$ where $0 \le a \le m-1$ such that $a$ and the modulus $m$ are relatively prime. In light of the above discussion, $\phi(m)$ is the number of elements in the set $(\mathbb{Z}_m)^*$. It is also the case that $\phi(m)$ is the number of elements in $\mathbb{Z}_m$ that satisfies any one of the three conditions in Theorem 1.

If the modulus $m$ is a prime number, then $\phi(m)=m-1$. The following shows several values of $\phi(m)$.

\displaystyle \begin{aligned} &\phi(2)=1 \\&\phi(3)=2 \\&\phi(4)=2 \\&\phi(5)=4 \\&\phi(6)=2 \\&\phi(7)=6 \\&\phi(8)=4 \\&\phi(9)=6 \\&\phi(10)=4 \\&\phi(11)=10 \end{aligned}

When the modulus $m$ is a prime number, Fermat’s little theorem tells us that $a^{\phi(m)}=a^{m-1} \equiv 1 \ (\text{mod} \ m)$ for any $a \in (\mathbb{Z}_m)^*=\left\{1,2,3,\cdots,m-1 \right\}$. This fact is true even when the modulus is not prime if the power is kept as $\phi(m)$. We have the following theorem.

Theorem 3 (Euler’s Theorem)

We have $a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)$ for any integer $a$ that is relatively prime to the modulus $m$.

Theorem 3 can also be stated as: $a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)$ for any $a \in (\mathbb{Z}_m)^*$. The proof is amazingly similar to that of Fermat’s little theorem (see the post Proving Fermat’s Little Theorem). We use the following lemma in proving Theorem 3.

Lemma 4

If integers $h$ and $k$ satisfy any condition in Theorem 1, then so does the product $h \cdot k$.

Proof of Lemma 4

Since the 3 conditions in Theorem 1 are equivalent, it does not matter which one we pick. Condition 2 is probably the most convenient. So we show that if $h$ has a multiplicative inverse and $k$ has a multiplicative inverse, then $h \cdot k$ has a multiplicative inverse modulo $m$.

Suppose $h \cdot h_0 \equiv 1 \ (\text{mod} \ m)$ and $k \cdot k_0 \equiv 1 \ (\text{mod} \ m)$ for some integers $h_0$ and $k_0$ in $\mathbb{Z}_m$. We multiply the two congruences and obtain:

$h \cdot h_0 \cdot k \cdot k_0=(h \cdot k) \cdot (h_0 \cdot k_0) \equiv 1 \ (\text{mod} \ m)$

if $h_0 \cdot k_0$ is in $\mathbb{Z}_m$, then it is the multiplicative inverse of $h \cdot k$. If not, then take the least residue mod $m$. $\blacksquare$

Proof of Theorem 3

Let $a$ be an integer that is relatively prime to the modulus $m$, i.e., $\text{GCD}(a,m)=1$. Let $\left\{t_1,t_2,t_3,\cdots,t_{\phi(m)} \right\}$ enumerate the $\phi(m)$ many elements of $(\mathbb{Z}_m)^*$. Multiply these elements by $a$ and we have the following set:

$A=\left\{a \cdot t_1,a \cdot t_2,a \cdot t_3,\cdots,a \cdot t_{\phi(m)} \right\}$

Consider the least residues modulo $m$ of the members of the set $A$. We have:

$B=\left\{b_1,b_2,b_3,\cdots,b_{\phi(m)} \right\}$

Note that for each $b_j \in B$, $b_j \in \mathbb{Z}_m$ and $b_j \equiv a \cdot t_j \ (\text{mod} \ m)$. We have two claims.

• The numbers $b_i$ and $b_j$ are distinct whenever $i \ne j$.
• Each $b_j$ is relatively prime to the modulus $m$, i.e., $b_j \in (\mathbb{Z}_m)^*$ for each $j$.

The first claims tells us that the set $B$ has $\phi(m)$ many distinct elements. The second claims tells us that the set $B$ is a subset of $(\mathbb{Z}_m)^*=\left\{t_1,t_2,t_3,\cdots,t_{\phi(m)} \right\}$. Since the subset $B$ has $\phi(m)$ many distinct elements and $(\mathbb{Z}_m)^*$ has $\phi(m)$ many distinct elements, they must equal. So we have $B=(\mathbb{Z}_m)^*$. With this information, we have the following congruence equation.

$\displaystyle at_1 \cdot a t_2 \cdot a t_3 \cdots a t_{\phi(m)} \equiv t_1 \cdot t_2 \cdot t_3 \cdots t_{\phi(m)} \ (\text{mod} \ m)$

Because each $t_j$ is relatively prime to the modulus, we can cancel out all $t_j$ and obtain:

$\displaystyle a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)$

So the theorem hinges on the two claims listed above. We now prove them one by one. To show the first claim, suppose $b_i=b_j$. Then $a \cdot t_i \equiv a \cdot t_j \ (\text{mod} \ m)$. We can cancel out $a$ on both sides since $a$ is relatively prime to $m$. We have $t_i \equiv t_j \ (\text{mod} \ m)$. Since both $t_i$ and $t_j$ are least residues mod $m$, for them to be congruent to each other, the only possibility is $t_i=t_j$. Thus $i=j$. The contrapositive of what we just show is that if $i \ne j$, then $b_i \ne b_j$. So the numbers $b_j$ are all distinct.

To show the second claim, note that $b_j \equiv a \cdot t_j \ (\text{mod} \ m)$. Both $a$ and $t_j$ are relatively prime to $m$. So by Lemma 4, $a \cdot t_j$ is relatively prime to $m$. Hence $b_j$ is relatively prime to the modulus $m$. $\blacksquare$

___________________________________________________________________________________________________________________

The setting for the phi function deserves some comments. The sets $\mathbb{Z}_m$ and $(\mathbb{Z}_m)^*$ defined above can be considered as algebraic objects.

The set $\mathbb{Z}_m=\left\{0,1,2,\cdots,m-1 \right\}$ along with addition and multiplication modulo $m$ is a ring. Thus $\mathbb{Z}_m$ is often called the ring of integers modulo $m$.

Based on Theorem 1 and Lemma 4, the set $(\mathbb{Z}_m)^*$ with the multiplication modulo $m$ is a group, i.e., it is a set with a binary operation called multiplication such that every element has an inverse.

Let the modulus $m$ is a prime number. As indicated above, $(\mathbb{Z}_m)^*=\left\{1,2,\cdots,m-1 \right\}$. An interesting angle is that $\mathbb{Z}_m$ can be considered a commutative ring in which every non-zero element has a multiplicative inverse, i.e., $\mathbb{Z}_m$ is a field (in fact a finite field).

Though we do not focus too much on the algebraic side of things in this blog, $\mathbb{Z}_m$, as a field, plays an important role in number theory and has applications in cryptography.

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

# Solving Linear Diophantine Equations

Equations such as the ones in the following list always have solutions in real numbers. When we focus only on integer solutions, they are called linear Diophantine equations. In this post, we discuss how to work with linear Diophantine equations in two unknowns. Specifically we show, given such an equation, how to tell if it has solutions and if it does have solutions, how to describe the complete solution set.

$1638x+357y=819$

$255x - 2261y = 1003$

$78x + 195y=45$

$374x+285y=49$

$21x+10y+25z=26$

$22x_1+15x_2+91x_3+437x_4=255$

As indicated above, we are only interested in integer solutions to the equation $ax+by=c$. So by a solution to $ax+by=c$, we mean a pair of integers $(x,y)$ that satisfies the equation.

Solving linear Diophantine equations is a topic that is an extension of the discussion on Euclidean algorithm and the extended Euclidean algorithm in this previous post.

Here’s the thought process. To solve the linear Diophantine equation $ax+by=c$, where $a$, $b$ and $c$ are integers, the first step is to find the greatest common divisor of $a$ and $b$, using Euclidean algorithm. We use the notation $\text{GCD}(a,b)$ to denote the greatest common divisor. Once we know $\text{GCD}(a,b)$, we would know whether the equation $ax+by=c$ has solutions. If it does have solutions, the same algorithm that derives the GCD will generate a particular solution of the equation (this is the extended Euclidean algorithm). From the particular solution, we can describe completely the solution set of the equation $ax+by=c$. In the next section, we discuss this thought process in greater details.

___________________________________________________________________________________________________________________

How to Find Solutions

We demonstrate the method using the linear Diophantine equation $1638x+357y=819$, the first one in the above list, proving any necessary lemma and theorem along the way. We work our way to Theorem 3 below, which gives a way to describe the complete solution set of any linear Diophantine equation (if it has one solution).

Let $d=\text{GCD}(a,b)$. The equation $ax+by=d$ always has a solution. In fact this statement is called the extended Euclidean algorithm. The solution can be obtained by working backward from the Euclidean algorithm (when we use it to obtain the GCD).

For example, $\text{GCD}(1638,357)=21$. We can trace back the steps in finding the GCD to see that

$1638 \cdot (-5)+357 \cdot 23=21$.

Thus the pair $x=-5$ and $y=23$ is a solution to the equation $1638x+357y=21$. Based on this development, we can see that $1638x+357y=c$ always has a solution as long as $c$ is a multiple of $21$. For example, the equation $1638x+357y=819$ has solutions since we have the following:

$1638 \cdot (-5 \cdot 39)+357 \cdot (23 \cdot 39)=21 \cdot 39=819$.

Thus the pair $x=-195$ and $y=897$ is a solution to the equation $1638x+357y=819$, which is the first linear Diophantine equation listed at the beginning of the post. We summarize this discussion in the following lemma.

Lemma 1

Let $d=\text{GCD}(a,b)$. The linear Diophantine equation $ax+by=c$ has a solution if and only if $d \ \lvert \ c$.

The notation $d \ \lvert \ c$ means that $c$ is divisible by $d$.

Proof of Lemma 1
The above discussion essentially shows the direction $\Longleftarrow$. The extended Euclidean algorithm indicates that $ax+by=d$ has a solution $x=x_0$ and $y=y_0$. If $c=d \cdot k$ for some integer $k$, then $a(x_0 \cdot k)+b(y_0 \cdot k)=d \cdot k$ indicates that the pair $x=x_0 \cdot k$ and $y=y_0 \cdot k$ is a solution to $ax+by=c$.

The direction $\Longrightarrow$ follows from the observation that $d=\text{GCD}(a,b)$ always divides the left-hand side of $ax+by=c$. Thus $d$ must divide the right-hand side as well unless the equation has no solution. $\blacksquare$

It turns out that if we can find one solution to a linear Diophantine equation, we can find infinitely many solutions.

Lemma 2

If the pair $x=x_0$ and $y=y_0$ is a solution to $ax+by=c$, then so is the following number pair

$x=x_0+b \cdot k$ and $y=y_0-a \cdot k$

where $k$ is any integer.

We can prove Lemma 2 by plugging the new solutions into the equation $ax+by=c$. We can also observe that if we increase $x$ by the value of $b$, we increase the left-hand side of the equation by $a \cdot b$. On the other hand, if we decrease $y$ by the amount $b$, we decrease the left-hand side of the equation by $b \cdot a$. The net effect is that the left-hand side of the equation remains unchanged.

Using Lemma 2, the following describes infinitely many solutions of the equation $1638x+357y=819$.

$x=-195+357k$ and $y=897-1638k$ for all integers $k$

But the above solution set is not complete. For example, the number pair $x=-178$ and $y=819$ is also a solution to the equation $1638x+357y=819$, but is not listed above. The following theorem will give the complete solution set.

Theorem 3

Let $d=\text{GCD}(a,b)$. If the pair $x=x_0$ and $y=y_0$ is a solution to $ax+by=c$, then the complete solution set of the equation consists of all the integer pairs $(x,y)$ such that

$\displaystyle x=x_0+\frac{b}{d} \cdot k$

$\displaystyle y=y_0-\frac{a}{d} \cdot k$

where $k$ is any integer.

Proof of Theorem 3

Suppose that the pair $x=x_0$ and $y=y_0$ is a solution to $ax+by=c$. Two points to show. One is that any number pair of the above form is a solution. The other is that any solution is of the above form. To see the first, note that

$\displaystyle a(x_0+\frac{b}{d} \cdot k)+b(y_0-\frac{a}{d} \cdot k)=ax_0+by_0=c$

To see the second point, suppose that the number pair $x=x_1$ and $y=y_1$ is a solution to the equation $ax+by=c$. We have the following.

$ax_0+by_0=c$

$ax_1+by_1=c$

Rearranging and dividing by $d$, we have the following.

$a(x_1-x_0)=b(y_0-y_1)$

$\displaystyle \frac{a}{d}(x_1-x_0)=\frac{b}{d}(y_0-y_1) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

Note that the two fractions in the last equation are integers since $d$ is the greatest common divisor of $a$ and $b$. Furthermore $\displaystyle \text{GCD} \biggl(\frac{a}{d},\frac{b}{d}\biggr)=1$. Note that after canceling out all the common prime factors of two numbers, the resulting two numbers should be relatively prime.

Based on equation (1) above, the number $\displaystyle \frac{b}{d}$ divides $\displaystyle \frac{a}{d}(x_1-x_0)$. Because $\displaystyle \text{GCD} \biggl(\frac{a}{d},\frac{b}{d}\biggr)=1$, the number $\displaystyle \frac{b}{d}$ cannot divide $\displaystyle \frac{a}{d}$. So the number $\displaystyle \frac{b}{d}$ must divide $\displaystyle x_1-x_0$. So for some integer $k$, we have:

$\displaystyle x_1-x_0=\frac{b}{d} \cdot k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

Plug $\displaystyle \frac{b}{d} \cdot k$ into (1), we have $\displaystyle \frac{a}{d} \cdot \frac{b}{d} \cdot k=\frac{b}{d}(y_0-y_1)$. This leads to the following.

$\displaystyle y_0-y_1=\frac{a}{d} \cdot k \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$

Equations (2) and (3) show that the solution $x=x_1$ and $y=y_1$ is of the form given in the theorem. $\blacksquare$

Based on Theorem 3, the complete solution set to the equation $1638x+357y=819$ is the following:

$\displaystyle x=-195+\frac{357}{21} \cdot k=-195+17k$

$\displaystyle y=897-\frac{1638}{21} \cdot k=897-78k$

where $k$ is any integer.

___________________________________________________________________________________________________________________

Recap

A linear Diophantine equation $ax+by=c$ is solvable if and only if $d \ \lvert \ c$ where $d=\text{GCD}(a,b)$.

If a linear Diophantine equation $ax+by=c$ is solvable, solving it involves two steps.

Step 1
We first find a particular solution. We can find one by trial and error if the numbers are not too large. Otherwise, we can apply the extended Euclidean algorithm. Note that if we use the Euclidean algorithm to find $d=\text{GCD}(a,b)$, we can just work backward in the Euclidean algorithm to find a solution to the equation $ax+by=d$, which in terms leads to a solution to $ax+by=c$.

Step 2
Theorem 3 provides a way to desribe the complete solution set of the linear Diophantine equation $ax+by=c$ based on the particular solution that is found in Step 1.

___________________________________________________________________________________________________________________

More Examples

To solve $255x - 2261y = 1003$, we need to find the GCD of $255$ and $2261$ (the negative sign of $2261$ can be dropped). We use the Euclidean algorithm.

$2261=8 \cdot 255+221$

$255=1 \cdot 221+34$

$221=6 \cdot 34+17$

$34=2 \cdot 17+0$

The GCD is $17$, which divides $1003$. So the equation has solutions. We need to find a specific solution. First we work backward from the above divisions to find a solution to $255x - 2261y = 17$. Then we multiply that solution by $59$. Working backward, we get:

$255(-62)-2261(-7)=17$

So the number pair $x=-62$ and $y=-7$ is a solution of $255x - 2261y = 17$. Thus the number pair $x=-62 \cdot 59=-3658$ and $y=-7 \cdot 59=-413$ is a solution of $255x - 2261y = 1003$. Thus the following completely describes the solution set of $85x - 68y = 51$.

$\displaystyle x=-3658-\frac{2261}{17} \cdot k=-3658-133k$

$\displaystyle y=-413-\frac{255}{17} \cdot k=-413-15k$

________________________________

To solve $78x+195y=45$, note that the GCD of $78$ and $195$ is $39$, which does not divide $45$. Thus the equation has no solutions.

________________________________

To solve $374x+285y=49$, first find the GCD of $374$ and $285$. We apply the Euclidean algorithm.

$374=1 \cdot 285+89$

$285=3 \cdot 89+18$

$89=4 \cdot 18+17$

$18=1 \cdot 17+1$

$17=17 \cdot 1+0$

Thus the GCD is 1. So the equation has solutions. To get one specific solution, we work backward from the above divisions and obtain:

$374(-16)+285(21)=1$

Thus $x=-16 \cdot 49=-784$ and $y=21 \cdot 49=1029$ is a specific solution to $374x+285y=49$. The complete solution set is described by:

$x=-784+285k$

$y=1029-374k$

for any integer $k$.

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

# Proving Fermat’s Little Theorem

In working with the notion of congruence modulo $m$ where $m$ is a positive integer, one important calculation is finding the powers of a number $a$, i.e, the calculation $a^n \equiv \ \text{mod} \ m$. In one particular situation the calculation of interest is to identify the power $n$ such that $a^n \equiv 1 \ \text{mod} \ m$. One elementary tool that can shed some light on this situation is the Fermat’s little theorem. This post is a self contained proof of this theorem.

After proving the theorem, we examine variations in the statements of the Fermat’s little theorem. There are some subtle differences among the variations. In one version of the Fermat’s little theorem (Theorem 4a below), the converse is not true as witnessed by the Carmichael numbers. In another version (theorem 4b below), the converse is true and gives a slightly better primality test (see Theorem 5 below) than the typical statement of the Fermat’s little theorem.

___________________________________________________________________________________________________________________

Example

Before discussing Fermat’s theorem and its proof, let’s look at an example. Let $m=11$, which is a prime number. Calculate the powers of $a$ modulo $m=11$ for all $a$ where $1 \le a \le m-1$. Our goal is to look for $a^n \equiv 1 \ \text{mod} \ 11$.

First of all, if the goal is $a^n \equiv 1 \ \text{mod} \ 11$, then $a$ cannot be $11$ or a multiple of $11$. Note that if $a$ is a multiple of $11$, then $a^n \equiv 0 \ (\text{mod} \ 11)$ for any positive integer $n$. So we only need to be concerned with numbers $a$ that are not multiples of $m=11$, i.e., numbers $a$ that are not divisible by $m=11$.

Any number greater than $11$ and is not divisible by $11$ is congruent modulo eleven to one integer $r$ in the range $1 \le r \le 10$. So we only need to calculate $a^n$ modulo $11$ for $1 \le a \le 10$. The following table displays the results of $a^n$ modulo $m=11$.

$\displaystyle \begin{bmatrix} a^1&a^2&a^3&a^4&a^5&a^6&a^7&a^8&a^9&a^{10} \\\text{ }&\text{ }&\text{ } \\ 1&1&1&1&1&1&1&1&1&1 \\ 2&4&8&5&10&9&7&3&6&1 \\ 3&9&5&4&1&3&9&5&4&1 \\ 4&5&9&3&1&4&5&9&3&1 \\ 5&3&4&9&1&5&3&4&9&1 \\ 6&3&7&9&10&5&8&4&2&1 \\ 7&5&2&3&10&4&6&9&8&1 \\ 8&9&6&4&10&3&2&5&7&1 \\ 9&4&3&5&1&9&4&3&5&1 \\ 10&1&10&1&10&1&10&1&10&1 \end{bmatrix}$

The above table indicates that to get $a^n \equiv 1$, the power can stop at $10$, one less than the modulus. According to Fermat’s theorem, this is always the case as long as the modulus is a prime number and as long as the base $a$ is a number that is not divisible by the modulus.

___________________________________________________________________________________________________________________

Fermat’s Little Theorem

The following is a statement of the theorem.

Theorem 1 (Fermat’s Little Theorem)
If $m$ is a prime number, then $a^{m-1} \equiv 1 \ (\text{mod} \ m)$ for any integer $a$ with $\text{GCD}(a,m)=1$.

Note that $\text{GCD}(a,b)$ refers to the greatest common divisor of the integers $a$ and $b$. When $\text{GCD}(a,b)=1$, the integers $a$ and $b$ are said to be relatively prime. We also use the notation $a \ \lvert \ b$ to mean that the integer $a$ divides $b$ without leaving a remainder.

In the discussion at the end of the above example, the base $a$ is a number that is required to be not divisible by the modulus $m$. If the modulus $m$ is a prime number, $a$ is a number that is not divisible by the modulus $m$ is equivalent to the condition $\text{GCD}(a,m)=1$. See the section called Variations below.

We will present below a formal proof of the theorem. The following example will make the idea of the proof clear. Let $m=11$. Let $a=3$. Calculate the following $10$ numbers:

$a, 2a, 3a, 4a, 5a, 6a, 7a, 8a, 9a, 10a$

For each of the above numbers, find the least residue modulo $m=11$. The following shows the results.

\displaystyle \begin{aligned} \text{ }&1 \cdot 3 \equiv 3 \ \ (\text{mod} \ 11) \\&2 \cdot 3 \equiv 6 \ \ (\text{mod} \ 11) \\&3 \cdot 3 \equiv 9 \ \ (\text{mod} \ 11) \\&4 \cdot 3 \equiv 1 \ \ (\text{mod} \ 11) \\&5 \cdot 3 \equiv 4 \ \ (\text{mod} \ 11) \\&6 \cdot 3 \equiv 7 \ \ (\text{mod} \ 11) \\&7 \cdot 3 \equiv 10 \ \ (\text{mod} \ 11) \\&8 \cdot 3 \equiv 2 \ \ (\text{mod} \ 11) \\&9 \cdot 3 \equiv 5 \ \ (\text{mod} \ 11) \\&10 \cdot 3 \equiv 8 \ \ (\text{mod} \ 11) \end{aligned}

The above calculation shows that the least residues of $a, 2a, 3a, 4a, 5a, 6a, 7a, 8a, 9a, 10a$ are just an rearrangement of $1, 2, 3, 4, 5, 6, 7, 8, 9, 10$. So we have:

$a \cdot 2a \cdot 3a \cdot 4a \cdot 5a \cdot 6a \cdot 7a \cdot 8a \cdot 9a \cdot 10a \equiv 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 \ \ (\text{mod} \ 11)$

$a^{10} \ 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 \equiv 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 \ \ (\text{mod} \ 11)$

Because $10!$ (10 factorial) is relatively prime with $11$, we can cancel it out on both side of the congruence equation. Thus we have $a^{10} \equiv 1 \ (\text{mod} \ 11)$ for $a=3$.

The above example has all the elements of the proof that we will present below. The basic idea is that whenever $a$ and the modulus $m$ are relatively prime, taking the least residues of $a, 2a, 3a, \cdots, (m-1)a$ modulo $m$ produces the numbers $1,2,3,\cdots,m-1$ (possibly in a different order).

We have the following lemma.

Lemma 2
Let $m$ be a prime number. Let $a$ be a positive integer that is relatively prime with $m$, i.e., $\text{GCD}(a,m)=1$. Then calculating the least residues of the number $a, 2a, 3a, \cdots, (m-1)a$ modulo $m$ gives the numbers $1,2,3,\cdots,m-1$.

Proof of Lemma 2

Let $b_1,b_2,b_3,\cdots,b_{m-1}$ be the least residues of $a, 2a, 3a, \cdots, (m-1)a$ modulo $m$. That is, for each $j$, $b_j$ is the number with $0 \le b_j \le m-1$ such that $b_j \equiv j \cdot a \ (\text{mod} \ m)$. Our goal is to show that $b_1,b_2,b_3,\cdots,b_{m-1}$ are the numbers $1,2,3,\cdots,m-1$. To this end, we need to show that each $b_j$ satisfies $1 \le b_j \le m-1$ and that the numbers $b_j$ are distinct.

First of all, $b_j \ne 0$. Suppose $b_j=0$. Then $0 \equiv j \cdot a \ (\text{mod} \ m)$ and $m \lvert j \cdot a$. By Euclid’s lemma, either $m \ \lvert \ j$ or $m \ \lvert \ a$. Since $\text{GCD}(a,m)=1$, $m \not \lvert \ a$. So $m \ \lvert \ j$. But $j$ is a positive integer less than $m$. So we have a contradiction. Thus each $b_j$ satisfies $1 \le b_j \le m-1$.

Now we show the numbers $b_1,b_2,b_3,\cdots,b_{m-1}$ are distinct (the list has exactly $m-1$ numbers). To this end, we need to show that $b_i \ne b_j$ when $i \ne j$. Suppose we have $b_i=b_j$ and $i \ne j$. . Then $i \cdot a \equiv j \cdot a \ (\text{mod} \ m)$. Since $a$ and $m$ are relatively prime, there is a cancelation law that allows us to cancel out $a$ on both sides. Then we have $i \equiv j \ (\text{mod} \ m)$. This means that $m \ \lvert \ (i-j)$. Since $i$ and $j$ are positive integers less than the modulus $m$, for $m \ \lvert \ (i-j)$ to happen, $i$ must equals $j$, contradicting $i \ne j$. It follows that $b_1,b_2,b_3,\cdots,b_{m-1}$ are distinct.

Taking stock of what we have so far, we have shown that $\left\{b_1,b_2,b_3,\cdots,b_{m-1} \right\} \subset \left\{1,2,3,\cdots,m-1 \right\}$. Both sides of the set inclusion have $m-1$ distinct numbers. So both sides of the set inclusion must equal. $\blacksquare$

We now prove Fermat’s little theorem.

Proof of Theorem 1

Let $m$ be a prime number. Let $a$ be a positive integer such that $\text{GCD}(a,m)=1$. By Lemma 2, the least resides of $a, 2a, 3a, \cdots, (m-1)a$ modulo $m$ are the numbers $1,2,3,\cdots,m-1$. Thus we have the following congruence equations:

$a \cdot 2a \cdot 3a \cdots \cdot (m-1)a \equiv 1 \cdot 2 \cdot 3 \cdots \cdot (m-1) \ \ (\text{mod} \ m)$

$a^{m-1} \ 1 \cdot 2 \cdot 3 \cdots \cdot (m-1) \equiv 1 \cdot 2 \cdot 3 \cdots \cdot (m-1) \ \ (\text{mod} \ m)$

Just as in the earlier example, we can cancel out $(m-1)!$ on both sides of the last congruence equation. Thus we have $a^{m-1} \equiv 1 \ (\text{mod} \ m)$. $\blacksquare$

___________________________________________________________________________________________________________________

Variations

There are several ways to state the Fermat’s little theorem.

Theorem 3
If $m$ is a prime number, then $a^{m} \equiv a \ (\text{mod} \ m)$ for any integer $a$.

Theorem 3 is a version of the Fermat’s theorem that is sometimes stated instead of Theorem 1. It has the advantage of being valid for all integers $a$ without having the need to consider whether $a$ and the modulus $m$ are relatively prime. It is easy to see that Theorem 3 implies Theorem 1. On the other hand, Theorem 3 is a corollary of Theorem 1.

To see that Theorem 3 follows from Theorem 1, let $m$ be prime and $a$ be any integer. Suppose $a$ and the modulus $m$ are not relatively prime. Then they have a common divisor $d>1$. Since $m$ is prime, $d$ must be $m$. So $a$ is an integer multiple of $m$. Thus $m$ divides both $a$ and any power of $a$. We have $a^{n} \equiv a \ (\text{mod} \ m)$ for any integer $n$. In particular, $a^{m} \equiv a \ (\text{mod} \ m)$. The case that $a$ and the modulus $m$ are relatively prime follows from Theorem 1.

We now consider again the versions that deal with $a^{m-1} \equiv 1$. The following is a side-by-side comparison of Theorem 1 with another statement of the Fermat’s little theorem. Theorem 1 is re-labeled as Theorem 4a.

Theorem 4a (= Theorem 1)
If $m$ is a prime number, then $a^{m-1} \equiv 1 \ (\text{mod} \ m)$ for any integer $a$ with $\text{GCD}(a,m)=1$.

Theorem 4b
If $m$ is a prime number, then $a^{m-1} \equiv 1 \ (\text{mod} \ m)$ for any integer $a$ that is not divisible by $m$.

The equivalence of these two versions follows from the fact that for any prime number $m$, $\text{GCD}(a,m)=1$ if and only if $a$ is not divisible by $m$. It is straightforward to see that if $\text{GCD}(a,m)=1$, then $a$ is not divisible by $m$. For the converse to be true, $m$ must be a prime number.

Since any integer $a$ is congruent modulo $m$ to some $r$ with $0 \le r \le m-1$, the following version is also an equivalent statement of the Fermat’s little theorem.

Theorem 4c
If $m$ is a prime number, then $a^{m-1} \equiv 1 \ (\text{mod} \ m)$ for any integer $a$ such that $1 \le a \le m-1$.

___________________________________________________________________________________________________________________

The Converse

It is a natural question to ask whether the converse of the Fermat’s little theorem is true. In many sources, it is stated that the converse is not true. It turns out that the answer depends on the versions. The converse of Theorem 4a is not true, while the converse of Theorem 4b and the converse of Theorem 4c are true. Let’s compare the following statements about the positive integer $m$:

$a^{m-1} \equiv 1 \ (\text{mod} \ m)$ for any integer $a$ with $\text{GCD}(a,m)=1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

$a^{m-1} \equiv 1 \ (\text{mod} \ m)$ for any integer $a$ that is not divisible by $m \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

Statement (1) is the conclusion of Theorem 4a, while statement (2) is the conclusion of Theorem 4b.

The statement (2) is a stronger statement. Any positive integer $m$ that satisfies (2) would satisfy (1). This is because the set of all integers $a$ for which $\text{GCD}(a,m)=1$ is a subset of the set of all integers $a$ for which $a$ is not divisible by $m$.

However, statement (1) does not imply statement (2). Any composite positive integer $m$ that satisfies (1) is said to be a Carmichael number. Thus any Carmichael number would be an example showing that the converse of Theorem 4a is not true. There are infinitely many Carmichael numbers, the smallest of which is $561= 3 \cdot 11 \cdot 17$. See the blog post Introducing Carmichael numbers for a more detailed discussion.

Any positive integer $m$ satisfying statement (2) is a prime number. Thus the converse of Theorem 4b is true. We have the following theorem.

Theorem 5
Let $m$ be an integer with $m>1$. Then $m$ is a prime number if and only if statement (2) holds.

Proof of Theorem 5

The direction $\Longrightarrow$ is Theorem 4b. To show $\Longleftarrow$, we show the contrapositive, that is, if $m$ is not a prime number, then statement (2) does not hold, i.e., there is some $a$ not divisible by $m$ such that $a^{m-1} \not \equiv 1 \ (\text{mod} \ m)$.

Suppose $m$ is not prime. Then $m$ has a divisor $a$ where $1. We claim that $a^{m-1} \not \equiv 1 \ (\text{mod} \ m)$. By way of a contradiction, suppose $a^{m-1} \equiv 1 \ (\text{mod} \ m)$. Then $m \ \lvert \ (a^{m-1}-1)$. Since $a \ \lvert \ m$, we have $a \ \lvert \ (a^{m-1}-1)$. So $a^{m-1}-1=a \cdot j$ for some integer $j$. Now we have $a \cdot (a^{m-2}-j)=1$. This implies that $a$ divides $1$. This is impossible since $1. This establishes the direction $\Longleftarrow$. $\blacksquare$

As a Carmichael number, $561$ satisfies statement (1). However it would not satisfy statement (2). By the proof of Theorem 5, if $a$ is a prime factor of $561$, then $a^{560} \not \equiv 1 \ (\text{mod} \ 561)$. Note that $3^{560} \not \equiv 1 \ (\text{mod} \ 561)$ since $3$ is a divisor of $561$. In fact, $3^{560} \equiv 375 \ (\text{mod} \ 561)$ and $11^{560} \equiv 154 \ (\text{mod} \ 561)$. We also have $17^{560} \equiv 34 \ (\text{mod} \ 561)$. Thus statement (1) is a weaker statement.

Any statement for the Fermat’s little theorem can be used as a primality test (Theorems 4a, 4b or 4c). On the face of it, Theorem 5 seems like an improvement over Theorem 4a, 4b or 4c since Theorem 5 can go both directions. However, using it to show that $m$ is prime would require checking $a^{m-1} \equiv 1 \ (\text{mod} \ m)$ for all $a$ with $1 < a \le m-1$. If $m$ has hundreds of digits, this would be a monumental undertaking! Thus this primality test has its limitation both in terms of practical considerations and the possibility of producing false positives.

__________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

# The Fundamental Theorem of Arithmetic

This post discusses and proves the fundamental theorem of arithmetic.

Finding the prime factors of a large integer is no easy feat. For example, the ninth Fermat number $F_9=2^{2^9}+1$ has 155 digits and has the following three prime factors:

$a=\text{2,424,833}$

$b=\text{7,455,602,825,647,884,208,337,395,736,200,454,918,783,366,342,657}$

\displaystyle \begin{aligned} c=&\text{ 741,640,062,627,530,801,524,787,141,901,937,474,059,940,781,097,519} \\&\text{ 023,905,821,316,144,415,759,504,705,008,092,818,711,693,940,737} \end{aligned}

These prime factors have 9 digits, 49 digits and 99 digits, respectively. They were published in 1993 after lengthy calculations involving approximately 700 workstations and a supercomputer using a number field sieve algorithm (see [1]). If the project were to be done today, it could certainly be done much faster and more efficiently with the current state of the art in supercomputing. However, the project will still be no trivial feat.

The following 617-digit integer is a product of two prime numbers and has yet to be factored by anyone (or any computer or any sets of computers). According RSA Laboratories, barring fundamental algorithmic or computing advances, the above number or other similarly sized number is expected to stay unfactored in the decades to come. For more background about this large number, see see RSA challenge number and RSA factoring challenge.

25195908475657893494027183240048398571429282126204
03202777713783604366202070759555626401852588078440
69182906412495150821892985591491761845028084891200
72844992687392807287776735971418347270261896375014
97182469116507761337985909570009733045974880842840
17974291006424586918171951187461215151726546322822
16869987549182422433637259085141865462043576798423
38718477444792073993423658482382428119816381501067
48104516603773060562016196762561338441436038339044
14952634432190114657544454178424020924616515723350
77870774981712577246796292638635637328991215483143
81678998850404453640235273819513786365643912120103
97122822120720357

Though the implementation of prime factorization may be difficult or even impossible for large numbers, the fundamental theorem of arithmetic guarantees that any positive integer can be expressed uniquely as a product of prime numbers. The fundamental theorem of arithmetic is an essential theorem in number theory. In this post, we present of proof of this fundamental theorem.

___________________________________________________________________________________________________________________

The Fundamental Theorem of Arithmetic

The theorem has two parts – the existence and the uniqueness of the prime factorization. The existence part is relatively easy. We first prove the existence part. We use Euclid’s lemma to prove the uniqueness part.

Lemma 1

Any integer $n>1$ has a prime divisor.

Proof

Let $n$ be an integer with $n>1$. If $n$ is prime, then it has a prime divisor, namely $n$. So assume $n$ is not prime. Then $n=h \cdot k$ for some positive integers $h$ and $k$ smaller than $n$.

Now consider the set $D$ of all positive integer divisors of $n$. The set $D$ is nonempty since $h$ and $k$ belong to this set. The set $D$ is also a finite set since an integer can only have finitely many integer divisors. Every finite set of real numbers has a smallest element. Let $p$ be the least element of $D$.

The $p$ must be a prime number. If not, $p$ would have a positive divisor $q$ that is smaller than $p$. Then $q$ is also a positive divisor of $n$, contradicting that $p$ is the least element of $D$. $\blacksquare$

Lemma 2

Any integer $n>1$ is a product of prime numbers.

Proof

We prove by induction. The lemma is certainly true for $n=2$. Suppose the lemma is true for all positive integers $k$ where $k.

If $n$ is prime, then we are done. Assume $n$ is not prime. Then $n=h \cdot k$ for some positive integers $h$ and $k$ smaller than $n$. By induction hypothesis, both $h$ and $k$ are product of prime numbers. We can conclude that $n$ is also a product of prime numbers. $\blacksquare$

Euclid’s Lemma

If $p$ is a prime number and $p \ \lvert (a \cdot b)$, then $p \ \lvert \ a$ or $p \ \lvert \ b$.

Proof of Euclid’s Lemma is found in this post. As a corollary of Euclid’s Lemma, we have the following lemma.

Lemma 3

If $p$ is a prime number and $p \ \lvert (a_1 \cdot a_2 \cdots a_n)$, then $p \ \lvert \ a_i$ for some $i$.

Proof

We prove by induction. The case for $n=2$ is the Euclid’s Lemma. Assume that the lemma is true for $n$ where $n \ge 2$. Suppose that $p \ \lvert (a_1 \cdot a_2 \cdots a_n \cdot a_{n+1})$. By Euclid’s lemma, we have $p \ \lvert (a_1 \cdot a_2 \cdots a_n)$ or $p \ \lvert \ a_{n+1}$. In the first case, the induction hypothesis tells us that $p \ \lvert \ a_i$ for some $i$ with $1 \le i \le n$. In the second case $p \ \lvert \ a_{n+1}$. The two cases together tell us that $p \ \lvert \ a_i$ for some $i$ with $1 \le i \le n+1$.

Since the validity of the lemma for $n$ implies the validity of the lemma for $n+1$ and since the lemma is true for $n=2$, we now know that the lemma is true for all integers $n>1$. This establishes the lemma. $\blacksquare$

Fundamental Theorem of Arithmetic

Any interger $n>1$ can be expressed uniquely as a product of prime numbers.

Proof

Let $n$ be an integer with $n>1$. The existence of the prime factors of $n$ is established by Lemma 2. We now show there is only one prime factorization for $n$. We would like to point out that order of the prime factors is not important. For example, we consider $2 \times 2 \times 3 \times 11$ and $11 \times 3 \times 2 \times 2$ as the same factorization for the integer $132$.

Suppose that $n=p_1 \cdot p_2 \cdots p_h$ and $n=q_1 \cdot q_2 \cdots q_k$ are prime factorizations of the integer $n$. We show that each $p_i$ is identical to some $q_j$ and each $q_s$ is identical to some $p_t$. This implies that the prime numbers $p_1,p_2,\cdots,p_h$ are simply a rearrangement of $q_1,q_2,\cdots,q_k$ such that the only difference for the two factorizations is in the order of the factors.

Note that $p_1 \cdot (p_2 \cdots p_h)=q_1 \cdot q_2 \cdots q_k$. Thus $p_1$ divides $q_1 \cdot q_2 \cdots q_k$, or we write $p_1 \ \lvert \ q_1 \cdot q_2 \cdots q_k$. By Lemma 3, $p_1 \ \lvert \ q_j$ for some $j$. Since they are prime, $p_1=q_j$. Then cancel out $p_1$ on both side of the equation, we have

$p_2 \cdot (p_3 \cdots p_h)=q_1 \cdot q_2 \cdots q_{j-1} \cdot q_{j+1} \cdots q_k$

Note that $p_2$ divides the right-hand side of the above equation. By Lemma 3, $p_2 \ \lvert \ q_w$ for some $w$. Continue in this same manner, we see that each $p$ is identical to some $q$. Furthermore, $h \le k$. Otherwise, there would be some $p_i$ left after we cancel out all the $q_j$, leading to the situation that the product of several prime numbers is equal to one.

By interchanging $p$ with $q$, the same argument will also show that each $q$ is identical to some $p$. Furthermore, $k \le h$. Thus we have $h=k$ and that the two factorizations are really just rearrangement of each other. $\blacksquare$

Comment

From the fundamental theorem of arithmetic, it follows that any positive integer greater than one can be expressed uniquely in the following way:

$p_1^{e_1} \cdot p_2^{e_2} \cdot p_3^{e_3} \cdots p_m^{e_m}$

where $m$ is a positive integer and each $e_i \ge 1$. Such representation of an integer is called a prime-power decomposition. For example, $7056=2^4 \cdot 3^2 \cdot 7^2$.

___________________________________________________________________________________________________________________

Reference

1. Lenstra, A. K., Lenstra, H. W., Manasse, M. S., Pollard, J. M. The Factorization of the Ninth Fermat Number, Mathematiics of Computation, Volume 61, Number 203, July 1993, Pages 319-349.

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$

# Euclid’s Lemma

This post presents a proof of a lemma that is called Euclid’s lemma, which is one of the fundamental properties of prime numbers. Euclid’s lemma is the statement that if a prime number divides a product of two integers, it must divide one of the factors.

This post is also part of the series of posts leading up to the fundamental theorem of arithmetic.

We first state all the tools that we need. The notation $a \ \lvert \ b$ refers to the condition that $a$ divides $b$. The notation $\text{GCD}(a,b)$ refers to the greatest common divisor (GCD) of $a$ and $b$.

___________________________________________________________________________________________________________________

Extended Euclidean Algorithm

Let $a$ and $b$ be integers. Let $d$ be the greatest common divisor of $a$ and $b$. Then there exist integers $x$ and $y$ such that $ax+by=d$.

The extended Euclidean algorithm is discussed in this post.

___________________________________________________________________________________________________________________

Lemma 1

If $d \ \lvert \ a \cdot b$ and $\text{GCD}(d,a)=1$, then $d \ \lvert \ b$.

Proof of Lemma 1

Suppose that $d \ \lvert \ a \cdot b$ and $\text{GCD}(d,a)=1$. According to the extended Euclidean algorithm, for some integers $x$ and $y$, we have $ax+dy=1$. Multiplying both sides by $b$, we have:

$abx+dby=b$

Since $d$ divides each term in the left-hand side of this equation, $d \ \lvert \ b$. $\blacksquare$

___________________________________________________________________________________________________________________

Euclid’s Lemma

If $p$ is a prime number and $p \ \lvert (a \cdot b)$, then $p \ \lvert \ a$ or $p \ \lvert \ b$.

Proof

If $p \ \lvert \ a$, then we are done. So assume $p \not \lvert \ a$, which implies that $\text{GCD}(p,a)=1$. If $\text{GCD}(p,a)>1$, $\text{GCD}(p,a)=p$, which implies that $p \ \lvert \ a$. Note that the only positive divisors of $p$ are $1$ and $p$. By Lemma 1, $p \ \lvert \ b$. $\blacksquare$

Comment

We would like to point out that the assumption that $p$ is prime is essential in Euclid’s lemma. Note that $8 \ \lvert \ (4 \cdot 4)$ and $8 \not \lvert \ 4$.

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$