Euler’s phi function, part 1

Posted on August 31, 2013 by Dan Ma

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.

$\text{GCD}(a,m)=1$ .
There is a $b \in \mathbb{Z}_m$ such that $a \cdot b \equiv 1 \ (\text{mod} \ m)$ .
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<j$ 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$

___________________________________________________________________________________________________________________

Comments

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 Congruences

Posted on August 24, 2013 by Dan Ma

A congruence statement that involves unknowns is said to be a congruence equation. In this post, we discuss congruence equations of the form $ax \equiv b \ (\text{mod} \ m)$ where $x$ is the unknown. These are called linear congruence equations. The goal of this post is to describe a method of solving such equations. As a practical application, the decryption key in the RSA algorithm is obtained by solving the linear congruence equation $ax \equiv 1 \ (\text{mod} \ m)$ (see Example 3 below).

Take a simple example of $12x \equiv 30 \ (\text{mod} \ 9)$ . Solving it means finding all integers $x$ such that $9 \ \lvert \ (12x-30)$ or $12x-30=9k$ for some integer $k$ . It is clear that $x=1$ is a solution. After one solution is found, there are infinitely many other solutions. For this example, they are $x=1+9j$ for all integers $j$ . However, these additional solutions are congruent to $x=1$ modulo $m=9$ . Are there other solutions that are not congruent to $x=1$ modulo $m=9$ ? It turns out there are two more, $x=4$ and $x=7$ . Any solution to $12x \equiv 30 \ (\text{mod} \ 9)$ is congruent modulo $m=9$ to one of these three solutions, $x=1$ , $x=4$ or $x=7$ . So the linear congruence equation $12x \equiv 30 \ (\text{mod} \ 9)$ has three distinct solutions.

For the congruence equation $ax \equiv b \ (\text{mod} \ m)$ , we are interested in finding a set of distinct solutions modulo $m$ . Since every integer is congruent modulo $m$ to one of the least residues $0,1,2,3,\cdots,m-1$ , we can simply narrow our focus by looking for solutions only among the least residues.

So by a solution to the linear congruence $ax \equiv b \ (\text{mod} \ m)$ , we mean an integer $x=r$ with $0 \le r \le m-1$ such that $ar \equiv b \ (\text{mod} \ m)$ .

The linear congruence $ax \equiv b \ (\text{mod} \ m)$ may have no solution. If it does have a solution, the number of solutions is $d=\text{GCD}(a,m)$ , which is the greatest common divisor of $a$ and $m$ . The following discussion will make clear how to derive the $d$ many solutions.

___________________________________________________________________________________________________________________

Connection with Linear Diophantine Equations

Note that the equation $ax+my=b$ is another way of stating the linear congruence $ax \equiv b \ (\text{mod} \ m)$ . If one has a solution, so does the other (and vice versa). So the linear congruence equation has a solution if and only if the corresponding linear Diophantine equation has a solution (see Theorem 1 below)

To solve the linear congruence equation $ax \equiv b \ (\text{mod} \ m)$ , one approach is to solve the corresponding linear Diophantine equation $ax+my=b$ . The approach in solving $ax+my=b$ is discussed in the previous post called Solving Linear Diophantine Equations.

___________________________________________________________________________________________________________________

Examples

We first work some examples.

Example 1

Solve $51x \equiv 177 \ (\text{mod} \ 1008)$ .

The linear congruence is identical to the linear Diophantine equation $51x+1008y=177$ . So they both have the same solutions. So we focus on solving $51x+1008y=177$ .

First, find $d=\text{GCD}(51,1008)$ . We carry out the Euclidean algorithm.

$1008=19 \cdot 51+39$

$51=1 \cdot 39+12$

$39=3 \cdot 12+3$

$12=4 \cdot 3+0$

Thus $d=\text{GCD}(51,1008)=3$ . Note that $3 \ \lvert \ 177$ . So the equation $51x+1008y=177$ has solutions. We need to find a particular solution.

To do that, we first solve $51x+1008y=3$ . We work backward in the steps of the Euclidean algorithm as follows:

$\displaystyle \begin{aligned} 3&=39-3 \cdot 12 \\&=39-3 (51-39)\\&=39(4)+51(-3) \\&=(1008-19 \cdot 51) (4)+51(-3) \\&=51(-79)+1008(4) \end{aligned}$

Since $177=3 \cdot 59$ , we have $51(-79 \cdot 59)+1008(4 \cdot 59)=3 \cdot 59=177$ . Thus the number pair $x=-4661$ and $y=236$ is a particular solution of the equation $51x+1008y=177$ . The general solutions are described by

$\displaystyle x=-4661+\frac{1008}{3} \cdot t=-4661+336t$

$\displaystyle y=236-\frac{51}{3} \cdot t=236-17t$

where $t$ is any integer.

To solve the given linear congruence $51x \equiv 177 \ (\text{mod} \ 1008)$ , we only need to use the $x$ solutions. The solutions we are interested in are in the range $0 \le r \le 1007$ . The solutions are $x=43,379,715$ for $t=14,15,16$ . Note that the number of solutions is identical to the GCD of $a=51$ and the modulus $m=1008$ .

Example 2

Solve $51x \equiv 689 \ (\text{mod} \ 1008)$ .

This one has no solutions since $3 \not \lvert \ 689$ . For the same reason, the equation $51x+1008y=689$ has no solutions.

Example 3

Solve $97x \equiv 1 \ (\text{mod} \ 53460)$ .

Just as in Example 1, the first step is to find $d=\text{GCD}(97,53460)$ . We apply the Euclidean algorithm.

$53460=551 \cdot 97+13$

$97=7 \cdot 13+6$

$13=2 \cdot 6+1$

$6=6 \cdot 1+0$

So $d=\text{GCD}(97,53460)=1$ . With Example 1 as a guide, there is only one solution to the given linear congruence.

We work backward in the steps of the Euclidean algorithm to obtain $97(-8267)+53460(15)=1$ . So $x=-8267$ is a particular solution to the given linear congruence equation and its corresponding linear Diophantine equation $97x+53460y=1$ .

Now the general solution is given by $x=-8267+53460t$ for any integer $t$ . The unique solution we look for is $45193$ where $t=1$ .

In the modular arithmetic of congruence modulo $53460$ , the product of $97$ and $45193$ is $1$ . So we can view $45193$ as the multiplicative inverse of $97$ and vice versa. We can of course use a computer program to construct a multiplication table for congruence modulo $53460$ arithmetic. The approach shown here is based on Euclidean algorithm, which is an efficient algorithm for finding inverses.

This example has a connection to the RSA algorithm. The modulus $53460$ is the product $(p-1)(q-1)$ where $p=199$ and $q=271$ are prime numbers. The number $e=97$ and $N=p \cdot q=53929$ is an example for an encryption key for the RSA algorithm. Finding the decryption key entails solving the linear congruence $97x \equiv 1 \ (\text{mod} \ 53460)$ . The prime numbers are obviously small and thus not realistic. It is a good practical demonstration of solving linear congruence. For an illustration of RSA, see the post called An Illustration of the RSA Algorithm.

