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

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. 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=q_1 \cdot r_0+r_1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 0 \le r_1

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

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

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

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

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

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

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

# A first look at Dirichlet’s theorem

As a result of Euclid’s proof that there are infinitely many prime numbers (dated back to the time around 300 BC), we know that there are infinitely many prime numbers dispersed among the odd integers $1, 3, 5, 7, 9, \cdots$. It turns out that when you divide the odd integers into 2 halves (see the following two sequences), each half also contains infinitely many prime numbers:

$1, 5, 9, 13, 17, 21, 25 \cdots$

$3, 7, 11, 15, 19, 23, 27 \cdots$

So does each of the following sequences:

$5, 11, 17, 23, 29, 35, 41 \cdots$

$7, 37, 67, 97, 127, 157, 187 \cdots$

These examples provides a first look at the Dirichlet’s theorem on arithmetic progressions.
___________________________________________________________________________________________________________________

The Dirichlet’s Theorem on Arithmetic Progressions

An arithmetic progression is a sequence of numbers where each term is obtained by adding a constant to the previous term. The constant is called the common difference. If the first term is $a$ and the common difference is $d>0$, the following is an arithmetic progression:

$\displaystyle a, a+d, a+2d, a+3d, \cdots$

The Dirichlet’s theorem states that an arithmetic progression contains infinitely many prime numbers if the first term $a$ and the common difference $d$ are relatively prime (i.e. the only common divisor of $a$ and $d$ is 1).

The above 4 sequences of integers are all arithmetic progressions where the first term and the common difference are relatively prime. Take the third example $5, 11, 17, 23, 29, 35, 41 \cdots$. The common difference is 6 and the first term is 5, which are relatively prime. By the Dirichlet’s theorem, we can be confident that this sequence contains infinitely many prime numbers. Note that not all the terms are prime (e.g. 35). So the prime numbers in an arithmetic progression do not need to be consecutive. In fact, even if an arithmetic progression contains infinitely many primes, there will always be infinitely many terms that are not prime.

Note that in the third example, the first 5 terms are primes ($5, 11, 17, 23, 29$) but the sixth term is not a prime. Thus $5, 11, 17, 23, 29$ is a finite arithmetic progression of length 5 consisting entirely of primes. The first 6 terms $7, 37, 67, 97, 127, 157$ in the fourth example is an arithmetic progression of length 6 consisting of entirely of primes.

It is a well known recent result that the prime numbers contains finite arithmetic progressions of any length. This result is known as the Green-Tao theorem and was proved by Ben Green and Terence Tao in 2004.

For a more detailed discussion of the Dirichlet’s theorem, see the Wikipedia entry on Dirichlet’s theorem on arithmetic progressions.

___________________________________________________________________________________________________________________

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

# Euclid’s Proof of the Infinitude of Primes

The oldest known proof that there are infinite number of primes is the one that is due to Euclid (around 300 BC). It is probably the most accessible. So I start the blog by stating this proof.

________________________________________________________

Theorem. There are infinitely many prime numbers.

The strategy is to show that given a finite list of prime numbers $\left\{p_1, p_2, \cdots, p_n \right\}$, we can always find another prime number not on the list.

Let $n=p_1 \times p_2 \times \cdots \times p_n$. Let $p$ be a prime divisor of $n+1$. If $p$ is on the list $\left\{p_1, p_2, \cdots, p_n \right\}$, then $p$ would divide both $n+1$ and $n$. This means that $p$ would divide 1 (the difference of $n$ and $n+1$). This is impossible. So $p$ must a prime number not on the original list. Hence there must be infinitely many prime numbers.

________________________________________________________

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

$\text{ }$