How to Chinese remainder, part 1

This is the third post in a series of posts on the Chinese remainder theorem (first post and second post). In this and the next post, we highlight two algorithms for obtaining the solution of a system of linear congruence equations. The Chinese remainder theorem guarantees that, under certain condition, any system of linear congruence equations has a unique solution (unique modulo the product of all the moduli of the congruence equations). The theorem is usually abbreviated as CRT. Even though the solution is unique, there are more than one way to solve systems of simultaneous linear congruence equations. In this post, we extract an algorithm from a constructive proof of CRT that is found in many textbooks (used here in this previous post). In the next post, we present another algorithm for solving systems of linear congruence equations.

The statement of CRT only guarantees the existence of a solution and does not show how to derive the unique solution. In many situations, it is sufficient to know that solutions exist (e.g. using CRT to prove theorems). In other situations where actual solutions are sought, we need more than the statement of CRT. In these situations, an algorithm is needed to actually find a solution. It is critical to have an algorithm for solving CRT problems, especially in computer implementation.

The algorithm discussed here is to solve the following is the version of the Chinese remainder theorem. This version has been shown to be equivalent to several other versions in this previous post.

Theorem F (Chinese Remainder Theorem)
Suppose m_1,m_2,\cdots,m_t are positive integers that are pairwise relatively prime. Let m=m_1 \cdot m_2 \cdots m_t. Suppose we have the following system of linear congruence equations

    a_1 \ x \equiv b_1 \ (\text{mod} \ m_1)

    a_2 \ x \equiv b_2 \ (\text{mod} \ m_2)

      \cdots

    a_{t-1} \  x \equiv b_{t-1} \ (\text{mod} \ m_{t-1})

    a_t \  x \equiv b_t \ (\text{mod} \ m_t)

such that each of the linear congruence equations has a unique solution, i.e. for each i, a_i and m_i are relatively prime. Then the system of linear congruence equations has a unique solution modulo m=m_1 \cdot m_2 \cdots m_t.

____________________________________________________________________________

Examples

We first start with two examples.

Example 1
Solve the following system of linear congruence equations.

    x \equiv 3 \ (\text{mod} \ 17)

    x \equiv 10 \ (\text{mod} \ 21)

    x \equiv 15 \ (\text{mod} \ 29)

Both 17 and 29 are prime. The factors of 21 are 3 and 7. The three moduli are pairwise relatively prime (i.e. no two of which have a common factor other than 1). Thus CRT implies that the three equations have a solution x_0. The solution is unique modulo 10353 = 17 x 21 x 29. This means that if y is another solution, then y\equiv x_0 \ (\text{mod} \ 10353).

The solution is x_0=3 \cdot 609 \cdot 11+10 \cdot 493 \cdot 19+15 \cdot 357 \cdot 13 \ (\text{mod} \ 10353) where

    609=21 \cdot 29 and 609 \cdot 11 \equiv 1 \ (\text{mod} \ 17)

    493=17 \cdot 29 and 493 \cdot 19 \equiv 1 \ (\text{mod} \ 21)

    357=17 \cdot 21 and 357 \cdot 13 \equiv 1 \ (\text{mod} \ 29)

The number 609 is the product of the remaining moduli (all the modulo not 17). Because 609 and the modulus 17 are relatively prime, the number 609 has a multiplicative inverse modulo 17. The multiplicative inverse is 11, found using the extended Euclidean algorithm. The other two pairs “493 and 19” and “357 and 13” are found similarly. Thus the solution x_0 is the sum of three numbers. The first is 3 x 609 x 11, where 3 is the solution to the first equation, and 609 and 11 multiplicative inverses to each other modulo 17. The other two numbers 10 x 493 x 19 and 15 x 357 x 13 are obtained similarly.

After reducing modulo 10353, the solution is

    \displaystyle \begin{aligned} x_0&\equiv 3 \cdot 609 \cdot 11+10 \cdot 493 \cdot 19+15 \cdot 357 \cdot 13 \ (\text{mod} \ 10353) \\&\equiv 20097+93670+69615 \ (\text{mod} \ 10353) \\&\equiv 9744+493+7497 \ (\text{mod} \ 10353) \\&\equiv 17734 \ (\text{mod} \ 10353) \\&\equiv 7381 \ (\text{mod} \ 10353)  \end{aligned}

The algorithm demonstrated here requires the computation of three multiplicative inverses. One try and true method for finding multiplicative inverse in the extended Euclidean algorithm (i.e. applying the Euclidean algorithm and then work backward). We demonstrate how to solve 609y \equiv 1 \ (\text{mod} \ 17). To this end, solve the linear diophantine equation 609y+17z=1. Then work backward.

    \displaystyle \begin{aligned} &609=17 \cdot 35+1 \\&17=14 \cdot 1+3 \\&14=3 \cdot 4+2 \\&3=2 \cdot 1+1 \\&2=1 \cdot 2+0 \\&\text{ } \\&\text{ } \end{aligned}        \ \ \ \ \ \ \ \ \   \displaystyle \begin{aligned} 1&=3-2 \\&=3-(14-3 \cdot 4) \\&=14(-1)+3(5) \\&=14(-1)+(17-14)5 \\&=17(5)+14(-6) \\&=17(5)+(609-17 \cdot 35) (-6) \\&=609(-6)+17(215) \end{aligned}

