# Another look at the fundamental theorem of arithmetic

This is the first post of a series of blog posts on the Chinese remainder theorem, often abbreviated CRT. In this post, we take another look at the fundamental theorem of arithmetic. This post is background for the next post, which will show that CRT can be built step by step from the fundamental theorem of arithmetic.

Links to the other posts in the series:
second post, third post, fourth post.

Every integer can be factored into a product of primes in essentially one way. This fact is called the fundamental theorem of arithmetic. For example, the number 84 is 2 x 2 x 3 x 7. The ordering of the primes is not important here since, for example, 2 x 2 x 3 x 7 is the same as 3 x 2 x 7 x 2. The example of 84 seems to suggest that the fundamental theorem of arithmetic is simply an exercise at the elementary school. In general, factoring a number is a very hard problem. For integers with hundreds or thousands of digits, finding the factors may take more seconds than the number of atoms in the universe! The fundamental theorem of arithmetic guarantees that such factorization exists for any integer, large or small. Because of this, the prime numbers are the building blocks of the integers (the atoms of arithmetic).

What is the importance of knowing that every integer can be factored into prime numbers in a unique way? A short answer is that the fundamental theorem of arithmetic is a foundation result. A vast array of mathematical structures are built on this foundation. The fundamental theorem of arithmetic is the beginning point of many mathematical stories. In this and subsequent posts, we highlight one such example. We show that the Chinese remainder theorem follows from the fundamental theorem of arithmetic. CRT combines beauty and utility. Even though CRT has been known for at least 1,000 years, it continues to present new applications in many areas, e.g. in coding theory, cryptography and the theory of computing. Surprisingly, the proof of CRT is quite simple. CRT follows from a lemma that is equivalent to the fundamental theorem of arithmetic. As a result, the discussion in this and the subsequent posts is a clear demonstration of the power of the fundamental theorem of arithmetic.

In this post, we discuss the fundamental theorem of arithmetic. In the next posts, we discuss CRT.

____________________________________________________________________________

The lemma

The starting point is the following lemma.

Lemma A
Let $a$, $b$ and $d>0$ be integers. Suppose that $\text{GCD}(a,d)=1$, i.e. the greatest common divisor of $a$ and $d$ is 1. If $d \lvert (a \cdot b)$, then $d \lvert b$.

Proof
Suppose that $\text{GCD}(a,d)=1$. By the extended Euclidean algorithm, the linear diophantine equation $ax+dy=1$ is solvable in integers. Let $x$ and $y$ be integers that satisfy this equation. Multiply this equation by $b$ to obtain $abx+dby=b$. Since $d \lvert (a \cdot b)$, $d$ divides both terms on the left hand side of the last equation. Thus $d \lvert b$. $\square$

Lemma A is a simple statement. The proof is also simple, simply using the extended Euclidean algorithm, which is the Euclidean algorithm working backward. the Euclidean alogorithm consists, at heart, of a series of divisions to derive the greatest common divisor. As discussed below, the simple Lemma A leads to the fundamental theorem of arithmetic and Lemma A can also be derived from the fundamental theorem of arithmetic.

____________________________________________________________________________

The fundamental theorem of arithmetic

The fundamental theorem of arithmetic states that any positive integer greater than 1 can be expressed as a product of primes and that the factorization is unique. The theorem is proved in this previous post. Here, we show that it is equivalent to Lemma A.

Theorem B
The following conditions are equivalent:

1. The statement of Lemma A.
2. (Euclid’s lemma) If $p$ is a prime number and $p \lvert (a \cdot b)$, then either $p \lvert a$ or $p \lvert b$.
3. (Fundamental Theorem of Arithmetic) Every positive integer $n>1$ can be written as a product of prime numbers and that this product (called a factorization) is unique.

Condition 2 is usually referred to as the Euclid’s lemma. Condition 3 is, of course, a statement of the fundamental theorem of arithmetic. The story we would like to tell is that Lemma A is equivalent to the fundamental theorem of arithmetic. Thus any consequence of Lemma A is also a consequence of the fundamental theorem of arithmetic.

The proof of $1 \rightarrow 2 \rightarrow 3$ is done in this previous post. We also like to point out one additional argument is needed to establish the equivalence of the three conditions. The proof to establish the fundamental theorem of arithmetic in the previous post uses an induction argument to show that every integer is a product of prime numbers. So condition 2 plus the induction argument establish condition 3. The role of condition 2 is to establish the uniqueness of the product of primes. We only need to show $3 \rightarrow 1$.

Proof
$3 \rightarrow 1$
Suppose that $a$ and $d$ have no prime factors in common and that $d \lvert (a \cdot b)$. So we have $a \cdot b=d \cdot m$ for some integer $m$. By condition 3, we can express $a$ and $d$ as a product of primes as follows:

$\displaystyle p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_t^{\alpha_t} \times b=q_1^{\delta_1} \cdot q_2^{\delta_2} \cdots q_r^{\delta_r} \times m$

The numbers $p_i$ are the prime factors of $a$ and the numbers $q_i$ are the prime factors of $d$. The exponents $\alpha_i$ and $\delta_j$ are positive integers. Note that $p_i \ne q_j$ for any $i$ and $j$. Each $q_i^{\delta_i}$ must appear in the prime factorization of the left-hand side. Since $q_i^{\delta_i}$ cannot appear in the factorization of $a$, it must be in the factorization of $b$. $\square$

The loop $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$ shows the equivalence of the three statements. From a logical standpoint, any one of these statements is the fundamental theorem of arithmetic. As a demonstration of the power of the fundamental theorem of arithmetic, the next post shows that the Chinese remainder theorem is derived using Lemma A.

____________________________________________________________________________
$\copyright \ 2015 \text{ by Dan Ma}$

This post is an introductory discussion on the congruence equations of the form $x^2 \equiv a \ (\text{mod} \ p)$ where the modulus $p$ is an odd prime and the number $a$ is relatively prime to $p$. A discussion on the related notion of quadratic residues is found here. Specific algorithms for solving quadratic congruence eqautions with odd prime moduli are discussed in this subsequent post.

____________________________________________________________________________

Simple Example

We start off with a simple example. Calculate $x^2$ modulo $m=11$ for $x=0,1,2,\cdots,10$.

$0^2 \equiv 0 \ (\text{mod} \ 11)$

$1^2 \equiv 1 \ (\text{mod} \ 11)$

$2^2 \equiv 4 \ (\text{mod} \ 11)$

$3^2 \equiv 9 \ (\text{mod} \ 11)$

$4^2 \equiv 5 \ (\text{mod} \ 11)$

$5^2 \equiv 3 \ (\text{mod} \ 11)$

$6^2 \equiv 3 \ (\text{mod} \ 11)$

$7^2 \equiv 5 \ (\text{mod} \ 11)$

$8^2 \equiv 9 \ (\text{mod} \ 11)$

$9^2 \equiv 4 \ (\text{mod} \ 11)$

$10^2 \equiv 1 \ (\text{mod} \ 11)$

The above calculation shows that the values of $x^2$ modulo $m=11$ can only be $1,3,4,5,9$. So equations such as $x^2 \equiv a \ (\text{mod} \ 11)$ for $a=1,3,4,5,9$ have solutions. For example, the solutions for the equation $x^2 \equiv 5 \ (\text{mod} \ 11)$ are $x=4$ and $x=7$.

On the other hand, the equations $x^2 \equiv b \ (\text{mod} \ 11)$ for $b=2,6,7,8,10$ have no solutions.

Also note that whenever $a \ne 0$ and the equation $x^2 \equiv a \ (\text{mod} \ 11)$ has a solution, the solutions come in pairs.

____________________________________________________________________________

Let $m$ be an odd prime number. Let $a$ be an integer that is not divisible by $p$ (equivalently relatively prime to $p$). The object of interest here is the quadratic congruence equation $x^2 \equiv a \ (\text{mod} \ p)$. It turns out that each such equation has exactly two solutions whenever the number $a$ and the modulus $p$ are relatively prime (as demonstrated in the above simple example). The following lemma and corollary confirm what we see in the above example.

Lemma 1

Let $p$ be an odd prime number. Let $a$ be an integer that is not divisible by $p$. Then the equation

$x^2 \equiv a \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

has no solutions or exactly two solutions.

Proof of Lemma 1
If equation (1) has no solutions, then we are done. Suppose it has at least one solution, say $x=r$. We have $r^2 \equiv a \ (\text{mod} \ p)$. It follows that $x=-r \equiv p-r \ (\text{mod} \ p)$ is a solution of equation (1) too.

We claim $x=r$ and $x=p-r$ are distinct modulo $p$. To see this, suppose $p-r \equiv r \ (\text{mod} \ p)$. Then $p \ \lvert \ (p-2r)$. Because $p$ is an odd prime, $p \not \lvert \ 2$. So $p \ \lvert \ r$. This implies that $p \ \lvert \ r^2$. Because $p \ \lvert \ (r^2-a)$, $p \ \lvert \ a$, contradicting the assumption that $p \not \lvert \ a$. Thus $p-r \not \equiv r \ (\text{mod} \ p)$, demonstrating that equation (1) has at least two solutions.