___________________________________________________________________________________________________________________

Discussion

We now prove some theorems to support the above examples. Theorem 1 translates linear congruence into linear Diophantine equation. Theorem 2 shows how to obtain the solutions of a linear congruence equation given a particular solution.

Theorem 1

Let $d=\text{GCD}(a,m)$ . The following conditions are equivalent.

The linear congruence $ax \equiv b \ (\text{mod} \ m)$ has a solution.
The linear Diophantine equation $ax+my=b$ has a solution.
$d \ \lvert \ b$ .

______________________________________
$\text{ }$
Thus the key to solving a linear congruence equation is to first find the GCD of the coefficient of $x$ and the modulus $m$ . If the GCD divides the constant $b$ , we know there is a solution.

If there is one solution, the linear congruence equation $ax \equiv b \ (\text{mod} \ m)$ has $d=\text{GCD}(a,m)$ many distinct solutions modulo $m$ .

If we carry out the Euclidean algorithm to find the GCD, we can work backward to find a particular solution to the equation $ax+my=d$ . This will lead to a particular solution to the equation $ax+my=b$ , which can be used to describe the $d$ many solutions of the given linear congruence equation $ax \equiv b \ (\text{mod} \ m)$ . Theorem 2 below summarizes this process.

Theorem 2

Let $d=\text{GCD}(a,m)$ . Let $x=x_0$ be a solution to the linear congruence equation $ax \equiv b \ (\text{mod} \ m)$ . We have the following:

The following $d$ integers satisfy the given linear congruence equation and are distinct congruent modulo $m$ .

$\text{ }$

$\displaystyle x=x_0+\frac{m}{d} \cdot t$ where $t=0,1,2,\cdots,d-1$

The $d$ many numbers listed in the first bullet point are the complete solutions in the sense that any number $x$ that satisfies the linear congruence $ax \equiv b \ (\text{mod} \ m)$ is congruent modulo $m$ to one of the numbers in the above bullet point.

$\text{ }$

The least residues modulo $m$ of the $d$ numbers in the first bullet point are the solutions of the given linear congruence equation $ax \equiv b \ (\text{mod} \ m)$ .

$\text{ }$
Proof of Theorem 2

Since $x=x_0$ is a solution to the linear congruence, we have $a \cdot x_0+m \cdot y_0=b$ for some integer $y_0$ . Thus the number pair $x=x_0$ and $y=y_0$ is a particular solution to the linear Diophantine equation $ax+my=b$ . The following describes the complete solution set of $ax+my=b$ .

$\displaystyle x=x_0+\frac{m}{d} \cdot t \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

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

where $t$ is any integer. Now discard the $y$ and consider the following:

$\displaystyle x=x_0+\frac{m}{d} \cdot t$ where $t=0,1,2,\cdots,d-1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

Clearly these $d$ many values satisfy the linear congruence $ax \equiv b \ (\text{mod} \ m)$ . Moreover, they are distinct modulo $m$ since the absolute difference of any two of these values is less than $m$ . So the first bullet point is established.

Any number $x$ that satisfies the linear congruence $ax \equiv b \ (\text{mod} \ m)$ must look like $\displaystyle x=x_0+\frac{m}{d} \cdot j$ where $j$ is some integer (see (1) above). We show that $\displaystyle x=x_0+\frac{m}{d} \cdot j$ is congruent to one of the numbers in (2).

First, look at the case that $j>0$ . By the division algorithm, we have $j=q \cdot d+r$ for some integer $q$ and some integer $r$ with $0 \le r <d$ . Now, we have the following calculation:

$\displaystyle x=x_0+\frac{m}{d} \cdot j=x_0+\frac{m}{d} \cdot (q \cdot d+r)=x_0+m \cdot q+\frac{m}{d} \cdot r \equiv x_0+\frac{m}{d} \cdot r \ (\text{mod} \ m)$

Now look at the case that $j<0$ . By the division algorithm, we have $-j=q \cdot d+r$ for some integer $q$ and some integer $r$ with $0 \le r <d$ . So, $j=(-q) \cdot d+(-r)$ . We have the following calculation.

$\displaystyle x=x_0+\frac{m}{d} \cdot j=x_0+\frac{m}{d} \cdot (-q \cdot d-r)=x_0+m \cdot (-q)+\frac{m}{d} \cdot (-r)$

$\displaystyle \equiv x_0+\frac{m}{d} \cdot (-r) \equiv x_0+\frac{m}{d} \cdot (d-r) \ (\text{mod} \ m)$

The last number $\displaystyle x_0+\frac{m}{d} \cdot (d-r)$ is one of the numbers in (2). So the $d$ many numbers in (2) describes all the solutions to the given linear congruence. Thus the second bullet point is established.

Since we focus on the solutions among the least residues modulo $m$ , we can obtain the $d$ many solutions by taking the least residues of the numbers in the second bullet point. Thus the third bullet point is established. $\blacksquare$

___________________________________________________________________________________________________________________

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

Solving Linear Diophantine Equations

Posted on August 18, 2013 by Dan Ma

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$

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

$y=897-1638k$

$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

Posted on August 14, 2013 by Dan Ma

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<a<m$ . 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<a$ . 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}$

Using Fermat’s Little Theorem to Test Primality

Posted on August 10, 2013 by Dan Ma

Fermat’s little theorem describes a property that is common to all prime numbers. This property can be used as a way to detect the “prime or composite” status of an integer. Primality testing using Fermat’s little theorem is called the Fermat primality test. In this post, we explain how to use this test and to discuss some issues surrounding the Fermat test.

___________________________________________________________________

Describing the test

The Fermat primality test, as mentioned above, is based on Fermat’s little theorem. The following is the statement of the theorem.

Fermat’s little theorem

$n$

$a$

$n$

$a^{n-1} \equiv 1 (\text{mod} \ n) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

The above theorem indicates that all prime numbers possess a certain property. Therefore if a given positive integer does not possess this property, we know for certain that this integer is not prime. Suppose that the primality of an integer $n$ is not known. If we can find an integer $a$ that is relatively prime to $n$ such that $a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$ , then we have conclusive proof that $n$ is composite. Such a number $a$ is said to be a Fermat witness for (the compositeness of) $n$ .

The Fermat test is closedly linked to the notations of probable primes and pseudoprimes. If the congruence relation (1) is true for $n$ and $a$ , then $n$ is said to be a probable prime to base $a$ . Furthermore, if $n$ happens to be a composite number, then $n$ is said to be a pseudoprime to base $a$ . Pseudoprime prime is a composite number that possesses the prime-like property as indicated by (1) for one base $a$ .

The Fermat primality test from a compositeness perspective is about looking for Fermat witnesses. If a Fermat witness is found, the number being tested is proved to be composite. On the other hand, the Fermat primality test, from a primality perspective, consists of checking the congruence relation (1) for several bases that are randomly selected. If the number $n$ is found to be a probable prime to all the randomly chosen bases, then $n$ is likely a prime number.

