Versions of the Chinese remainder theorem

This post is the second post in a series of posts on the Chinese remainder theorem (CRT). The previous post sets up the scene by discussing the fundamental theorem of arithmetic. In this post, we derive the various versions of CRT from a lemma (Lemma A below) that is equivalent to the fundamental theorem of arithmetic.

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

____________________________________________________________________________

The starting point

Lemma A and Theorem B are discussed in the previous post. Lemma A is shown to be equivalent to the fundamental theorem of arithmetic. Lemma A makes CRT possible.

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

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. Every positive integer $n>1$ can be written as a product of prime numbers and that this product (called a factorization) is unique.

In this post, we start from Lemma A and derive several versions of CRT. First, let’s look at a consequence of Lemma A.

Lemma C
Let $m_1,m_2,\cdots,m_t$ be positive integers that are pairwise relatively prime. Let $M=m_1 \cdot m_2 \cdots m_t$. Then for any integer $n$,

$M \lvert n$ if and only if $m_i \ \lvert \ n$ for each $i$.

Proof
The direction $\rightarrow$ is clear.

We show the direction $\leftarrow$. Suppose that for each $i$, $m_i \lvert n$. Then $n=m_1 \cdot r_1$ for some integer $r_1$. Note that $m_2 \lvert n=m_1 \cdot r_1$. By Lemma 1, $m_2 \lvert r_1$. We can write $n=m_1 \cdot m_2 \cdot r_2$ for some integer $r_2$. Continue the same argument, it follows that $n=m_1 \cdot m_2 \cdots m_t \cdot r$ for some integer $r$. This means that $M \lvert n$. $\square$

____________________________________________________________________________

The Chinese remainder theorem

The following are several statements of the Chinese remainder theorem. The first version is a re-statement of Lemma C using congruence notation.

Theorem D (Chinese Remainder Theorem)
Let $m_1,m_2,\cdots,m_t$ be positive integers that are pairwise relatively prime. Let $M=m_1 \cdot m_2 \cdots m_t$. Then for any integers $a$ and $b$,

$a \equiv b \ (\text{mod} \ M)$ if and only if $a \equiv b \ (\text{mod} \ m_i)$ for each $i$.

The proof of Lemma C would take care of Theorem D. Note that $a \equiv b \ (\text{mod} \ y)$ means that $y \lvert (a-b)$.

Theorem E (Chinese Remainder Theorem)
Let $m_1,m_2,\cdots,m_t$ be positive integers that are pairwise relatively prime. Let $M=m_1 \cdot m_2 \cdots m_t$. Then for any integers $a$ and $b$,

the integer $x_0$ is a solution of the linear congruence equation $a \cdot x \equiv b \ (\text{mod} \ M)$ if and only if the integer $x_0$ is satisfies simultaneously the following linear congruence equations:

$a \cdot x \equiv b \ (\text{mod} \ m_1)$

$a \cdot x \equiv b \ (\text{mod} \ m_2)$

$\cdots$

$a \cdot x \equiv b \ (\text{mod} \ m_t)$

Proof
By Theorem D, $a \cdot x_0 \equiv b \ (\text{mod} \ M)$ if and only if $a \cdot x_0 \equiv b \ (\text{mod} \ m_i)$ for each $i$. $\square$

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

Proof
First, a solution is produced. Then it is shown that the solution is unique. To produce the solution, the first step is solve each equation individually. Because $a_i$ and $m_i$ are relatively prime, the equation $a_i \ x \equiv b_i \ (\text{mod} \ m_i)$ has a unique solution $c_i$. Thus $a_i \ c_i \equiv b_i \ (\text{mod} \ m_i)$ for each $i$.

Next, let $N_i$ be the product of all the moduli $m_j$ where $j \ne i$. Note that $N_i$ and $m_i$ are still relatively prime. There exists a unique $n_i$ such that $N_i \ n_i \equiv 1 \ (\text{mod} \ m_i)$. In other words, $n_i$ is the multiplicative inverse of $N_i$ modulo $m_i$.

The proposed solution is $x_0=c_1 \cdot N_1 \cdot n_1+c_2 \cdot N_2 \cdot n_2+\cdots+c_t \cdot N_t \cdot n_t$. The following shows that $x_0$ is the solution to each equation.