It remains to be shown that any solution of equation (1) must be congruent to one of $x=r$ and $x=p-r$. Suppose $t^2 \equiv a \ (\text{mod} \ p)$. Then $t^2 \equiv r^2 \ (\text{mod} \ p)$. It follows that $p \ \lvert \ (t-r)(t+r)$. Thus $p$ must divide one of the two factors (Euclid’s lemma). The case $p \ \lvert \ (t-r)$ implies $t \equiv r \ (\text{mod} \ p)$. The case $p \ \lvert \ (t+r)$ implies $t \equiv -r \ (\text{mod} \ p)$. $\blacksquare$

Corollary 2

Let $p$ be an odd prime number. The equation $x^2 \equiv a \ (\text{mod} \ p)$ has exactly two solutions for $\displaystyle \frac{p-1}{2}$ many numbers $a \in \left\{1,2,\cdots,p-1 \right\}$ and has no solutions for the other $\displaystyle \frac{p-1}{2}$ numbers $a \in \left\{1,2,\cdots,p-1 \right\}$.

Remark
For the even prime $p=2$, the equation $x^2 \equiv a \ (\text{mod} \ 2)$ is not an interesting one. For $x^2 \equiv 0 \ (\text{mod} \ 2)$, $x=0$ is the only solution. For $x^2 \equiv 1 \ (\text{mod} \ 2)$, $x=1$ is the only solution.

For composite moduli, the quadratic equation $x^2 \equiv a \ (\text{mod} \ m)$ can have more than two solutions. For example, $x^2 \equiv 1 \ (\text{mod} \ 8)$ has four solutions $x=1,3,5,7$.

For these reasons, we only work with odd prime moduli for quadratic congruences.

____________________________________________________________________________

General Case

What about the general case of the quadratic congruence equation of the following form?

$\alpha y^2+\beta y+\gamma \equiv 0 \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

Of course, we only consider the equations where $\alpha \not \equiv 0 \ (\text{mod} \ p)$ and $p$ is an odd prime. It turns out that equation (2) can be replaced by an equivalent congruence equation of the same form as equation (1) above. So the general case of equation (2) presents no new problem. We just convert equation (2) to its equivalence and solve it accordingly. We now discuss how this is done.

The coefficient $\alpha$, the coefficient of the $y^2$ term, has a multiplicative inverse modulo $p$. So multiplying equation (2) by $\alpha^{-1}$ gives the following equation.

$y^2+\alpha^{-1} \beta y+\alpha^{-1} \gamma \equiv 0 \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$

So we can now focus on solving equation (3), which has the same solutions as equation (2). Consider the coefficient of the $y$ term. If the coefficient $\alpha^{-1} \beta$ is even, we can complete the square and obtain an equivalent equation of the same form as equation (1). If the coefficient $\alpha^{-1} \beta$ is odd, then we can add $p$ to it and obtain an even coefficient. We can then proceed to complete the square as in the even case. We demonstrate with two examples.

Consider the equation $3 y^2+4y+1 \equiv 0 \ (\text{mod} \ 11)$. Since $4 \cdot 3 \equiv 1 \ (\text{mod} \ 11)$. The multiplicative inverse of $4$ is $3$. So we multiply $4$ across and obtain $y^2+16y+4 \equiv 0 \ (\text{mod} \ 11)$. The coefficient of the $y$ term is even. We complete the square as follows.

$y^2+16y+4 \equiv 0 \ (\text{mod} \ 11)$

$y^2+16y+64 \equiv 64-4 \ (\text{mod} \ 11)$

$(y+8)^2 \equiv 60 \ (\text{mod} \ 11)$

$(y+8)^2 \equiv 5 \ (\text{mod} \ 11)$

The last equation in the above derivation is of the form $x^2 \equiv 5 \ (\text{mod} \ 11)$ where the solutions are $x=4$ and $x=7$. Thus we have $y+8 \equiv 4 \ (\text{mod} \ 11)$ and $y+8 \equiv 7 \ (\text{mod} \ 11)$. These two congruences give $y \equiv 7 \ (\text{mod} \ 11)$ and $y \equiv 10 \ (\text{mod} \ 11)$.

For the odd case, consider the equation $5 y^2+y+8 \equiv 0 \ (\text{mod} \ 11)$. The multiplicative inverse of $5$ is $9$ as $5 \cdot 9 \equiv 1 \ (\text{mod} \ 11)$. After multiplying by the inverse, we obtain $y^2+9y+72 \equiv 0 \ (\text{mod} \ 11)$. We further reduce $72$ modulo $11$ to get $y^2+9y+6 \equiv 0 \ (\text{mod} \ 11)$. Note that the coefficient of the $y$ term is odd. So we add modulus to that coefficient to obtain the equation $y^2+20y+6 \equiv 0 \ (\text{mod} \ 11)$. We then proceed to complete the square as follows.

$y^2+20y+100 \equiv 100-6 \ (\text{mod} \ 11)$