If the number $n$ is in reality a prime number, then the Fermat test will always give the correct result (as a result of Fermat’s little theorem). If the number $n$ is in reality a composite number, the Fermat test can make the mistake of identifying the composite number $n$ as prime (i.e. identifying a pseudoprime as a prime). For most composite numbers this error probability can be made arbitrarily small (by testing a large number of bases $a$ ). But there are rare composite numbers that evade the Fermat test. Such composite numbers are called Carmichael numbers. No matter how many bases you test on a Carmichael number, the Fermat test will always output Probably Prime. Carmichael numbers may be rare but there are infinitely many of them over the entire number line. More about Carmichael numbers below.

The following describes the steps of the Fermat primality test.

Fermat primality test

$n$

Composite

$n$

Probably Prime

Step 1. Choose a random integer $a \in \left\{2,3,\cdots,n-1 \right\}$ .
Step 2. Compute $\text{GCD}(a,n)$ . If it is greater than 1, then stop and output $n$ is Composite. Otherwise go to the next step.
Step 3. Compute $a^{n-1} \ (\text{mod} \ n)$ .

If $a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$ , then stop and output $n$ is Composite.
If $a^{n-1} \equiv 1 \ (\text{mod} \ n)$ , then $n$ may be a prime number. Do one of the following:

Return to Step 1 and repeat the process with a new $a$ .
Output $n$ is Probably Prime and stop.

$\text{ }$

The exponentiation in Step 3 can be done by the fast powering algorithm. This involves a series of squarings and multiplications. Even for numbers that have hundreds of digits, the fast powering algorithm is efficient.

One comment about Step 2 in the algorithm. Step 2 could be called the GCD test for primality. If you can find an integer $a$ such that $1<a<n$ and such that $\text{GCD}(a,n) \ne 1$ , then the integer $n$ is certainly composite. Such a number $a$ is called a GCD witness for the compositeness of $n$ . So the Fermat test as described above combines the GCD test and the Fermat test. We can use the Euclidean algorithm to find the GCD. If we happen to stumble upon a GCD witness, then we can try another $n$ for a candidate of a prime number. For most composite numbers, it is not likely to stumble upon a GCD witness. Thus when using the Fermat test, it is likely that Step 3 in the algorithm is used.

An example of Fermat primality testing is the post called A primality testing exercise from RSA-100.

____________________________________________________________________________

More about the test

When using the Fermat test, what is the probability of the test giving the correct result? Or what is the probability of making an error? Because the Fermat test is not a true probabilistic primality test, the answers to these questions are conditional. In one scenario which covers most of the cases, the test works like an efficient probabilistic test. In another scenario which occurs very rarely, the Fermat test fails miserably.

As with most diagnostic tests, the Fermat test can make two types of mistakes – false positives or false negatives. For primality testing discussed in this post, we define a positive result as the outcome that says the number being tested is a prime number and a negative result as the outcome that says the number being tested is a composite number. Thus a false positive is identifying a composite number as a prime number and a false negative is identifying a prime number as a composite number.

For the Fermat test, there is no false negative. If $n$ is a prime number in reality, the statement of Fermat’s little theorem does not allow the possibility that $n$ be declared a composite number. Thus if the Fermat test gives a negative result, it would be a true negative. In other words, finding a Fermat witness for $n$ is an irrefutable proof that $n$ is composite.

However, there can be false positives for the Fermat test. This is where things can get a little tricky. A composite number $n$ is said to be a Carmichael number if the above congruence relationship (1) holds for all bases $a$ relatively prime to $n$ . In other words, $n$ is a Carmichael number if $a^{n-1} \equiv 1 (\text{mod} \ n)$ for all $a$ that are relatively prime to $n$ . Saying it in another way, $n$ is a Carmichael number if there exists no Fermat witness for $n$ .

The smallest Carmichael number is 561. Carmichael numbers are rare but there are infinitely many of them. The existence of such numbers poses a challenge for the Fermat test. If you apply the Fermat test on a Carmichael number, the outcome will always be Probably Prime. So the Fermat test will always give a false positive when it is applied on a Carmichael number. To put it in another way, with respect to Carmichael numbers, the error probability of the Fermat test is virtually 100%!

So should a primality tester do? To keep things in perspective, Carmichael numbers are rare (see this post). If the primality testing is done on randomly chosen numbers, choosing a Carmichael number is not likely. So the Fermat test will often give the correct results. For those who are bothered by the nagging fear of working with Carmichael numbers, they can always switch to a Carmichael neutral test such as the Miller-Rabin test.

___________________________________________________________________

One bright spot about the Fermat test

There is one bright spot about the Fermat test. When applying the Fermat test on numbers that are not Carmichael numbers, the error probability can be made arbitrarily small. In this sense the Fermat test works like a true probabilistic primality test. Consider the following theorem.

Theorem 1

$n$

$a$

$1<a<n$

$n$

$a$

$1<a<n$

$n$

Theorem 1 means that the Fermat test can be very accurate on composite numbers that are not Carmichael numbers. As long as there is one base to which the composite number is not a pseudoprime (i.e. as long as there is a Fermat witness for the composite number in question), there will be enough of such bases (at least 50% of the possible bases). As a result, it is likely that the Fermat test will find a witness, especially if the tester is willing to use enough bases to test and if the bases are randomly chosen. When a base is randomly chosen, there is at least a 50% chance that the number $n$ is not a pseudoprime to that base (i.e. the Fermat test will detect the compositeness) or putting it in another way, there is at most a 50% chance that the Fermat test will not detect the compositeness of the composite number $n$ . So if $k$ values of $a$ are randomly selected, there is at most $0.5^k$ probability that the Fermat test will not detect the compositeness of the composite number $n$ (i.e. making a mistake). So the probability of a false positive is at most $0.5^k$ . For a large enough $k$ , this probability is practically zero.

Proof of Theorem 1
A base to which $n$ is a pseudoprime or not a pseudoprime should be a number in the interval $1<a<n$ that is relatively prime to $n$ . If $n$ is a pseudoprime to base $a$ , then $a$ raised to some power is congruent to 1 modulo $n$ . For this to happen, $a$ must be relatively prime to the modulus $n$ . For this reason, when we consider a base, it must be a number that is relatively prime to the composite integer $n$ (see the post on Euler’s phi function).

Let $a$ be a base to which $n$ is not a pseudoprime. We make the following claim.

Claim

$b$

$1<b<n$

$n$

$b$

$n$

$a \cdot b$

Since both integers $a$ and $b$ are assumed to be relatively prime to $n$ , the product $a \cdot b$ is also relatively prime to $n$ (see Lemma 4 in this post). Now consider the congruence $(ab)^{n-1} \ (\text{mod} \ n)$ , which is derived as follows:

$(ab)^{n-1} \equiv a^{n-1} \cdot b^{n-1} \equiv a^{n-1} \not \equiv 1 \ (\text{mod} \ n)$

