# Section2.2The Division Algorithm¶ permalink

An application of the Principle of Well-Ordering that we will use often is the division algorithm.

##### Proof

Let $a$ and $b$ be integers. If $b = ak$ for some integer $k$, we write $a \mid b$. An integer $d$ is called a common divisor of $a$ and $b$ if $d \mid a$ and $d \mid b$. The greatest common divisor of integers $a$ and $b$ is a positive integer $d$ such that $d$ is a common divisor of $a$ and $b$ and if $d'$ is any other common divisor of $a$ and $b$, then $d' \mid d$. We write $d = \gcd(a, b)$; for example, $\gcd( 24, 36) = 12$ and $\gcd(120, 102) = 6$. We say that two integers $a$ and $b$ are relatively prime if $\gcd( a, b ) = 1$.

# SubsectionThe Euclidean Algorithm¶ permalink

Among other things, Theorem 2.10 allows us to compute the greatest common divisor of two integers.

##### Example2.12

Let us compute the greatest common divisor of $945$ and $2415$. First observe that \begin{align*} 2415 & = 945 \cdot 2 + 525\\ 945 & = 525 \cdot 1 + 420\\ 525 & = 420 \cdot 1 + 105\\ 420 & = 105 \cdot 4 + 0. \end{align*} Reversing our steps, 105 divides 420, 105 divides 525, 105 divides 945, and 105 divides 2415. Hence, 105 divides both 945 and 2415. If $d$ were another common divisor of 945 and 2415, then $d$ would also have to divide 105. Therefore, $\gcd( 945, 2415 ) = 105$.

If we work backward through the above sequence of equations, we can also obtain numbers $r$ and $s$ such that $945 r + 2415 s = 105$. Observe that \begin{align*} 105 & = 525 + (-1) \cdot 420\\ & = 525 + (-1) \cdot [945 + (-1) \cdot 525]\\ & = 2 \cdot 525 + (-1) \cdot 945\\ & = 2 \cdot [2415 + (-2) \cdot 945] + (-1) \cdot 945\\ & = 2 \cdot 2415 + (-5) \cdot 945. \end{align*} So $r = -5$ and $s= 2$. Notice that $r$ and $s$ are not unique, since $r = 41$ and $s = -16$ would also work.

To compute $\gcd(a,b) = d$, we are using repeated divisions to obtain a decreasing sequence of positive integers $r_1 \gt r_2 \gt \cdots \gt r_n = d$; that is, \begin{align*} b & = a q_1 + r_1\\ a & = r_1 q_2 + r_2\\ r_1 & = r_2 q_3 + r_3\\ & \vdots \\ r_{n - 2} & = r_{n - 1} q_{n} + r_{n}\\ r_{n - 1} & = r_n q_{n + 1}. \end{align*} To find $r$ and $s$ such that $ar + bs = d$, we begin with this last equation and substitute results obtained from the previous equations: \begin{align*} d & = r_n\\ & = r_{n - 2} - r_{n - 1} q_n\\ & = r_{n - 2} - q_n( r_{n - 3} - q_{n - 1} r_{n - 2} )\\ & = -q_n r_{n - 3} + ( 1+ q_n q_{n-1} ) r_{n - 2} \\ & \vdots \\ & = ra + sb. \end{align*} The algorithm that we have just used to find the greatest common divisor $d$ of two integers $a$ and $b$ and to write $d$ as the linear combination of $a$ and $b$ is known as the Euclidean algorithm.

# SubsectionPrime Numbers¶ permalink

Let $p$ be an integer such that $p \gt 1$. We say that $p$ is a prime number, or simply $p$ is prime, if the only positive numbers that divide $p$ are 1 and $p$ itself. An integer $n \gt 1$ that is not prime is said to be composite.

# SubsectionHistorical Note¶ permalink

Prime numbers were first studied by the ancient Greeks. Two important results from antiquity are Euclid's proof that an infinite number of primes exist and the Sieve of Eratosthenes, a method of computing all of the prime numbers less than a fixed positive integer $n$. One problem in number theory is to find a function $f$ such that $f(n)$ is prime for each integer $n$. Pierre Fermat (1601?–1665) conjectured that $2^{2^n} + 1$ was prime for all $n$, but later it was shown by Leonhard Euler (1707–1783) that \begin{equation*}2^{2^5} + 1 = \text{4,294,967,297}\end{equation*} is a composite number. One of the many unproven conjectures about prime numbers is Goldbach's Conjecture. In a letter to Euler in 1742, Christian Goldbach stated the conjecture that every even integer with the exception of 2 seemed to be the sum of two primes: $4 = 2 + 2$, $6 = 3 + 3$, $8 =3 + 5$, $\ldots$. Although the conjecture has been verified for the numbers up through $4 \times 10^{18}$, it has yet to be proven in general. Since prime numbers play an important role in public key cryptography, there is currently a great deal of interest in determining whether or not a large number is prime.