$(y+10)^2 \equiv 94 \ (\text{mod} \ 11)$

$(y+10)^2 \equiv 6 \ (\text{mod} \ 11)$

The last equation in the above derivation is of the form $x^2 \equiv 6 \ (\text{mod} \ 11)$, which has no solutions (based on the simple example above). Thus the original equation $5 y^2+y+8 \equiv 0 \ (\text{mod} \ 11)$ has no solutions.

____________________________________________________________________________

Examples

To solve the quadratic congruence $x^2 \equiv a \ (\text{mod} \ p)$, one way is to compute the entire table of values for $x^2$ modulo $p$. For very small prime such as the simple example above, this approach is workable. For large primes, this requires a lot of computational resources.

To further illustrate the quadratic congruences, we work three examples with help from Euler’s Criterion and from using Excel to do some of the calculations.

According to Euler’s Criterion, the equation $x^2 \equiv a \ (\text{mod} \ p)$ has solutions if and only if $\displaystyle a^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$. Equivalently, the equation $x^2 \equiv a \ (\text{mod} \ p)$ has no solutions if and only if $\displaystyle a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$. So the solvability of the quadratic congruence equation can be translated as a modular exponentiation calculation.

The computation for $\displaystyle a^{\frac{p-1}{2}} \ (\text{mod} \ p)$ can be done directly using an online modular arithmetic calculator or using the fast-powering algorithm (discussed in the post Congruence Arithmetic and Fast Powering Algorithm). For a discussion and a proof of Euler’s Criterion, see the post Euler’s Criterion.

When Euler’s Criterion indicates there are solutions, how do we find the solutions? We demonstrate using the following examples.

Example 1
Solve $x^2 \equiv 5 \ (\text{mod} \ 61)$.

According to Euler’s Criterion, the equation $x^2 \equiv 5 \ (\text{mod} \ 61)$ has solutions since $5^{30} \equiv 1 \ (\text{mod} \ 61)$. To find the solutions, we keep adding the modulus to $a=5$ until we get a perfect square.

$\displaystyle x^2 \equiv 5 \equiv 5+61 \equiv 5+2(61) \equiv \cdots \equiv 5+20(61)=1225=35^2 \ (\text{mod} \ 61)$

So we have $x^2 \equiv 35^2 \ (\text{mod} \ 61)$, which gives $x=35$ and $x=-35$. The solutions are $x \equiv -35 \equiv 26 \ (\text{mod} \ 61)$ and $x \equiv 35 \ (\text{mod} \ 61)$.

Example 2
Solve $x^2 \equiv 899 \ (\text{mod} \ 50261)$.

Since $899^{25130} \equiv 1 \ (\text{mod} \ 50261)$, the equation has solutions. We then add the modulus repeatedly to $899$ until we get a perfect square (with the aid of an Excel spreadsheet).

$\displaystyle x^2 \equiv 899 \equiv 899+50261 \equiv 899+2(50261) \equiv \cdots \equiv 899+4297(50261)=215972416=14696^2 \ (\text{mod} \ 50261)$

So we have $x^2 \equiv 14696^2 \ (\text{mod} \ 50261)$, which gives $x=14696$ and $x=-14696$. The solutions are $x \equiv 14696 \ (\text{mod} \ 50261)$ and $x \equiv -14696 \equiv 35565 \ (\text{mod} \ 50261)$.

Example 3
Solve $x^2 \equiv 13961 \ (\text{mod} \ 50261)$.

Since $13961^{25130} \equiv -1 \ (\text{mod} \ 50261)$, the equation has no solutions according to Euler’s Criterion.

____________________________________________________________________________

$\copyright \ 2013 - 2015 \text{ by Dan Ma}$
Revised December 9, 2015

# Primitive roots of prime moduli

In this post we show that if $m$ is prime, then there exists a primitive root modulo $m$. It follows that there exist $\phi(m-1)$ primitive roots modulo $m$ where $\phi$ is Euler’s phi function.

For a basic discussion of the notion of primitive roots, see Defining Primitive Root. A basic discussion of the phi function is found in the post Euler’s phi function, part 1 and in the post Euler’s phi function, part 2.

In modular arithmetic, not all moduli have primitive roots. For example, for the modulus $m=8$, the least residues that are relatively prime are $a=1,3,5,7$. Thus $\phi(8)=4$. For each one of these values of $a$, $a^2 \equiv 1 \ (\text{mod} \ 8)$. Thus every one of them has order $2 < \phi(8)$. Thus there are no primitive roots modulo $m=8$. We prove the following results.

Theorem 1

Let $p$ be a prime number. Then there exists a primitive root modulo $p$.

$\text{ }$

Theorem 2

Let $p$ be a prime number. Then there are exactly $\phi(m-1)$ many primitive roots modulo $m$.