In the above derivation, we use the fact that $n$ is not a pseudoprime to base $a$ and $n$ is a pseudoprime to base $b$ . The above derivation shows that $n$ is not a pseudoprime to base $ab$ .

If $n$ is not a pseudoprime to all bases in $1<w<n$ , then we are done. So assume that $n$ is a pseudoprime to at least one base. Let $b_1,b_2,\cdots,b_k$ enumerate all bases to which $n$ is a pseudoprime. We assume that the $b_j$ are all distinct. So $b_i \not \equiv b_j \ (\text{mod} \ n)$ for all $i \ne j$ . By the above claim, the composite number $n$ is not a pseudoprime to all the following $k$ numbers:

$a \cdot b_1, \ a \cdot b_2, \cdots, \ a \cdot b_k$

It is also clear that $a \cdot b_i \not \equiv a \cdot b_j \ (\text{mod} \ n)$ for $i \ne j$ . What we have just shown is that there are at least as many bases to which $n$ is not a pseudoprime as there are bases to which $n$ is a pseudoprime. This means that $n$ is not a pseudoprime to at least 50% of the bases that are relatively prime to $n$ . In other words, as long as there exists one Fermat witness for $n$ , at least 50% of the bases are Fermat witnesses for $n$ . It then follows that $n$ is a pseudoprime to no more than 50% of the bases relatively prime to $n$ . $\blacksquare$

There is another way to state Theorem 1. Recall that Euler’s phi function $\phi(n)$ is defined to be the number of integers $a$ in the interval $1<a<n$ that are relatively prime to $n$ . With this in mind, Theorem 1 can be restated as the following:

Corollary 2

$n$

$\displaystyle \frac{\phi(n)}{2}$

$1<a<n$

___________________________________________________________________

Concluding remarks

Of course, Theorem 1 works only for the composite numbers that are not pseudoprime to at least one base (i.e. they are not Carmichael numbers). When you test the compositeness of a number, you do not know in advance if it is Carmichael or not. On the other hand, if the testing is done on randomly chosen numbers, it is not likely to randomly stumble upon Carmichael numbers. The Fermat test works well for the most part and often give the correct results. If one is concerned about the rare chance of a false positive in the form of a Carmichael number, then the Miller-Rabin test will be a good alternative.

Note:
The original post was written in August 10, 2013. On March 29, 2015, this post is replaced with a blog post called The Fermat primality test from the companion math crypto blog.

___________________________________________________________________
$\copyright \ \ 2013 - 2015 \ \text{Dan Ma}$

Congruence Arithmetic and Fast Powering Algorithm

Posted on August 4, 2013 by Dan Ma

In some cryptography applications such as RSA algorithm, it is necessary to compute $\displaystyle a^w$ modulo $m$ where the power $w$ and the modulus $m$ are very large numbers. We discuss and demonstrate an efficient algorithm that can handle such calculations. This general algorithm has various names such as fast powering algorithm, square-and-multiply algorithm and exponentiation by squaring.

The problem at hand is to compute $a^w \ (\text{mod} \ m)$ . The naïve approach is to compute by repeatedly multiplying by $a$ and reducing modulo $m$ . When the power $w$ is large (e.g. an integer with hundreds of digits), this approach is difficult or even impossible (given the current technology). In this post we discuss an alternative that is known as the fast powering algorithm.

___________________________________________________________________________________________________________________

An Example

Compute $1286^{1171}$ modulo $1363$ .

Using the naïve approach described earlier, we would do something like the following:

$\displaystyle \begin{aligned} 1286^{1171} &=(1286 \cdot 1286) \cdot 1286^{1269} \equiv 477 \cdot 1286^{1269} \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&=(477 \cdot 1286) \cdot 1286^{1268} \equiv 72 \cdot 1286^{1268} \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&=(72 \cdot 1286) \cdot 1286^{1267} \equiv 1271 \cdot 1286^{1267} \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&\text{ }\cdots \\&\text{ }\cdots \\&\text{ }\cdots \end{aligned}$

In this naïve approach, we would multiply two numbers at a time and then reduce the result modulo $1363$ so that the numbers do not get too large. The above example would involve $1170$ multiplications and then $1170$ divisions for the reduction modulo $1363$ . Great difficulty comes when the power is not $1171$ and instead is an integer with hundreds or even thousands of digits.

Note that in the above naïve approach, the power is reduced by one at each step. In the fast power alternative, the power comes down by an exponent of two in each step. The idea is to use the binary expansions of the exponent $1171$ to transform the computation of $1286^{1171}$ into a series of squarings and multiplications. To this end, we write $1171$ as a sum of powers of two as follows:

$(1) \ \ \ \ \ \ \ \ \ 1171=2^0+2^1+2^4+2^7+2^{10}$

Next we compute $1286^{2^0},1286^{2^1},1286^{2^2},1286^{2^3},\cdots,1286^{2^{10}}$ modulo $1363$ . Note that each term is the square of the preceding term, hence the word square in the name “square-and-multiply”. To make it easier to see, we put the results in the following table.

$\displaystyle (2) \ \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ i }&\text{ }&1286^{2^i}&\text{ }&\text{squaring}&\text{ }&\text{modulo } 1363&\text{ }&\text{ } \\\text{ }&\text{ }&\text{ } \\ 0&\text{ }&1286^{2^0}&\text{ }&\text{ }&\text{ }&\equiv 1286&\text{ }&* \\ 1&\text{ }&1286^{2^1}&\text{ }&\equiv 1286^2&\text{ }&\equiv 477&\text{ }&* \\ 2&\text{ }&1286^{2^2}&\text{ }&\equiv 477^2&\text{ }&\equiv 1271&\text{ }&\text{ } \\ 3&\text{ }&1286^{2^3}&\text{ }&\equiv 1271^2&\text{ }&\equiv 286&\text{ }&\text{ } \\ 4&\text{ }&1286^{2^4}&\text{ }&\equiv 286^2&\text{ }&\equiv 16&\text{ }&* \\ 5&\text{ }&1286^{2^5}&\text{ }&\equiv 16^2&\text{ }&\equiv 256&\text{ }&\text{ } \\ 6&\text{ }&1286^{2^6}&\text{ }&\equiv 256^2&\text{ }&\equiv 112&\text{ }&\text{ } \\ 7&\text{ }&1286^{2^7}&\text{ }&\equiv 112^2&\text{ }&\equiv 277&\text{ }&* \\ 8&\text{ }&1286^{2^8}&\text{ }&\equiv 277^2&\text{ }&\equiv 401&\text{ }&\text{ } \\ 9&\text{ }&1286^{2^9}&\text{ }&\equiv 401^2&\text{ }&\equiv 1330&\text{ }&\text{ } \\ 10&\text{ }&1286^{2^{10}}&\text{ }&\equiv 1330^2&\text{ }&\equiv 1089&\text{ }&* \end{bmatrix}$

Note that the rows marked by * in the above table are the results that we need. In the above table, there are 10 multiplications for the squarings and 10 divisions for the reduction modulo $1363$ .