The calculation on the left shows the repeated applications of divisions to show that (609,17)=1. The calculation on the right works backward to solve 609y+17z=1. The solution is y=-6, the least residue of which is y=11. \square

Example 2
Solve the following system of linear congruence equations.

    3 \ x \equiv 1 \ (\text{mod} \ 5)

    4 \ x \equiv 6 \ (\text{mod} \ 14)

    5 \ x \equiv 11 \ (\text{mod} \ 3)

The algorithm used in Example 1 works here. The only difference is that each equation needs to be solved individually. The numbers here are small. The equations can be solved by inspection. Otherwise, each equation can also be solved by solving an appropriate linear diophantine equation (as discussed here). The following are the solutions to the above equations (individually).

    x \equiv 2 \ (\text{mod} \ 5)

    x \equiv 5 \ (\text{mod} \ 14)

    x \equiv 1 \ (\text{mod} \ 3)

The problem is then to solve the system of the above 3 linear congruence equations. The solution is x_0=2 \cdot 42 \cdot 8+5 \cdot 15 \cdot 1+1 \cdot 70 \cdot 1 where:

    42=14 \cdot 3 and 42 \cdot 8 \equiv 1 \ (\text{mod} \ 5)

    15=5 \cdot 3 and 15 \cdot 1 \equiv 1 \ (\text{mod} \ 14)

    70=5 \cdot 14 and 70 \cdot 1 \equiv 1 \ (\text{mod} \ 3)

The above calculation requires solving three linear congruence equations individually and finding three multiplicative inverses. Both tasks can be done using the extended Euclidean algorithm. After further reduction modulo 210, the unique solution is:

    \displaystyle \begin{aligned} x_0&\equiv 2 \cdot 42 \cdot 8+5 \cdot 15 \cdot 1+1 \cdot 70 \cdot 1 \ (\text{mod} \ 210) \\&\equiv 672+75+70 \ (\text{mod} \ 210) \\&\equiv 42+75+70 \ (\text{mod} \ 210) \\&\equiv 187 \ (\text{mod} \ 210)   \end{aligned}

The above gives the unique solution to the given system of linear equations. \square

____________________________________________________________________________

An algorithm for CRT

Now we describe the algorithm that is described by the above two examples. Suppose that the following system of equations such that the moduli m1,m_2,\cdots,m_t are pairwise relatively prime and such that each equation by itself has a unique solution, i.e. a_i and m_i are relatively prime for each i.

    a_1 \ x \equiv b_1 \ (\text{mod} \ m_1)

    a_2 \ x \equiv b_2 \ (\text{mod} \ m_2)

      \cdots

    a_{t-1} \  x \equiv b_{t-1} \ (\text{mod} \ m_{t-1})

    a_t \  x \equiv b_t \ (\text{mod} \ m_t)

The following three steps describe how to obtain the solution to this system of equations.

Step 1
Solve each equation a_i \ x \equiv b_i \ (\text{mod} \ m_i) individually to obtain the solution x \equiv c_i \ (\text{mod} \ m_i). The original system is equivalent to the following equivalent system of equations, i.e. any solution to one system is the solution to the other.

    x \equiv c_1 \ (\text{mod} \ m_1)

    x \equiv c_2 \ (\text{mod} \ m_2)

      \cdots

    x \equiv c_{t-1} \ (\text{mod} \ m_{t-1})

    x \equiv c_t \ (\text{mod} \ m_t)

Step 2
For each i, let n_i be the product of all moduli m_j where j \ne i. Each n_i is relatively prime to m_i. Thus n_i has a multiplicative inverse modulo m_i. Equivalently solve the following equations individually.

    n_1 \ y \equiv 1 \ (\text{mod} \ m_1)

    n_2 \ y \equiv 1 \ (\text{mod} \ m_2)

      \cdots

    n_{t-1} \  y \equiv 1 \ (\text{mod} \ m_{t-1})

    n_t \  y \equiv 1 \ (\text{mod} \ m_t)

For each i, let w_i be the inverse of n_i modulo m_i, i.e. n_i^{-1} \equiv w_i \ (\text{mod} \ m_i).

Step 3
The solution is given by

    x_0 \equiv c_1 \cdot n_1 \cdot w_1+c_2 \cdot n_2 \cdot w_2+\cdots+c_t \cdot n_t \cdot w_t \ (\text{mod} \ m)

where m=m_1 \cdot m_2 \cdots m_t.

Let’s look at what the algorithm entails computationally. Step 1 requires solving a set of linear congruence equations individually (equivalently, solving linear diophantine equations individually), unless the equations are given in the form x \equiv c_i \ (\text{mod} \ m_i). The extended Euclidean algorithm is an excellent approach, especially in computer implementation.