$\text{ }$

Theorem 1 is the main theorem in this post. Theorem 2 follows from Theorem 1 and from a result proved in a previous post. The previous result is that if there exists a primitive root modulo $m$ (not necessarily prime), then there exist exactly $\phi(\phi(m))$ many primitive roots modulo $m$ (see Theorem 6 and Corollary 7 in Defining Primitive Root). Since Theorem 1 provides the existence of a primitive root, Theorem 2 follows from Theorem 1 and from the previous result and from the fact that $\phi(p)=p-1$ for any prime number.

___________________________________________________________________________________________________________________

Proving the Main Theorem

Our proof of the existence of a primitive root of any prime modulus uses only elementary techniques. Most of the results we need are developed here in this post. The first result is proved in a previous post (see Theorem 4 in Defining Primitive Root).

Lemma 3

Let $a$ be an integer with $0 \le a \le m-1$ such that $a$ is relaively prime to the modulus $m$. Let $k$ be the order of $a$ modulo $m$. Then the following two conditions are equivalent for any positive integer $n$.

1. The congruence condition $a^n \equiv 1 \ (\text{mod} \ m)$ holds.
2. The number $k$ is a divisor of $n$.

The second result is that of polynomial congruence. Let $f(x)$ be a polynomial with integer coefficients. In the next lemma, we are interested in solving the polynomial congruence equation $f(x) \equiv 0 \ (\text{mod} \ m)$.

Lemma 4

Let $m$ be a prime number. Let $f(x)$ be a polynomial of degree $n$. Then the equation

$f(x) \equiv 0 \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

$\text{ }$

has at most $n$ solutions.

Proof of Lemma 4

Suppose $f(x)=a_n x^n +a_{n-1} x^{n-1} + \cdots+a_2 x^2+a_1 x + a_0$ where $a_n \not \equiv 0 \ (\text{mod} \ m)$. We prove the lemma by induction on the degree $n$.

Suppose $n=1$. We have $f(x)=a_1 x +a_0 \equiv 0 \ (\text{mod} \ m)$. Since $m$ is prime and $a_1 \not \equiv 0 \ (\text{mod} \ m)$, the coefficient $a_1$ must be relatively prime to $m$. Then the congruence equation $a_1 x +a_0 \equiv 0 \ (\text{mod} \ m)$ has exactly one solution. The number of solutions of a linear congruence is the same as the greatest common divisor of the coefficient of $x$ and the modulus $m$ (see Theorem 2 in the post Solving Linear Congruences).

Suppose the lemma is true for polynomials of degree $n-1$. Consider two cases – either equation (1) has no solution or equation (1) has a solution. If the first case is true, then the conclusion of the lemma is true.

Suppose the second case is true. Suppose $b$ is a solution to equation (1). It follows that $f(b) \equiv 0 \ (\text{mod} \ m)$ and that $b$ is a least residue modulo $m$.

Our next goal is to factor the polynomial $f(x)$ into a product of a first degree polynomial and a polynomial of degree $n-1$. To this end, note that $x-b$ is a factor of $x^w-b^w$ for $w=1,2,3,\cdots,n$. We have the following derivation

\displaystyle \begin{aligned} f(x)&\equiv f(x)-f(b) \\&\equiv a_n (x^n-b^n) +a_{n-1} (x^{n-1}-b^{n-1}) + \cdots+a_2 (x^2-b^2)+a_1 (x-b) \\&\equiv (x-b) \cdot h(x) \ (\text{mod} \ m) \end{aligned}

where $h(x)$ is a polynomial of degree $n-1$.

Whenever $f(x) \equiv 0 \ (\text{mod} \ m)$, we have $m \ \lvert \ (x-b) \cdot h(x)$. Using the fact that $m$ is prime and Euclid’s lemma, either $m \ \lvert \ (x-b)$ or $m \ \lvert \ h(x)$. In terms of congruence, either $x-b \equiv 0 \ (\text{mod} \ m)$ or $h(x) \equiv 0 \ (\text{mod} \ m)$. The first congruence has exactly one solution. By induction hypothesis, the second congruence has at most $n-1$ solutions. Together, equation (1) has at most $n$ solutions. $\blacksquare$

Lemma 5

Let $m$ be a prime number. If $d \ \lvert \ (p-1)$, then the congruence equation $x^d \equiv 1 \ (\text{mod} \ m)$ has exactly $d$ many solutions.

Proof of Lemma 5

Suppose $d \ \lvert \ (p-1)$. Fermat’s little theorem tells us that $x^{m-1}-1 \equiv 0 \ (\text{mod} \ m)$ has exactly $m-1$ solutions, namely $1,2,3,\cdots,m-1$. We can factor the polynomial $x^{m-1}-1$ as follows:

$g(x)=x^{m-1}-1=(x^d-1) \cdot (x^{m-1-d}+x^{m-1-2d}+x^{m-1-3d}+\cdots+x^{d}+1)$

Let $t(x)=(x^{m-1-d}+x^{m-1-2d}+x^{m-1-3d}+\cdots+x^{d}+1)$. Whenever $g(x) \equiv 0 \ (\text{mod} \ m)$, $m \ \lvert \ g(x)=x^{m-1}-1=(x^d-1) \cdot t(x)$. By Euclid’s lemma, $m \ \lvert \ (x^d-1)$ or $m \ \lvert \ t(x)$. In terms of congruence, $x^d \equiv 1 \ (\text{mod} \ m)$ or $t(x) \equiv 0 \ (\text{mod} \ m)$.

By Lemma 4, the congruence $t(x) \equiv 0 \ (\text{mod} \ m)$ has at most $m-1-d$ solutions. Since $x^{m-1}-1 \equiv 0 \ (\text{mod} \ m)$ has exactly $m-1$ solutions, the congruence equation $x^d \equiv 1 \ (\text{mod} \ m)$ has at least $d$ many solutions.

By Lemma 4, the congruence equation $x^d \equiv 1 \ (\text{mod} \ m)$ has at most $d$ solutions. Thus $x^d \equiv 1 \ (\text{mod} \ m)$ has exactly $d$ many solutions. $\blacksquare$

We need one more lemma before proving Theorem 1.

Lemma 6

Let $a$ and $b$ be integers with $0 \le a,b \le m-1$. Let $\alpha$ be the order of $a$ modulo $m$. Let $\beta$ be the order of $b$ modulo $m$.

Suppose that $\alpha$ and $\beta$ are relatively prime. Then $\alpha \cdot \beta$ is the order of $a \cdot b$ modulo $m$.

Proof of Lemma 6

Let $\gamma$ be the order of $a \cdot b$ modulo $m$. We show that $\gamma=\alpha \beta$. The following derivation shows that $\alpha \ \lvert \ \gamma$.

$1 \equiv 1^\beta \equiv ((ab)^\gamma)^\beta =(ab)^{\gamma \beta}=(a)^{\gamma \beta} (b)^{\gamma \beta}=(a)^{\gamma \beta} (b^{\gamma})^{\beta} \equiv a^{\gamma \beta} \ (\text{mod} \ m)$

Since $a^{\gamma \beta} \equiv 1 \ (\text{mod} \ m)$, we have $\alpha \ \lvert \ \gamma \beta$ (by Lemma 3). Since $\alpha$ and $\beta$ are relatively prime, $\alpha \ \lvert \ \gamma$. By a symmetrical argument, it can also be shown that $\beta \ \lvert \ \gamma$.

Since $\alpha \ \lvert \ \gamma$, we have $\gamma=\alpha \cdot t$ for some integer $t$. Since $\beta \ \lvert \alpha \cdot t$, it follows that $\beta \ \lvert t$ (Euclid’s lemma). So $t=\beta \cdot z$ for some integer $z$. Now $\gamma=\alpha \cdot \beta \cdot z$. This means that $\alpha \beta \ \lvert \ \gamma$.

On the other hand, we have $\gamma \ \lvert \alpha \beta$. This follows from the following derivation and from Lemma 3.

$(ab)^{\alpha \beta}=(a^\alpha)^\beta \cdot (b^\beta)^\alpha \equiv 1 \ (\text{mod} \ m)$

It follows that $\gamma= \alpha \beta$. $\blacksquare$

Remark
Lemma 6 indicates that the orders of two numbers are multiplicative as long as the two orders are relatively prime. As a corollary of Lemma 6, it follows that the order of a product of finitely many numbers (for the same modulus) is the product of the individual orders provided that the orders are pairwise relatively prime. This fact will be used in the proof of Theorem 1 below.

Proof of Theorem 1

We start off with a prime factorization of the number $p-1$.

$\displaystyle p-1=w_1^{e_1} \cdot w_2^{e_2} \cdot w_3^{e_3} \cdots w_n^{e_n}$

In the above factorization, the numbers $w_i$ are distinct prime numbers and the exponents $e_i \ge 1$.

For each $i$, it is clear that $w_i^{e_i} \ \lvert \ (p-1)$. By Lemma 5, the congruence equation

$\displaystyle x^{w_i^{e_i}} \equiv 1 \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

has exactly $w_i^{e_i}$ many solutions. Note that the $w_i^{e_i}$ many solutions are integers in the interval $0 \le x \le p-1$. Furthermore, the order modulo $p$ of each of these solutions to (2) is a divisor of $w_i^{e_i}$ (by Lemma 3).