Now $1286^{1171}$ is calculated as follows:

$\displaystyle \begin{aligned} (3) \ \ \ \ \ \ \ \ \ 1286^{1171} &=1286^{2^0} \cdot 1286^{2^1} \cdot 1286^{2^4} \cdot1286^{2^7} \cdot 1286^{2^{10}} \\&\equiv 1286 \ \ \cdot 477 \ \ \ \ \cdot 16 \ \ \ \ \ \cdot 277 \ \ \ \ \cdot 1089 \ \ \text{mod} \ 1363 \\&\equiv 72 \ \ \ \ \cdot 16 \ \ \ \ \ \cdot 277 \ \ \ \ \cdot 1089 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&\equiv 1152 \ \ \cdot 277 \ \ \cdot 1089 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&\equiv 162 \ \ \cdot 1089 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&\equiv 591 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \end{aligned}$

We have the answer $1286^{1171} \equiv 591 \ (\text{mod} \ 1363)$ . The calculation in (3) is the step that gives the word “multiply” in the name “square-and-multiply”. In this step, we multiply the results obtained from the previous step.

We now tally up the amount of work that is done. The calculation in table (2) requires 10 multiplications for the squaring and 10 divisions for the reduction modulo $1363$ . The calculation in (3) requires 4 multiplications and 4 divisions for the reduction modulo $1363$ . Together, there are 14 multiplications and 14 divisions. In contrast, the naïve approach would require 1170 multiplications and 1170 divisions!

___________________________________________________________________________________________________________________

Description of Fast Powering Algorithm

To compute $a^w \equiv (\text{mod} \ m)$ , use the following steps. The following steps correspond with the steps in the above example.

Step (1)

Compute the binary expansions of the power $w$ .

$\displaystyle w=C_0 +C_1 \cdot 2^{1}+C_2 \cdot 2^{2}+\cdots+C_{k-1} \cdot 2^{k-1}+C_k \cdot 2^{k}$

where each $j$ , $C_j=0$ or $C_j=1$ . In particular, we assume that $C_k=1$ .

Step (2)

For each $j=0,1,2,\cdots,k$ , compute $\displaystyle a^{2^j} \equiv A_j$ modulo $m$ . Note that each $\displaystyle a^{2^j} \equiv A_j$ is the result of squaring the previous term $\displaystyle a^{2^{j-1}} \equiv A_{j-1}$ . We arrange the calculation in the following table.

$\displaystyle (2) \ \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ i }&\text{ }&a^{2^i}&\text{ }&\text{squaring}&\text{ }&\text{modulo } m&\text{ }&\text{ } \\\text{ }&\text{ }&\text{ } \\ 0&\text{ }&a^{2^0}&\text{ }&\text{ }&\text{ }&A_0\equiv a&\text{ }&\text{ } \\ 1&\text{ }&a^{2^1}&\text{ }&\equiv A_0^2&\text{ }&\equiv A_1&\text{ }&\text{ } \\ 2&\text{ }&a^{2^2}&\text{ }&\equiv A_1^2&\text{ }&\equiv A_2&\text{ }&\text{ } \\ 3&\text{ }&a^{2^3}&\text{ }&\equiv A_2^2&\text{ }&\equiv A_3&\text{ }&\text{ } \\ \text{ }&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\text{ } \\ \text{ }&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\text{ } \\ \text{ }&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\text{ } \\ k-1&\text{ }&a^{2^{k-1}}&\text{ }&\equiv A_{k-2}^2&\text{ }&\equiv A_{k-1}&\text{ }&\text{ } \\ k&\text{ }&a^{2^k}&\text{ }&\equiv A_{k-1}^2&\text{ }&\equiv A_k&\text{ }&\text{ } \end{bmatrix}$

Step (3)

Compute $a^w \equiv (\text{mod} \ m)$ using the following derivation.

$\displaystyle \begin{aligned}(3) \ \ \ \ \ \ \ \ \ a^{w}&=a^{C_0 +C_1 \cdot 2^{1}+C_2 \cdot 2^{2}+\cdots+C_{k-1} \cdot 2^{k-1}+C_k \cdot 2^{k}} \\&=a^{C_0} \cdot a^{C_1 \cdot 2^{1}} \cdot a^{C_2 \cdot 2^{2}} \cdots a^{C_{k-1} \cdot 2^{k-1}} \cdot a^{C_k \cdot 2^{k}} \\&=a^{C_0} \cdot (a^{2^{1}})^{C_1} \cdot (a^{2^{2}})^{C_2} \cdots (a^{2^{k-1}})^{C_{k-1}} \cdot (a^{2^{k}})^{C_k} \\&\equiv A_0^{C_0} \cdot (A_1)^{C_1} \cdot (A_2)^{C_2} \cdots (A_{k-1})^{C_{k-1}} \cdot (A_k)^{C_k} \ \ \ \ \ (\text{mod} \ m) \end{aligned}$

The last line in (3) is to be further reduced modulo $m$ . In the actual calculation, only the terms with $C_j=1$ need to be used.

We now establish an upper bound for the number multiplications. Step (2) requires $k$ multiplications and $k$ divisions to reduce modulo $m$ . Step (3) requires at most $k$ many multiplications since some of the $C_j$ many be zero. Step (3) also requires at most $k$ many divisions to reduce modulo $m$ . So altogether, the algorithm requires at most $2k$ multiplications and $2k$ divisions.

From Step (1), we know that $\displaystyle 2^k \le w$ . Take natural log of both sides, we have $\displaystyle k \le \frac{\text{ln}(w)}{\text{ln}(2)}$ and $\displaystyle 2 \cdot k \le \frac{2 \cdot \text{ln}(w)}{\text{ln}(2)}$ . So the fast powering algorithm requires at most

$\displaystyle \frac{2 \cdot \text{ln}(w)}{\text{ln}(2)}$

many multiplications and at most that many divisions to compute the congruence calculation $a^w \equiv (\text{mod} \ m)$ .

For example, when the power $w=2^{127}-1$ , which is a Mersenne prime, which has 39 digits. Now $w \approx 2^{127}$ . By the above calculation, the fast powering algorithm would take at most 254 multiplications and at most 254 divisions to do the power congruence computation.

The fast powering calculations demonstrated in this post can be done by hand (using a hand-held calculator). In real applications, such calculations should of course be done in a computer.

___________________________________________________________________________________________________________________

Another Example

Use the fast power algorithm to show that

$4030^{2657} \equiv 21144 \ (\text{mod} \ 55049)$

$21144^{79081} \equiv 4030 \ (\text{mod} \ 55049)$

Note that one congruence is encryption and the other one is decryption. We demonstrate the second calculation.

In doing the second calculation, we use a little bit of help from Fermat’s little theorem. The modulus $55049$ is a prime number. So $21144^{55048} \equiv 1 \ (\text{mod} \ 55049)$ . Thus we have:

$21144^{79081}=21144^{24033} \cdot 21144^{55048} \equiv 21144^{24033} \ (\text{mod} \ 55049)$