\displaystyle \begin{aligned} a_i x_0 &\equiv a_i (c_1 \cdot N_1 \cdot n_1+c_2 \cdot N_2 \cdot n_2+\cdots+c_i \cdot N_i \cdot n_i+ \cdots +c_t \cdot N_t \cdot n_t) \\&\equiv a_i \cdot c_1 \cdot N_1 \cdot n_1+a_i \cdot c_2 \cdot N_2 \cdot n_2+\cdots+a_i \cdot c_i \cdot N_i \cdot n_i +\cdots + a_i \cdot c_t \cdot N_t \cdot n_t \\&\equiv a_i \cdot c_i \cdot N_i \cdot n_i \\&\equiv a_i \cdot c_i \\&\equiv b_i \ (\text{mod} \ m_i) \end{aligned}

All the terms containing $N_j$ with $j \ne i$ drop out since $N_j$ contains $m_i$ as a factor. The product $N_i \cdot n_i$ drops out since it is congruent to 1 modulo $m_i$. Then $a_i \cdot c_i$ is congruent to $b_i$ modulo $m_i$.

To show the uniqueness, suppose $x$ is also a solution to the system of linear congruence equations. Then $a_i \ x \equiv a_i \ x_0 \ (\text{mod} \ m_i)$ for each $i$. Multiplying the inverse of $a_i$ on both sides, we have and $x \equiv x_0 \ (\text{mod} \ m_i)$ for each $i$. By Theorem E, $x \equiv x_0 \ (\text{mod} \ m)$. $\square$

Theorem G (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$. For any sequence of integers $c_1,c_2,\cdots,c_t$, the following system of linear congruence equations

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

has a unique solution modulo $m=m_1 \cdot m_2 \cdots m_t$.

Proof
This follows directly from Theorem F. $\square$

____________________________________________________________________________

To complete the loop

To complete the loop, we show that Theorem G implies Theorem D. Suppose that $a \equiv b \ (\text{mod} \ m_i)$ for each $i$. Consider the following system of congruence equations:

$x \equiv b \ (\text{mod} \ m_1)$

$x \equiv b \ (\text{mod} \ m_2)$

$\cdots$

$x \equiv b \ (\text{mod} \ m_t)$

The number $b$ is clearly a solution to this system of equations. By Theorem G, this solution is unique. So any other solution to this system must be congruent to $b$ modulo $m=m_1 \cdot m_2 \cdots m_t$. By assumption, $a$ is a solution to the system. So $a \equiv b \ (\text{mod} \ m)$. $\square$

The loop $D \rightarrow E \rightarrow F \rightarrow G \rightarrow D$ is now complete. Theorem G is the usual statement of CRT. Based on the loop, any one of the theorems can be called the Chinese remainder theorem. Note that the loop by itself does not establish the Chinese remainder theorem. For that to happen, some condition outside the loop must imply one condition in the loop. The above discussion shows that the fundamental theorem of arithmetic (in the form of Lemma A) implies Theorem D.

____________________________________________________________________________

CRT is a versatile tool and is found to be useful in many areas of mathematics. One approach in applying CRT is that of a divide and conquer idea. The original problem is divided into smaller problems, which can be solved independently of one another. At the end, the results of the smaller problems are combined to form the solution of the original problem. For example, in solving a linear congruence equation $a \cdot x \equiv b \ (\text{mod} \ M)$ for a large modulus $M$, CRT in the form of Theorem E suggests that the problem can be broken up into a set of linear congruence equations with smaller moduli. For this reason, CRT is important in computing (both theory and applications), especially in computing intensive areas such as coding theory and cryptography.

In the next posts, we discuss two algorithms for solving CRT simultaneous systems of equations and look at a few applications.

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

The Fundamental Theorem of Arithmetic

This post discusses and proves the fundamental theorem of arithmetic.

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

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

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

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

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

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

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

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

___________________________________________________________________________________________________________________

The Fundamental Theorem of Arithmetic

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

Lemma 1

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

Proof

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

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

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

Lemma 2

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

Proof

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

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

Euclid’s Lemma

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

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

Lemma 3

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

Proof

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

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

Fundamental Theorem of Arithmetic

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

Proof

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

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

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

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

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

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

Comment

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

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

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

___________________________________________________________________________________________________________________

Reference

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

___________________________________________________________________________________________________________________

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

Euclid’s Lemma

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

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

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

___________________________________________________________________________________________________________________

Extended Euclidean Algorithm

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

The extended Euclidean algorithm is discussed in this post.

___________________________________________________________________________________________________________________

Lemma 1

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

Proof of Lemma 1

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

$abx+dby=b$

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

___________________________________________________________________________________________________________________

Euclid’s Lemma

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

Proof

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

Comment

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

___________________________________________________________________________________________________________________

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

The Division Algorithm

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 .

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

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

___________________________________________________________________________________________________________________

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