Step 2 involves finding multiplicative inverses of the numbers n_i. The extended Euclidean algorithm is also an excellent approach, especially in computer implementation.

Step 3 is to gather up the results from Step 1 and Step 2. The computation here is to reduce modulo m=m_1 \cdot m_2 \cdots m_t.

____________________________________________________________________________

Why does the algorithm work?

The number x_0 \equiv c_1 \cdot n_1 \cdot w_1+c_2 \cdot n_2 \cdot w_2+\cdots+c_t \cdot n_t \cdot w_t \ (\text{mod} \ m) is a solution to each of the equations in the given system of linear congruence equations. To see that x_0 is a solution to the equation a_1 \ x \equiv b_1 \ (\text{mod} \ m_1), note that:

    \displaystyle \begin{aligned} a_1 \cdot x_0&\equiv a_1 \cdot (c_1 \cdot n_1 \cdot w_1+c_2 \cdot n_2 \cdot w_2+\cdots+c_t \cdot n_t \cdot w_t) \\&\equiv a_1 \cdot c_1 \cdot n_1 \cdot w_1+a_1 \cdot c_2 \cdot n_2 \cdot w_2+\cdots+a_1 \cdot c_t \cdot n_t \cdot w_t  \\&\equiv a_1 \cdot c_1 \cdot n_1 \cdot w_1 \\&\equiv a_1 \cdot c_1 \\&\equiv b_1 \ (\text{mod} \ m_1) \end{aligned}

In the above derivation, all the terms containing n_j with j \ne 1 drop out. This is because n_j has m_1 as a factor. The product n_1 \cdot w_1 drops out since w_1 is the multiplicative inverse if n_1 modulo m_1. Finally a_1 \cdot c_1 \equiv b_1 \ (\text{mod} \ m_1) since c_1 is a solution of the equation a_1 \ x \equiv b_1 \ (\text{mod} \ m_1). By the same reasoning, x_0 is the solution to all the other equations in the system.

To see that the solution x_0 is unique, see the proof in this previous post.

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

Another look at the fundamental theorem of arithmetic

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

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

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

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

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

____________________________________________________________________________

The lemma

The starting point is the following lemma.

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

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

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

____________________________________________________________________________

The fundamental theorem of arithmetic

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

Theorem B
The following conditions are equivalent:

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

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

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

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

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

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

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

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

Solving Linear Congruences

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.

  1. The linear congruence ax \equiv b \ (\text{mod} \ m) has a solution.
  2. The linear Diophantine equation ax+my=b has a solution.
  3. 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:

  1. The following d integers satisfy the given linear congruence equation and are distinct congruent modulo m.
  2. \text{ }

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

  3. 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.
  4. \text{ }

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

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

    1638x+357y=819

    255x - 2261y = 1003

    78x + 195y=45

    374x+285y=49

    21x+10y+25z=26

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

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

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

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

___________________________________________________________________________________________________________________

How to Find Solutions

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

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

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

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

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

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

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

Lemma 1

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

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

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

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

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

Lemma 2

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

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

where k is any integer.

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

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

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

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

Theorem 3

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

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

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

where k is any integer.

Proof of Theorem 3

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

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

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

    ax_0+by_0=c

    ax_1+by_1=c

Rearranging and dividing by d, we have the following.

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

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

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

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

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

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

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

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

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

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

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

where k is any integer.

___________________________________________________________________________________________________________________

Recap

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

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

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

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

___________________________________________________________________________________________________________________

More Examples

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

    2261=8 \cdot 255+221

    255=1 \cdot 221+34

    221=6 \cdot 34+17

    34=2 \cdot 17+0

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

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

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

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

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

________________________________

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

________________________________

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

    374=1 \cdot 285+89

    285=3 \cdot 89+18

    89=4 \cdot 18+17

    18=1 \cdot 17+1

    17=17 \cdot 1+0

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

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

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

    x=-784+285k

    y=1029-374k

for any integer k.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

The Fundamental Theorem of Arithmetic

This post discusses and proves the fundamental theorem of arithmetic.

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

    a=\text{2,424,833}

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

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

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

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

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

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

___________________________________________________________________________________________________________________

The Fundamental Theorem of Arithmetic

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

Lemma 1

Any integer n>1 has a prime divisor.

Proof

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

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

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

Lemma 2

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

Proof

We prove by induction. The lemma is certainly true for n=2. Suppose the lemma is true for all positive integers k where k<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

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

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Euclid’s Lemma

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

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

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

___________________________________________________________________________________________________________________

Extended Euclidean Algorithm

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

The extended Euclidean algorithm is discussed in this post.

___________________________________________________________________________________________________________________

Lemma 1

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

Proof of Lemma 1

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

    abx+dby=b

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

___________________________________________________________________________________________________________________

Euclid’s Lemma

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

Proof

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

Comment

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

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

The Euclidean Algorithm

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

        \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots

        \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
___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}