Step (1)

The binary expansions of $24033$ are:

$24033=2^0+2^5+2^6+2^7+2^8+2^{10}+2^{11}+2^{12}+2^{14}$

Step (2)

Compute $21144^{2^j}$ modulo $55049$ for each $j$ . The computation is displayed in the following table. The rows with * are the results that we need for Step (3).

$\displaystyle \begin{bmatrix} \text{ i }&\text{ }&21144^{2^i}&\text{ }&\text{squaring}&\text{ }&\text{modulo } 55049&\text{ }&\text{ } \\\text{ }&\text{ }&\text{ } \\ 0&\text{ }&21144^{2^0}&\text{ }&\text{ }&\text{ }&\equiv 21144&\text{ }&* \\ 1&\text{ }&21144^{2^1}&\text{ }&\equiv 21144^2&\text{ }&\equiv 15807&\text{ }&\text{ } \\ 2&\text{ }&21144^{2^2}&\text{ }&\equiv 15807^2&\text{ }&\equiv 48887&\text{ }&\text{ } \\ 3&\text{ }&21144^{2^3}&\text{ }&\equiv 48887^2&\text{ }&\equiv 41483&\text{ }&\text{ } \\ 4&\text{ }&21144^{2^4}&\text{ }&\equiv 41483^2&\text{ }&\equiv 7549&\text{ }&\text{ } \\ 5&\text{ }&21144^{2^5}&\text{ }&\equiv 7549^2&\text{ }&\equiv 11686&\text{ }&* \\ 6&\text{ }&21144^{2^6}&\text{ }&\equiv 11686^2&\text{ }&\equiv 41076&\text{ }&* \\ 7&\text{ }&21144^{2^7}&\text{ }&\equiv 41076^2&\text{ }&\equiv 40975&\text{ }&* \\ 8&\text{ }&21144^{2^8}&\text{ }&\equiv 40975^2&\text{ }&\equiv 11174&\text{ }&* \\ 9&\text{ }&21144^{2^9}&\text{ }&\equiv 11174^2&\text{ }&\equiv 7144&\text{ }&\text{ } \\ 10&\text{ }&21144^{2^{10}}&\text{ }&\equiv 7144^2&\text{ }&\equiv 6313&\text{ }&* \\ 11&\text{ }&21144^{2^{11}}&\text{ }&\equiv 6313^2&\text{ }&\equiv 53542&\text{ }&* \\ 12&\text{ }&21144^{2^{12}}&\text{ }&\equiv 53542^2&\text{ }&\equiv 14040&\text{ }&* \\ 13&\text{ }&21144^{2^{13}}&\text{ }&\equiv 14040^2&\text{ }&\equiv 46180&\text{ }&\text{ } \\ 14&\text{ }&21144^{2^{14}}&\text{ }&\equiv 46180^2&\text{ }&\equiv 49189&\text{ }&* \end{bmatrix}$

Step (3)

Compute $21144^{79081} \ (\text{mod} \ 55049)$ .

$\displaystyle \begin{aligned} 21144^{24033} &=21144^{2^0} \cdot 21144^{2^5} \cdot 21144^{2^6} \cdot 21144^{2^7} \cdot 21144^{2^{8}} \cdot 21144^{2^{10}} \cdot 21144^{2^{11}} \cdot 21144^{2^{12}} \cdot 21144^{2^{14}} \\&\equiv 21144 \cdot 11686 \cdot 41076 \cdot 40975 \cdot 11174 \cdot 6313 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \text{mod} \ 55049 \\&\equiv 25665 \cdot 40975 \cdot 11174 \cdot 6313 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 22328 \cdot 11174 \cdot 6313 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 11004 \cdot 6313 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 51463 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 9300 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 50821 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 4030 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \end{aligned}$

___________________________________________________________________________________________________________________

The Fundamental Theorem of Arithmetic

Posted on July 31, 2013 by Dan Ma

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<n$ .

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

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.

___________________________________________________________________________________________________________________

Euclid’s Lemma

Posted on July 29, 2013 by Dan Ma

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$ .

___________________________________________________________________________________________________________________

The Euclidean Algorithm

Posted on July 28, 2013 by Dan Ma

In this post, we discuss the Euclidean algorithm, which is an algorithm to find the greatest comment divisor of two integers. This post is also part of the series of posts leading up to the fundamental theorem of arithmetic.

___________________________________________________________________________________________________________________

Introduction

Computing the greatest common divisor of two integers is a topic that is taught in elementary school and is also an important tool that is of great interest in number theory. We begin with an example.

Let’s take a simple example of finding the greatest common divisor of 24 and 60. In a math class in elementary school, one motivation of finding the greatest common divisor of 24 and 60 is to reduce the fraction $\displaystyle \frac{24}{60}$ to its lowest terms. The first step is to factor each of the numerator and denominator using their prime factors.

$\displaystyle \frac{24}{60}=\frac{2 \cdot 2 \cdot 2 \cdot 3}{2 \cdot 2 \cdot 3 \cdot 5}$

Then cross out the prime factors common to the numerator and the denominator.

$\displaystyle \frac{24}{60}=\frac{\not 2 \cdot \not 2 \cdot 2 \cdot \not 3}{\not 2 \cdot \not 2 \cdot \not 3 \cdot 5}=\frac{2}{5}$

The product of the prime factors that are crossed out is $2 \cdot 2 \cdot 3=12$ , which is the greatest common divisor of 24 and 60.

Thus the greatest common divisor of two integers $a$ and $b$ is the product of the prime factors shared by the two numbers. This approach of finding the greatest common divisor depends on performing prime factorization, which is a hard problem for larger numbers. This approach, though conceptually clear, is clearly not efficient.

We need an algorithm for finding the greatest common divisor that does not require prime factorization. First, we have another discussion on the greatest common divisor.

___________________________________________________________________________________________________________________

The Greatest Common Divisor

Let $a$ and $b$ be integers. We say that $a$ divides $b$ (denoted by $a \ \lvert \ b$ ) if there is an integer $q$ such that $b=q \cdot a$ . In other words, $a \ \lvert \ b$ if $a$ divides $b$ without leaving a remainder. For examples, $3 \ \lvert \ 18$ and $7 \ \lvert \ 91$ . When $a$ does not divide $b$ , we write $a \not \lvert \ b$ .

The greatest common divisor (or GCD) of two integers $a$ and $b$ is denoted by $\text{GCD}(a,b)$ and is the largest positive integer that divides both $a$ and $b$ . It is clear that $\text{GCD}(a,b)$ is the positive integer $d$ such that

$d \lvert a$ and $d \lvert b$ .
If $c \lvert a$ and $c \lvert b$ , then $c \le d$ .

The greatest common integer $\text{GCD}(a,b)$ is always uniquely defined. Each integer has only finitely many integer divisors. So there are only finitely many divisors common to both $a$ and $b$ (the integer 1 is one of them). Any finite set of real numbers has a unique largest element. Thus among all the common divisors of $a$ and $b$ , there is the largest one, which we denote by $\text{GCD}(a,b)$ . Consequently, $\text{GCD}(a,b) \ge 1$ .