In fact, from Lemma 3, we can say that for any integer $x$ in the interval $0 \le x \le p-1$, the number $x$ is a solution of equation (2) if and only if the order modulo $p$ of $x$ is a divisor of $w_i^{e_i}$. We have the following claim.

Claim
For each $i$, we claim that there exists at least one integer $a_i$ in the interval $0 \le x \le p-1$ such that the order of $a_i$ modulo $p$ is $w_i^{e_i}$.

To see the above claim, the congruence equation

$\displaystyle x^{w_i^{e_i-1}} \equiv 1 \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$

has exactly $w_i^{e_i-1}$ many solutions in the interval $0 \le x \le p-1$ (using Lemma 5). Furthermore, the order of each of the solutions of (3) is a divisor of $w_i^{e_i-1}$.

In fact, from Lemma 3, we can also say that for any integer $x$ in the interval $0 \le x \le p-1$, the number $x$ is a solution of equation (3) if and only if the order modulo $p$ of $x$ is a divisor of $w_i^{e_i-1}$.

Note that the solutions of (3) are also solutions of (2). This is clear since we know that divisors of $w_i^{e_i-1}$ are also divisors of $w_i^{e_i}$.

Thus there are $w_i^{e_i}-w_i^{e_i-1}$ many of the solutions to (2) that are not solutions to equation (3). Pick one such solution and call it $a_i$. Let $k$ be the order of $a_i$ modulo $p$. There are three possibilities for $k$:

$k \le w_i^{e_i-1} \ \ \ \ \ w_i^{e_i-1}

Since $a_i$ is a solution to (2), the number $k$ is a divisor of $w_i^{e_i}$. Note that there are no divisors of $w_i^{e_i}$ within the interval $w_i^{e_i-1} since $w_i$ is a prime number. So $w_i^{e_i-1} is not possible.

Since $a_i$ is not a solution to (3), the number $k$ is not a divisor of $w_i^{e_i-1}$. This means that $k \le w_i^{e_i-1}$ is not possible. Since $w_i$ is prime, $k$ must be a power of $w_i$. Since $k$ must be a power of $w_i$, if $k \le w_i^{e_i-1}$, $k$ is then a divisor of $w_i^{e_i-1}$.

So the only possibility is that $k=w_i^{e_i}$. This establishes the above claim.

Let $g=a_1 \cdot a_2 \cdots a_n$. The primitive root modulo $p$ we are looking for is either $g$ if $g or the least residue of $g$ if $g \ge p$.

According to the above claim, the order modulo $p$ of $a_i$ is $w_i^{e_i}$. Clearly $w_i^{e_i}$ and $w_j^{e_j}$ are relatively prime for $i \ne j$. As a corollary of Lemma 6, the order of the product $g=a_1 \cdot a_2 \cdots a_n$ is the products of $w_i^{e_i}$, namely $p-1$. Thus $g=a_1 \cdot a_2 \cdots a_n$ or its least residue modulo $p$ is a primitive root. $\blacksquare$

___________________________________________________________________________________________________________________

$\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}$

# Fermat’s Little Theorem and RSA Algorithm

RSA is a cryptographic algorithm that is used to send and receive messages. We use the Fermat’s Little Theorem to prove that RSA works correctly and accurately. In other words, the decrypted message is indeed the original message from the sender. Mathematically we show that applying the encryption function and the decryption function successively produces the identity function.

To see how RSA works, see the previous post An Illustration of the RSA Algorithm.

___________________________________________________________________________________________________________________

RSA Algorithm

We first briefly describe the algorithm and then present the mathematical statement to validate.

Let $N=p \cdot q$ where $p$ and $q$ are two prime numbers. Let $\phi=(p-1) \cdot (q-1)$. Choose an integer $e$ with $1 such that $e$ and $\phi$ are relatively prime.

The public key consists of $N$ and $e$ where $e$ is the encryption key. Once it is published, anyone can use it to encrypt messages to send to the creator of the public key. The following is the encryption function:

$f(M) \equiv M^e \ (\text{mod} \ N)$

where $M$ is a positive integer and is the original message.

The private key is a positive integer $d$ that satisfies:

$d \cdot e \equiv 1 \ (\text{mod} \ \phi=(p-1) \cdot (q-1))$

In other words, $d$ is the multiplicative inverse of $e$ in the modular arithmetic of modulo $\phi$. The above condition is equivalent to: $de-1=(p-1) \cdot (q-1) \cdot k$ for some integer $k$.

The number $d$ is the decryption key that will be used to decode messages. So it should remain private.

Once the creator of the public key receives an encrypted message $C=f(M)$, he or she uses the following decryption function to obtain the original message $M$.

$g(C) \equiv C^d \ (\text{mod} \ N)$