We can observe that the greatest common integer $\text{GCD}(a,b)$ defined in this section is identical to the product of the prime factors shared by the two integers $a$ and $b$ .

To perform the Euclidean algorithm, we need the division algorithm and the following lemma.

Division Algorithm
Let $a$ and $b$ be positive integers. Then there exist unique integers $q$ and $r$ such that

$a = q \cdot b + r$

where $0 \le r <b$ .

Lemma 1
Let $a$ and $b$ be positive integers. If $a=q \cdot b+r$ , then $\text{GCD}(a,b)=\text{GCD}(b,r)$ .

For the discussion in this post, Lemma 1 is used in conjunction with the division algorithm. So we put Lemma 1 in words in the context of applying the division algorithm as follows.

Lemma 1. When $a$ is divided by $b$ , the GCD of $a$ and $b$ is the same as the GCD of the $b$ (the divisor) and the $r$ (the remainder).

Proof of Lemma 1

Suppose that $a=q \cdot b+r$ . Let $h=\text{GCD}(a,b)$ and $k=\text{GCD}(b,r)$ .

We first show that $h \le k$ . Since $a=q \cdot b+r$ and since $h \ \lvert \ a$ and $h \ \lvert \ b$ , we have $h \ \lvert \ r$ . Since $h$ is a common divisor of $b$ and $r$ , $h \le k$ .

Now we show $k \le h$ . Since $a=q \cdot b+r$ , it follows that $k$ is a common divisor of $a$ and $b$ . Thus $k \le h$ . $\blacksquare$

___________________________________________________________________________________________________________________

Example for the Euclidean Algorithm

Before defining the Euclidean algorithm, let’s look at an example. Find the greatest common divisor of $1638$ and $357$ .

The Euclidean algorithm can be implemented using subtraction or division.

In the subtraction implementation, the Euclidean algorithm starts with a pair of positive integers and forms a new pair that consists of the smaller integer and the difference between the larger and smaller integers. The process repeats until the two integers are equal. That number then is the greatest common divisor of the original pair.

The following series of subtractions derives the GCD of $1638$ and $357$ .

$\displaystyle (1) \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ }&\text{ }&\text{Number 1}&\text{ }&\text{Number 2} \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1638&\text{ }&357 \\ 2&\text{ }&1281&\text{ }&357 \\ 3&\text{ }&924&\text{ }&357 \\ 4&\text{ }&567&\text{ }&357 \\ 5&\text{ }&210&\text{ }&357 \\ 6&\text{ }&210&\text{ }&147 \\ 7&\text{ }&63&\text{ }&147 \\ 8&\text{ }&63&\text{ }&84 \\ 9&\text{ }&63&\text{ }&21 \\ 10&\text{ }&42&\text{ }&21 \\ 11&\text{ }&21&\text{ }&21 \end{bmatrix}$

In the above table, to go from one row to the next, the larger number is reduced by the smaller number. The process stops when the two numbers are equal. In this example, the greatest common divisor is $21$ .

Note that the above subtraction process can be speeded up by doing division instead. For example, in the above table, you can jump from row 1 to row 5 by applying the division algorithm. The following is the same example using the division implementation.

$\displaystyle (2) \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ }&\text{ }&\text{Number 1}&\text{ }&\text{Number 2} \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1638&\text{ }&357 \\ 2&\text{ }&210&\text{ }&357 \\ 3&\text{ }&210&\text{ }&147 \\ 4&\text{ }&63&\text{ }&147 \\ 5&\text{ }&63&\text{ }&21 \\ 6&\text{ }&0&\text{ }&21 \end{bmatrix}$

To go from row 1 to row 2, divide $1638$ by $357$ to obtain the remainder $210$ . To go from row 2 to row 3, divide the larger number $357$ by $210$ to obtain the remainder $147$ . Repeat the process until one of reaching the remainder of zero. Then the other number in the last row is the greatest common divisor. The following is the same algorithm with the divisions added.

$\displaystyle (3) \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ }&\text{ }&\text{Number 1}&\text{ }&\text{Number 2}&\text{ }&\text{Division} \\\text{ }&\text{ }&\text{ } \\ 1&\text{ }&1638&\text{ }&357&\text{ }&1638=4 \cdot 357+210 \\ 2&\text{ }&210&\text{ }&357&\text{ }&357=1 \cdot 210+147 \\ 3&\text{ }&210&\text{ }&147&\text{ }&210=1 \cdot 147+63 \\ 4&\text{ }&63&\text{ }&147&\text{ }&147=2 \cdot 63+21 \\ 5&\text{ }&63&\text{ }&21&\text{ }&63=3 \cdot 21+0 \\ 6&\text{ }&0&\text{ }&21 \end{bmatrix}$

As shown in the example, the Euclidean algorithm only requires subtractions or divisions and no prime factorization. Note that Lemma 1 is used throughout the two tables. Let’s look at table (3). Because the GCD of two numbers is the same as the divisor and the remainder (Lemma 1), the GCD of any row is identical to the GCD of the row below.

___________________________________________________________________________________________________________________

The Euclidean Algorithm

In the remainder of the post, we only discuss the division implementation of the Euclidean algorithm. The following is the description of the Euclidean algorithm.

Euclidean Algorithm

Let $a_0$ and $b_0$ be positive integers. Assume $b_0<a_0$ . Start with the pair $(a_0,b_0)$ and forms a new pair that consists of the smaller number and the remainder derived from dividing the larger number by the smaller. The process stops when reaching a remainder of zero. Then the other number in the last pair is the GCD of $a_0$ and $b_0$ .

To describe using some notations, we have the following divisions.

$a_0=q_0 \cdot b_0+r_0 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \le r_0<b_0$

$b_0=q_1 \cdot r_0+r_1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \le r_1<r_0$

$r_0=q_0 \cdot r_1+r_2 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \le r_2<r_1$

$\cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots$

$r_k=q_k \cdot r_{k+1}+r_{k+2} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \le r_{k+2}<r_{k+1}$

The above series of divisions will stop at some $k=j$ where the remainder $r_{j+2}=0$ . We have $r_j=q_j \cdot r_{j+1}$ where $r_{j+1}$ is the GCD of the original pair $(a_0,b_0)$ .

Proof of Euclidean Algorithm
In the above notation, the sequence of non-negative numbers $b_0>r_0>r_1>r_2>\cdots$ must stop at some point. Eventually $r_{j+2}=0$ for some $j$ . We have $r_j=q_j \cdot r_{j+1}+0$ . Then $\text{GCD}(r_j,r_{j+1})=\text{GCD}(r_{j+1},0)=r_{j+1}$ .

Applying Lemma 1 repeatedly, we have:

$\displaystyle \begin{aligned} r_{j+1}&=\text{GCD}(r_{j+1},0) \\&=\text{GCD}(r_j,r_{j+1}) \\&\cdots \\&\cdots \\&\cdots \\&=\text{GCD}(r_1,r_{2}) \\&=\text{GCD}(r_0,r_{1}) \\&=\text{GCD}(b_0,r_{0}) \\&=\text{GCD}(a_0,b_{0}) \end{aligned}$

Comment. Note that the statement of the Euclidean algorithm starts with a pair of positive integers $(a_0,b_0)$ . If either number is negative, we can take the absolute value of the numbers and the resulting GCD is the same as the original pair. This follows from the following fact.

$\text{GCD}(a,b)=\text{GCD}(-a,b)=\text{GCD}(a,-b)=\text{GCD}(-a,-b)$

___________________________________________________________________________________________________________________

The Extended Euclidean Algorithm

Another good use of the Euclidean algorithm is to find integer solutions to the linear equation $ax+by=d$ where $d=\text{GCD}(a,b)$ . This is called the extended Euclidean algorithm. We state it in the following lemma.

Lemma 2 (The Extended Euclidean Algorithm)
Let $a$ and $b$ be integers. Let $d=\text{GCD}(a,b)$ . Then there are integers $x$ and $y$ that satisfies the equation $ax+by=d$ .

Proving Lemma 2 is a matter of working the Euclidean algorithm backward. We demonstrate the idea using our example of $a=1638$ and $b=357$ . The following shows the divisions used in Table (3) above.

$1638=4 \cdot 357+210$
$357=1 \cdot 210+147$
$210=1 \cdot 147+63$
$147=2 \cdot 63+21$
$63=3 \cdot 21+0$

We start off with the second to the last division and work backward.

$\displaystyle \begin{aligned} 21&=147-2 \cdot 63 \\&=147 - 2 \cdot (210-147) \\&=3 \cdot 147-2 \cdot 210 \\&=3 \cdot (357-210)-2 \cdot 210 \\&=3 \cdot 357 -5 \cdot 210 \\&=3 \cdot 357- 5 \cdot (1638- 4 \cdot 357) \\&=(-5) \cdot 1638+23 \cdot 357 \end{aligned}$

The equation $1638x+357y=21$ has solution $x=-5$ and $y=23$ .

As an application to the extended Euclidean algorithm, we have the following corollary.

Corollary 3
Let $a$ and $b$ be integers. Let $h=\text{GCD}(a,b)$ . Then if $k$ is a common divisor of $a$ and $b$ , then $k$ is a divisor of $h$ .

Proof of Corollary
According to Lemma 2, there are integers $x$ and $y$ such that $ax+by=h$ . Note that $k$ divides each term on the left-hand side of this equation. So $k$ divides $h$ as well. $\blacksquare$
___________________________________________________________________________________________________________________

The Division Algorithm

Posted on July 27, 2013 by Dan Ma

The division algorithm is the conceptual underpinning of many concepts in number theory (congruence arithmetic is one example). In this post, we present a proof of the division algorithm and connect it to one important property of congruence.

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

___________________________________________________________________________________________________________________

The Division Algorithm

The following is the statement of the division algorithm.

Let $a$ and $b$ be positive integers. Then there exist unique integers $q$ and $r$ such that

$a = q \cdot b + r$

where $0 \le r <b$ .

Let $A$ be the set $A=\left\{a-jb: j=0,1,2,3,\cdots \right\}$ . Let $A_+$ be the following subset of $A$ .

$A_+=\left\{x \in A: x \ge 0 \right\}$

The set $A_+$ is a set of non-negative integers. Hence it must have a least element, say $r$ . Then we have $r=a-qb$ for some positive integer $q$ . Furthermore, we have $0 \le r<b$ . If $r>b$ , $r$ would not be the least element of $A_+$ since we can subtract $b$ into $r$ to obtain $a-(q+1)b$ , which is less than $r$ and is an element of $A_+$ .

We now have found integers $q$ and $r$ such that $a = q \cdot b + r$ . It remains to show that the integers $q$ and $r$ are unique. Suppose there are also integers $q_0$ and $r_0$ such that

$a=q \cdot b + r=q_0 \cdot b + r_0$

After subtracting, $(q-q_0) \cdot b + (r-r_0)=0$ . Since $b$ divides both $0$ and $(q-q_0) \cdot b$ , $b$ must divides $r-r_0$ . This means that $r-r_0=0$ , since both $r$ and $r_0$ are non-negative integers that are less than $b$ . Thus $r=r_0$ and in turns $q-q_0$ . $\blacksquare$

Conceptually the division algorithm tells us that there is a unique remainder $r$ upon division of $a$ by $b$ . In terms of actual computation, it does not tell us how to find the remainder or the quotient. However it is the conceptual underpinning of many concepts and ideas in number theory.

___________________________________________________________________________________________________________________

Congruence

We now use the division algorithm to prove one important property of congruence. The symbol $a \equiv b \ (\text{mod} \ m)$ means that $m$ divides $a-b$ (in words, we say $a$ is congruent to $b$ modulo $m$ ). For a basic discussion of congruence arithmetic, see “A basic discussion of congruences”. We prove the following property of congruence.

For every integer $a$ , $a \equiv r \ (\text{mod} \ m)$ for a unique integer $r$ with $0 \le r<m$ .

In other words, any integer is congruence modulo $m$ to one and only one element $r$ in the set $\left\{0,1,2,\cdots,m-1 \right\}$ . The integer $r$ is called the least residue of $a$ modulo $m$ .

The above property about least residue follows from the division algorithm. Let $a$ be any integer. If $a=0$ , clearly $a \equiv 0 \ (\text{mod} \ m)$ . We can assume that $a \ne 0$ .

Now consider the case that $a>0$ . By the division algorithm, there are integers $q$ and $r$ such that $a=q \cdot m+r$ where $0 \le r <m$ . Thus $a \equiv r \ (\text{mod} \ m)$ .

Consider the case that $a<0$ . By the division algorithm, there are integers $q$ and $r$ such that $-a=q \cdot m+r$ where $0 \le r <m$ . Immediately we have $a=(-q) \cdot m+(-r)$ . Thus $a \equiv -r \ (\text{mod} \ m)$ . Note that $-r \equiv m-r \ (\text{mod} \ m)$ . Thus $a \equiv m-r \ (\text{mod} \ m)$ /

One concluding remark is that any least residue that is found in the above argument is unique. This is because no two distinct elements of the set $\left\{0,1,2,\cdots,m-1 \right\}$ can be congruent to each other. $\blacksquare$

___________________________________________________________________________________________________________________

Exploring Number Theory

A blog on elementary number theory

Tag Archives: Number Theory

Euler’s phi function, part 1

Solving Linear Congruences

Solving Linear Diophantine Equations

Proving Fermat’s Little Theorem

Using Fermat’s Little Theorem to Test Primality

Congruence Arithmetic and Fast Powering Algorithm

The Fundamental Theorem of Arithmetic

Euclid’s Lemma

The Euclidean Algorithm

The Division Algorithm