___________________________________________________________________________________________________________________

The Mathematical Statement to Validate

What we prove is that the decryption function is to undo the encryption function. Specifically, we prove the following:

$g(C)=g(f(M))=(M^e)^d=M^{ed} \equiv M \ (\text{Mod} \ N) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

In other words, applying the decryption function $g$ to the encryption function $f$ produces the original message.

___________________________________________________________________________________________________________________

Fermat’s Little Theorem

In this section, we list out the tools we need to prove the correctness of RSA.

Theorem 1 (Fermat’s Little Theorem)
If $p$ is a prime number and $a$ is an integer such that $a$ and $p$ are relatively prime, then

$a^{p-1}-1$ is an integer multiple of $p$

or equivalently $a^{p-1} \equiv 1 \ (\text{mod} \ p)$.

For a proof of Fermat’s little theorem, see this post.

Lemma 2 (Euclid’s Lemma)
Let $a$, $b$ and $d$ be integers where $d \ne 0$. Then if $d$ divides $a \cdot b$ (symbolically $d \lvert a \cdot b$), then either $d \lvert a$ or $d \lvert b$.

Euclid’s Lemma is needed to prove the following Lemma.

Lemma 3
Let $M$ be an integer. Let $p$ and $q$ be prime numbers with $p \ne q$.

Then if $a \equiv M \ (\text{mod} \ p)$ and $a \equiv M \ (\text{mod} \ q)$, then $a \equiv M \ (\text{mod} \ p \cdot q)$.

Proof of Lemma 3
Suppose we have $a \equiv M \ (\text{mod} \ p)$ and $a \equiv M \ (\text{mod} \ q)$. Then for some integers $i$ and $j$, we have:

$a=M+p \cdot i$ and $a=M+q \cdot j$.

Then $p \cdot i=q \cdot j$. This implies that $p$ divides $q \cdot j$ ($p \lvert q \cdot j$). By Euclid’s lemma, we have either $p \lvert q$ or $p \lvert j$. Since $p$ and $q$ are distinct prime numbers, we cannot have $p \lvert q$. So we have $p \lvert j$ and that $j=p \cdot w$ for some integer $w$.

Now, $a=M+q \cdot j=M+q \cdot p \cdot w$, implying that $a \equiv M \ (\text{mod} \ p \cdot q)$. $\blacksquare$

___________________________________________________________________________________________________________________

The Proof of (1)

We now prove the property $(1)$ described above. We show that

$(M^e)^d=M^{ed} \equiv M \ (\text{Mod} \ N=p \cdot q)$

We first show that $M^{ed} \equiv M \ (\text{Mod} \ p)$ and $M^{ed} \equiv M \ (\text{Mod} \ q)$. Then the desired result follows from Lemma 3.

To show $M^{ed} \equiv M \ (\text{Mod} \ p)$, we consider two cases: $M \equiv 0 \ (\text{Mod} \ p)$ or $M \not \equiv 0 \ (\text{Mod} \ p)$.

Case 1. $M \equiv 0 \ (\text{Mod} \ p)$. Then $M$ is an integer multiple of $p$, say $M=p \cdot w$ where $w$ is an integer. Then $M^{ed}=(p \cdot w)^{ed}=p \cdot p^{ed-1} \cdot w^{ed}$. So both $M$ and $M^{ed}$ are integer multiples of $p$. Thus $M^{ed} \equiv M \ (\text{Mod} \ p)$.

Case 2. $M \not \equiv 0 \ (\text{Mod} \ p)$. This means that $p$ and $M$ are relatively prime (having no common divisor other than 1). Thus we can use Fermat’s Little Theorem. We have $M^{p-1} \equiv 1 \ (\text{mod} \ p)$.

From the way the decryption key $d$ is defined above, we have $ed-1=(p-1) \cdot (q-1) \cdot k$ for some integer $k$. We then have:

\displaystyle \begin{aligned} M^{ed}&=M^{ed-1} \cdot M \\&=M^{(p-1) \cdot (q-1) \cdot k} \cdot M \\&=(M^{p-1})^{(q-1) \cdot k} \cdot M \\&\equiv (1)^{(q-1) \cdot k} \cdot M \ (\text{Mod} \ p) \ * \\&\equiv M \ (\text{Mod} \ p) \end{aligned}

At the step with *, we apply Fermat’s Little Theorem. So we have $M^{ed} \equiv M \ (\text{Mod} \ p)$.

The same reason reasoning can show that $M^{ed} \equiv M \ (\text{Mod} \ q)$.

By Lemma 3, it follows that $M^{ed} \equiv M \ (\text{Mod} \ N=p \cdot q)$. $\blacksquare$

___________________________________________________________________________________________________________________

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

Revised August 9, 2014.