<section xml:id="section-division-algorithm">
<title>The Division Algorithm</title>
<introduction>
<p>
An application of the Principle of Well-Ordering that we will use often is the division algorithm.
</p>
<theorem xml:id="theorem-integers-division_algorithm">
<title>Division Algorithm</title>
<idx><h>Division algorithm</h><h>for integers</h></idx>
<statement>
<p>
Let <m>a</m> and <m>b</m> be integers, with <m>b \gt 0</m>.
Then there exist unique integers <m>q</m> and <m>r</m> such that
<me>
a = bq + r
</me>
where <m>0 \leq r \lt b</m>.
</p>
</statement>
<proof>
<p>
This is a perfect example of the existence-and-uniqueness type of proof.
We must first prove that the numbers <m>q</m> and <m>r</m> actually exist.
Then we must show that if <m>q'</m> and <m>r'</m> are two other such numbers,
then <m>q = q'</m> and <m>r = r'</m>.
</p>
<p>
<em>Existence of <m>q</m> and <m>r</m>.</em> Let
<me>
S = \{ a - bk : k \in {\mathbb Z} \text{ and } a - bk \geq 0 \}
</me>.
If <m>0 \in S</m>, then <m>b</m> divides <m>a</m>,
and we can let <m>q = a/b</m> and <m>r = 0</m>.
If <m>0 \notin S</m>, we can use the Well-Ordering Principle.
We must first show that <m>S</m> is nonempty.
If <m>a \gt 0</m>, then <m>a - b \cdot 0 \in S</m>.
If <m>a \lt 0</m>, then <m>a - b(2a) = a(1 - 2b) \in S</m>.
In either case <m>S \neq \emptyset</m>.
By the Well-Ordering Principle,
<m>S</m> must have a smallest member, say <m>r = a - bq</m>.
Therefore, <m>a = bq + r</m>, <m>r \geq 0</m>.
We now show that <m>r \lt b</m>.
Suppose that <m>r \gt b</m>.
Then
<me>
a - b(q + 1)= a - bq - b = r - b \gt 0
</me>.
In this case we would have <m>a - b(q + 1)</m> in the set <m>S</m>.
But then <m>a - b(q + 1) \lt a - bq</m>,
which would contradict the fact that
<m>r = a - bq</m> is the smallest member of <m>S</m>.
So <m>r \leq b</m>.
Since <m>0 \notin S</m>, <m>r \neq b</m> and so <m>r \lt b</m>.
</p>
<p>
<em>Uniqueness of <m>q</m> and <m>r</m>.</em>
Suppose there exist integers <m>r</m>, <m>r'</m>,
<m>q</m>, and <m>q'</m> such that
<me>
a = bq + r, 0 \leq r \lt b \quad \text{and}\quad a = bq' + r', 0 \leq r' \lt b
</me>.
Then <m> bq + r = bq' + r'</m>.
Assume that <m>r' \geq r</m>.
From the last equation we have <m>b(q - q') = r' - r</m>;
therefore, <m>b</m> must divide <m>r' - r</m> and <m>0 \leq r'- r \leq r' \lt b</m>.
This is possible only if <m>r' - r = 0</m>.
Hence, <m>r = r'</m> and <m>q = q'</m>.
</p>
</proof>
</theorem>
<p>
Let <m>a</m> and <m>b</m> be integers.
If <m>b = ak</m> for some integer <m>k</m>, we write <m>a \mid b</m>.
An integer <m>d</m> is called a
<term>common divisor</term>
of <m>a</m> and <m>b</m> if <m>d \mid a</m> and <m>d \mid b</m>.
The <term>greatest common divisor</term><idx><h>Greatest common divisor</h><h>of two integers</h></idx> of integers <m>a</m> and <m>b</m> is a positive integer <m>d</m> such that <m>d</m> is a common divisor of <m>a</m> and <m>b</m> and if <m>d'</m> is any other common divisor of <m>a</m> and <m>b</m>,
then <m>d' \mid d</m>.
<notation>
<usage><m>a \mid b</m></usage>
<description><m>a</m> divides <m>b</m></description>
</notation>
<notation>
<usage><m>\gcd(a, b)</m></usage>
<description>greatest common divisor of <m>a</m> and <m>b</m></description>
</notation>
We write <m>d = \gcd(a, b)</m>;
for example,
<m>\gcd( 24, 36) = 12</m> and <m>\gcd(120, 102) = 6</m>.
We say that two integers <m>a</m> and <m>b</m> are
<term>relatively prime</term>
if <m>\gcd( a, b ) = 1</m>.
</p>
<theorem xml:id="theorem-integers-gcd">
<statement>
<p>
Let <m>a</m> and <m>b</m> be nonzero integers.
Then there exist integers <m>r</m> and <m>s</m> such that
<me>
\gcd( a, b) = ar + bs
</me>.
Furthermore,
the greatest common divisor of <m>a</m> and <m>b</m> is unique.
</p>
</statement>
<proof>
<p>
Let
<me>
S = \{ am + bn : m, n \in {\mathbb Z} \text{ and } am + bn \gt 0 \}
</me>.
Clearly, the set <m>S</m> is nonempty;
hence, by the Well-Ordering Principle <m>S</m> must have a smallest member,
say <m>d = ar + bs</m>.
We claim that <m>d = \gcd( a, b)</m>.
Write <m>a = dq + r'</m> where <m>0 \leq r' \lt d</m>.
If <m>r' \gt 0</m>, then
<md>
<mrow>r'& = a - dq</mrow>
<mrow>& = a - (ar + bs)q</mrow>
<mrow>& = a - arq - bsq</mrow>
<mrow>& = a( 1 - rq ) + b( -sq )</mrow>
</md>,
which is in <m>S</m>.
But this would contradict the fact that <m>d</m> is the smallest member of <m>S</m>.
Hence, <m>r' = 0</m> and <m>d</m> divides <m>a</m>.
A similar argument shows that <m>d</m> divides <m>b</m>.
Therefore, <m>d</m> is a common divisor of <m>a</m> and <m>b</m>.
</p>
<p>
Suppose that <m>d'</m> is another common divisor of <m>a</m> and <m>b</m>,
and we want to show that <m>d' \mid d</m>.
If we let <m>a = d'h</m> and <m>b = d'k</m>, then
<me>
d = ar + bs = d'hr + d'ks = d'(hr + ks)
</me>.
So <m>d'</m> must divide <m>d</m>.
Hence, <m>d</m> must be the unique greatest common divisor of <m>a</m> and <m>b</m>.
</p>
</proof>
</theorem>
<corollary xml:id="corollary-integers-coprime">
<statement>
<p>
Let <m>a</m> and <m>b</m> be two integers that are relatively prime.
Then there exist integers <m>r</m> and <m>s</m> such that <m>ar + bs = 1</m>.
</p>
</statement>
</corollary>
</introduction>
<subsection>
<title>The Euclidean Algorithm</title>
<p>
Among other things,
<xref ref="theorem-integers-gcd" /> allows us to compute the greatest common divisor of two integers.
</p>
<example xml:id="example-integers-gcd">
<title>Greatest Common Divisor of Two Integers</title>
<p>
Let us compute the greatest common divisor of <m>945</m> and <m>2415</m>.
First observe that
<md>
<mrow>2415 & = 945 \cdot 2 + 525</mrow>
<mrow>945 & = 525 \cdot 1 + 420</mrow>
<mrow>525 & = 420 \cdot 1 + 105</mrow>
<mrow>420 & = 105 \cdot 4 + 0</mrow>
</md>.
</p>
<p>
Reversing our steps, 105 divides 420, 105 divides 525, 105 divides 945, and 105 divides 2415.
Hence, 105 divides both 945 and 2415.
If <m>d</m> were another common divisor of 945 and 2415,
then <m>d</m> would also have to divide 105.
Therefore, <m>\gcd( 945, 2415 ) = 105</m>.
</p>
<p>
If we work backward through the above sequence of equations,
we can also obtain numbers <m>r</m> and <m>s</m> such that <m>945 r + 2415 s = 105</m>.
Observe that
<md>
<mrow>105 & = 525 + (-1) \cdot 420</mrow>
<mrow>& = 525 + (-1) \cdot [945 + (-1) \cdot 525]</mrow>
<mrow>& = 2 \cdot 525 + (-1) \cdot 945</mrow>
<mrow>& = 2 \cdot [2415 + (-2) \cdot 945] + (-1) \cdot 945</mrow>
<mrow>& = 2 \cdot 2415 + (-5) \cdot 945</mrow>
</md>.
</p>
<p>
So <m>r = -5</m> and <m>s= 2</m>.
Notice that <m>r</m> and <m>s</m> are not unique,
since <m>r = 41</m> and <m>s = -16</m> would also work.
</p>
</example>
<p>
To compute <m>\gcd(a,b) = d</m>,
we are using repeated divisions to obtain a decreasing sequence of positive integers <m>r_1 \gt r_2 \gt \cdots \gt r_n = d</m>; that is,
<md>
<mrow>b & = a q_1 + r_1</mrow>
<mrow>a & = r_1 q_2 + r_2</mrow>
<mrow>r_1 & = r_2 q_3 + r_3</mrow>
<mrow>& \vdots</mrow>
<mrow>r_{n - 2} & = r_{n - 1} q_{n} + r_{n}</mrow>
<mrow>r_{n - 1} & = r_n q_{n + 1}</mrow>
</md>.
</p>
<p>
To find <m>r</m> and <m>s</m> such that <m>ar + bs = d</m>,
we begin with this last equation and substitute results obtained from the previous equations:
<md>
<mrow>d & = r_n</mrow>
<mrow>& = r_{n - 2} - r_{n - 1} q_n</mrow>
<mrow>& = r_{n - 2} - q_n( r_{n - 3} - q_{n - 1} r_{n - 2} )</mrow>
<mrow>& = -q_n r_{n - 3} + ( 1+ q_n q_{n-1} ) r_{n - 2}</mrow>
<mrow>& \vdots</mrow>
<mrow>& = ra + sb</mrow>
</md>.
</p>
<p>
The algorithm that we have just used to find the greatest common divisor <m>d</m> of two integers <m>a</m> and <m>b</m> and to write <m>d</m> as the linear combination of <m>a</m> and <m>b</m> is known as the
<term>Euclidean algorithm</term>
<idx><h>Euclidean algorithm</h></idx>.
<idx><h>Algorithm</h><h>Euclidean</h></idx>
</p>
</subsection>
<subsection>
<title>Prime Numbers</title>
<p>
Let <m>p</m> be an integer such that <m>p \gt 1</m>.
We say that <m>p</m> is a <term>prime number</term>,
<idx><h>Prime integer</h></idx>
or simply <m>p</m> is <term>prime</term>,
if the only positive numbers that divide <m>p</m> are 1 and <m>p</m> itself.
An integer <m>n \gt 1</m> that is not prime is said to be <term>composite</term>.
<idx><h>Composite integer</h></idx>
</p>
<lemma xml:id="theorem-integers-prime-divisor">
<creator>Euclid</creator>
<statement>
<p>
Let <m>a</m> and <m>b</m> be integers and <m>p</m> be a prime number.
If <m>p \mid ab</m>, then either <m>p \mid a</m> or <m>p \mid b</m>.
</p>
</statement>
<proof>
<p>
Suppose that <m>p</m> does not divide <m>a</m>.
We must show that <m>p \mid b</m>.
Since <m>\gcd( a, p ) = 1</m>,
there exist integers <m>r</m> and <m>s</m> such that <m>ar + ps = 1</m>.
So
<me>
b = b(ar + ps) = (ab)r + p(bs)
</me>.
Since <m>p</m> divides both <m>ab</m> and itself,
<m>p</m> must divide <m>b = (ab)r + p(bs)</m>.
</p>
</proof>
</lemma>
<theorem xml:id="theorem-integers-infinite-primes">
<creator>Euclid</creator>
<statement>
<p>
There exist an infinite number of primes.
</p>
</statement>
<proof>
<p>
We will prove this theorem by contradiction.
Suppose that there are only a finite number of primes,
say <m>p_1, p_2, \ldots, p_n</m>.
Let <m>P = p_1 p_2 \cdots p_n + 1</m>.
Then <m>P</m> must be divisible by some <m>p_i</m> for <m>1 \leq i \leq n</m>.
In this case, <m>p_i</m> must divide
<m>P - p_1 p_2 \cdots p_n = 1</m>, which is a contradiction.
Hence, either <m>P</m> is prime or there exists an additional prime number
<m>p \neq p_i</m> that divides <m>P</m>.
</p>
</proof>
</theorem>
<theorem xml:id="theorem-fund-theorem-arithmetic">
<title>Fundamental Theorem of Arithmetic</title>
<idx><h>Fundamental Theorem</h><h>of Arithmetic</h></idx>
<statement>
<p>
Let <m>n</m> be an integer such that <m>n \gt 1</m>.
Then
<me>
n = p_1 p_2 \cdots p_k
</me>,
where <m>p_1, \ldots, p_k</m> are primes
(not necessarily distinct).
Furthermore, this factorization is unique; that is, if
<me>
n = q_1 q_2 \cdots q_l
</me>,
then <m>k = l</m> and the <m>q_i</m>'s are just the <m>p_i</m>'s rearranged.
</p>
</statement>
<proof>
<p>
<em>Uniqueness.</em> To show uniqueness we will use induction on <m>n</m>.
The theorem is certainly true for <m>n = 2</m> since in this case <m>n</m> is prime.
Now assume that the result holds for all integers <m>m</m> such that <m>1 \leq m \lt n</m>, and
<me>
n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l
</me>,
where <m>p_1 \leq p_2 \leq \cdots \leq p_k</m> and <m>q_1 \leq q_2 \leq \cdots \leq q_l</m>.
By <xref ref="theorem-integers-prime-divisor" />, <m>p_1 \mid q_i</m> for some
<m>i = 1, \ldots,
l</m> and <m>q_1 \mid p_j</m> for some <m>j = 1, \ldots, k</m>.
Since all of the <m>p_i</m>'s and <m>q_i</m>'s are prime,
<m>p_1 = q_i</m> and <m>q_1 = p_j</m>.
Hence, <m>p_1 = q_1</m> since <m>p_1 \leq p_j = q_1 \leq q_i = p_1</m>.
By the induction hypothesis,
<me>
n' = p_2 \cdots p_k = q_2 \cdots q_l
</me>
has a unique factorization.
Hence, <m>k = l</m> and <m>q_i = p_i</m> for <m>i = 1, \ldots, k</m>.
</p>
<p>
<em>Existence.</em> To show existence,
suppose that there is some integer that cannot be written as the product of primes.
Let <m>S</m> be the set of all such numbers.
By the Principle of Well-Ordering,
<m>S</m> has a smallest number, say <m>a</m>.
If the only positive factors of <m>a</m> are <m>a</m> and 1, then <m>a</m> is prime,
which is a contradiction.
Hence, <m>a = a_1 a_2</m> where
<m>1 \lt a_1 \lt a</m> and <m>1 \lt a_2 \lt a</m>.
Neither <m>a_1\in S</m> nor <m>a_2 \in S</m>,
since <m>a</m> is the smallest element in <m>S</m>.
So
<md>
<mrow>a_1 & = p_1 \cdots p_r</mrow>
<mrow>a_2 & = q_1 \cdots q_s</mrow>
</md>.
</p>
<p>
Therefore,
<me>
a = a_1 a_2 = p_1 \cdots p_r q_1 \cdots q_s
</me>.
So <m>a \notin S</m>, which is a contradiction.
</p>
</proof>
</theorem>
</subsection>
<subsection>
<title>Historical Note</title>
<p>
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 <m>n</m>.
One problem in number theory is to find a function <m>f</m> such that <m>f(n)</m> is prime for each integer <m>n</m>.
Pierre Fermat (1601?<ndash />1665) conjectured that
<m>2^{2^n} + 1</m> was prime for all <m>n</m>,
but later it was shown by Leonhard Euler (1707<ndash />1783) that
<me>
2^{2^5} + 1 = \text{4,294,967,297}
</me>
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:
<m>4 = 2 + 2</m>, <m>6 = 3 + 3</m>,
<m>8 =3 + 5</m>, <m>\ldots</m>.
Although the conjecture has been verified for the numbers up through <m>4 \times 10^{18}</m>,
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.
</p>
<xi:include xmlns="http://www.w3.org/2001/XInclude" href="./sage/integers-info.xml" />
</subsection>
</section>
Section 2.2 The Division Algorithm
View Source for section
An application of the Principle of Well-Ordering that we will use often is the division algorithm.
Theorem 2.2.1. Division Algorithm.
View Source for theorem
<theorem xml:id="theorem-integers-division_algorithm">
<title>Division Algorithm</title>
<idx><h>Division algorithm</h><h>for integers</h></idx>
<statement>
<p>
Let <m>a</m> and <m>b</m> be integers, with <m>b \gt 0</m>.
Then there exist unique integers <m>q</m> and <m>r</m> such that
<me>
a = bq + r
</me>
where <m>0 \leq r \lt b</m>.
</p>
</statement>
<proof>
<p>
This is a perfect example of the existence-and-uniqueness type of proof.
We must first prove that the numbers <m>q</m> and <m>r</m> actually exist.
Then we must show that if <m>q'</m> and <m>r'</m> are two other such numbers,
then <m>q = q'</m> and <m>r = r'</m>.
</p>
<p>
<em>Existence of <m>q</m> and <m>r</m>.</em> Let
<me>
S = \{ a - bk : k \in {\mathbb Z} \text{ and } a - bk \geq 0 \}
</me>.
If <m>0 \in S</m>, then <m>b</m> divides <m>a</m>,
and we can let <m>q = a/b</m> and <m>r = 0</m>.
If <m>0 \notin S</m>, we can use the Well-Ordering Principle.
We must first show that <m>S</m> is nonempty.
If <m>a \gt 0</m>, then <m>a - b \cdot 0 \in S</m>.
If <m>a \lt 0</m>, then <m>a - b(2a) = a(1 - 2b) \in S</m>.
In either case <m>S \neq \emptyset</m>.
By the Well-Ordering Principle,
<m>S</m> must have a smallest member, say <m>r = a - bq</m>.
Therefore, <m>a = bq + r</m>, <m>r \geq 0</m>.
We now show that <m>r \lt b</m>.
Suppose that <m>r \gt b</m>.
Then
<me>
a - b(q + 1)= a - bq - b = r - b \gt 0
</me>.
In this case we would have <m>a - b(q + 1)</m> in the set <m>S</m>.
But then <m>a - b(q + 1) \lt a - bq</m>,
which would contradict the fact that
<m>r = a - bq</m> is the smallest member of <m>S</m>.
So <m>r \leq b</m>.
Since <m>0 \notin S</m>, <m>r \neq b</m> and so <m>r \lt b</m>.
</p>
<p>
<em>Uniqueness of <m>q</m> and <m>r</m>.</em>
Suppose there exist integers <m>r</m>, <m>r'</m>,
<m>q</m>, and <m>q'</m> such that
<me>
a = bq + r, 0 \leq r \lt b \quad \text{and}\quad a = bq' + r', 0 \leq r' \lt b
</me>.
Then <m> bq + r = bq' + r'</m>.
Assume that <m>r' \geq r</m>.
From the last equation we have <m>b(q - q') = r' - r</m>;
therefore, <m>b</m> must divide <m>r' - r</m> and <m>0 \leq r'- r \leq r' \lt b</m>.
This is possible only if <m>r' - r = 0</m>.
Hence, <m>r = r'</m> and <m>q = q'</m>.
</p>
</proof>
</theorem>
Let \(a\) and \(b\) be integers, with \(b \gt 0\text{.}\) Then there exist unique integers \(q\) and \(r\) such that
\begin{equation*}
a = bq + r
\end{equation*}
where \(0 \leq r \lt b\text{.}\)
Proof.
View Source for proof
<proof>
<p>
This is a perfect example of the existence-and-uniqueness type of proof.
We must first prove that the numbers <m>q</m> and <m>r</m> actually exist.
Then we must show that if <m>q'</m> and <m>r'</m> are two other such numbers,
then <m>q = q'</m> and <m>r = r'</m>.
</p>
<p>
<em>Existence of <m>q</m> and <m>r</m>.</em> Let
<me>
S = \{ a - bk : k \in {\mathbb Z} \text{ and } a - bk \geq 0 \}
</me>.
If <m>0 \in S</m>, then <m>b</m> divides <m>a</m>,
and we can let <m>q = a/b</m> and <m>r = 0</m>.
If <m>0 \notin S</m>, we can use the Well-Ordering Principle.
We must first show that <m>S</m> is nonempty.
If <m>a \gt 0</m>, then <m>a - b \cdot 0 \in S</m>.
If <m>a \lt 0</m>, then <m>a - b(2a) = a(1 - 2b) \in S</m>.
In either case <m>S \neq \emptyset</m>.
By the Well-Ordering Principle,
<m>S</m> must have a smallest member, say <m>r = a - bq</m>.
Therefore, <m>a = bq + r</m>, <m>r \geq 0</m>.
We now show that <m>r \lt b</m>.
Suppose that <m>r \gt b</m>.
Then
<me>
a - b(q + 1)= a - bq - b = r - b \gt 0
</me>.
In this case we would have <m>a - b(q + 1)</m> in the set <m>S</m>.
But then <m>a - b(q + 1) \lt a - bq</m>,
which would contradict the fact that
<m>r = a - bq</m> is the smallest member of <m>S</m>.
So <m>r \leq b</m>.
Since <m>0 \notin S</m>, <m>r \neq b</m> and so <m>r \lt b</m>.
</p>
<p>
<em>Uniqueness of <m>q</m> and <m>r</m>.</em>
Suppose there exist integers <m>r</m>, <m>r'</m>,
<m>q</m>, and <m>q'</m> such that
<me>
a = bq + r, 0 \leq r \lt b \quad \text{and}\quad a = bq' + r', 0 \leq r' \lt b
</me>.
Then <m> bq + r = bq' + r'</m>.
Assume that <m>r' \geq r</m>.
From the last equation we have <m>b(q - q') = r' - r</m>;
therefore, <m>b</m> must divide <m>r' - r</m> and <m>0 \leq r'- r \leq r' \lt b</m>.
This is possible only if <m>r' - r = 0</m>.
Hence, <m>r = r'</m> and <m>q = q'</m>.
</p>
</proof>
This is a perfect example of the existence-and-uniqueness type of proof. We must first prove that the numbers \(q\) and \(r\) actually exist. Then we must show that if \(q'\) and \(r'\) are two other such numbers, then \(q = q'\) and \(r = r'\text{.}\)
Existence of \(q\) and \(r\text{.}\) Let
\begin{equation*}
S = \{ a - bk : k \in {\mathbb Z} \text{ and } a - bk \geq 0 \}\text{.}
\end{equation*}
If \(0 \in S\text{,}\) then \(b\) divides \(a\text{,}\) and we can let \(q = a/b\) and \(r = 0\text{.}\) If \(0 \notin S\text{,}\) we can use the Well-Ordering Principle. We must first show that \(S\) is nonempty. If \(a \gt 0\text{,}\) then \(a - b \cdot 0 \in S\text{.}\) If \(a \lt 0\text{,}\) then \(a - b(2a) = a(1 - 2b) \in S\text{.}\) In either case \(S \neq \emptyset\text{.}\) By the Well-Ordering Principle, \(S\) must have a smallest member, say \(r = a - bq\text{.}\) Therefore, \(a = bq + r\text{,}\) \(r \geq 0\text{.}\) We now show that \(r \lt b\text{.}\) Suppose that \(r \gt b\text{.}\) Then
\begin{equation*}
a - b(q + 1)= a - bq - b = r - b \gt 0\text{.}
\end{equation*}
In this case we would have \(a - b(q + 1)\) in the set \(S\text{.}\) But then \(a - b(q + 1) \lt a - bq\text{,}\) which would contradict the fact that \(r = a - bq\) is the smallest member of \(S\text{.}\) So \(r \leq b\text{.}\) Since \(0 \notin S\text{,}\) \(r \neq b\) and so \(r \lt b\text{.}\)
Uniqueness of \(q\) and \(r\text{.}\) Suppose there exist integers \(r\text{,}\) \(r'\text{,}\) \(q\text{,}\) and \(q'\) such that
\begin{equation*}
a = bq + r, 0 \leq r \lt b \quad \text{and}\quad a = bq' + r', 0 \leq r' \lt b\text{.}
\end{equation*}
Then \(bq + r = bq' + r'\text{.}\) Assume that \(r' \geq r\text{.}\) From the last equation we have \(b(q - q') = r' - r\text{;}\) therefore, \(b\) must divide \(r' - r\) and \(0 \leq r'- r \leq r' \lt b\text{.}\) This is possible only if \(r' - r = 0\text{.}\) Hence, \(r = r'\) and \(q = q'\text{.}\)
Let \(a\) and \(b\) be integers. If \(b = ak\) for some integer \(k\text{,}\) we write \(a \mid b\text{.}\) An integer \(d\) is called a common divisor of \(a\) and \(b\) if \(d \mid a\) and \(d \mid b\text{.}\) 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\text{,}\) then \(d' \mid d\text{.}\) We write \(d = \gcd(a, b)\text{;}\) for example, \(\gcd( 24, 36) = 12\) and \(\gcd(120, 102) = 6\text{.}\) We say that two integers \(a\) and \(b\) are relatively prime if \(\gcd( a, b ) = 1\text{.}\)
Theorem 2.2.2.
View Source for theorem
<theorem xml:id="theorem-integers-gcd">
<statement>
<p>
Let <m>a</m> and <m>b</m> be nonzero integers.
Then there exist integers <m>r</m> and <m>s</m> such that
<me>
\gcd( a, b) = ar + bs
</me>.
Furthermore,
the greatest common divisor of <m>a</m> and <m>b</m> is unique.
</p>
</statement>
<proof>
<p>
Let
<me>
S = \{ am + bn : m, n \in {\mathbb Z} \text{ and } am + bn \gt 0 \}
</me>.
Clearly, the set <m>S</m> is nonempty;
hence, by the Well-Ordering Principle <m>S</m> must have a smallest member,
say <m>d = ar + bs</m>.
We claim that <m>d = \gcd( a, b)</m>.
Write <m>a = dq + r'</m> where <m>0 \leq r' \lt d</m>.
If <m>r' \gt 0</m>, then
<md>
<mrow>r'& = a - dq</mrow>
<mrow>& = a - (ar + bs)q</mrow>
<mrow>& = a - arq - bsq</mrow>
<mrow>& = a( 1 - rq ) + b( -sq )</mrow>
</md>,
which is in <m>S</m>.
But this would contradict the fact that <m>d</m> is the smallest member of <m>S</m>.
Hence, <m>r' = 0</m> and <m>d</m> divides <m>a</m>.
A similar argument shows that <m>d</m> divides <m>b</m>.
Therefore, <m>d</m> is a common divisor of <m>a</m> and <m>b</m>.
</p>
<p>
Suppose that <m>d'</m> is another common divisor of <m>a</m> and <m>b</m>,
and we want to show that <m>d' \mid d</m>.
If we let <m>a = d'h</m> and <m>b = d'k</m>, then
<me>
d = ar + bs = d'hr + d'ks = d'(hr + ks)
</me>.
So <m>d'</m> must divide <m>d</m>.
Hence, <m>d</m> must be the unique greatest common divisor of <m>a</m> and <m>b</m>.
</p>
</proof>
</theorem>
Let \(a\) and \(b\) be nonzero integers. Then there exist integers \(r\) and \(s\) such that
\begin{equation*}
\gcd( a, b) = ar + bs\text{.}
\end{equation*}
Furthermore, the greatest common divisor of \(a\) and \(b\) is unique.
Proof.
View Source for proof
<proof>
<p>
Let
<me>
S = \{ am + bn : m, n \in {\mathbb Z} \text{ and } am + bn \gt 0 \}
</me>.
Clearly, the set <m>S</m> is nonempty;
hence, by the Well-Ordering Principle <m>S</m> must have a smallest member,
say <m>d = ar + bs</m>.
We claim that <m>d = \gcd( a, b)</m>.
Write <m>a = dq + r'</m> where <m>0 \leq r' \lt d</m>.
If <m>r' \gt 0</m>, then
<md>
<mrow>r'& = a - dq</mrow>
<mrow>& = a - (ar + bs)q</mrow>
<mrow>& = a - arq - bsq</mrow>
<mrow>& = a( 1 - rq ) + b( -sq )</mrow>
</md>,
which is in <m>S</m>.
But this would contradict the fact that <m>d</m> is the smallest member of <m>S</m>.
Hence, <m>r' = 0</m> and <m>d</m> divides <m>a</m>.
A similar argument shows that <m>d</m> divides <m>b</m>.
Therefore, <m>d</m> is a common divisor of <m>a</m> and <m>b</m>.
</p>
<p>
Suppose that <m>d'</m> is another common divisor of <m>a</m> and <m>b</m>,
and we want to show that <m>d' \mid d</m>.
If we let <m>a = d'h</m> and <m>b = d'k</m>, then
<me>
d = ar + bs = d'hr + d'ks = d'(hr + ks)
</me>.
So <m>d'</m> must divide <m>d</m>.
Hence, <m>d</m> must be the unique greatest common divisor of <m>a</m> and <m>b</m>.
</p>
</proof>
Let
\begin{equation*}
S = \{ am + bn : m, n \in {\mathbb Z} \text{ and } am + bn \gt 0 \}\text{.}
\end{equation*}
Clearly, the set \(S\) is nonempty; hence, by the Well-Ordering Principle \(S\) must have a smallest member, say \(d = ar + bs\text{.}\) We claim that \(d = \gcd( a, b)\text{.}\) Write \(a = dq + r'\) where \(0 \leq r' \lt d\text{.}\) If \(r' \gt 0\text{,}\) then
\begin{align*}
r'& = a - dq\\
& = a - (ar + bs)q\\
& = a - arq - bsq\\
& = a( 1 - rq ) + b( -sq )\text{,}
\end{align*}
which is in \(S\text{.}\) But this would contradict the fact that \(d\) is the smallest member of \(S\text{.}\) Hence, \(r' = 0\) and \(d\) divides \(a\text{.}\) A similar argument shows that \(d\) divides \(b\text{.}\) Therefore, \(d\) is a common divisor of \(a\) and \(b\text{.}\)
Suppose that \(d'\) is another common divisor of \(a\) and \(b\text{,}\) and we want to show that \(d' \mid d\text{.}\) If we let \(a = d'h\) and \(b = d'k\text{,}\) then
\begin{equation*}
d = ar + bs = d'hr + d'ks = d'(hr + ks)\text{.}
\end{equation*}
So \(d'\) must divide \(d\text{.}\) Hence, \(d\) must be the unique greatest common divisor of \(a\) and \(b\text{.}\)
Corollary 2.2.3.
View Source for corollary
<corollary xml:id="corollary-integers-coprime">
<statement>
<p>
Let <m>a</m> and <m>b</m> be two integers that are relatively prime.
Then there exist integers <m>r</m> and <m>s</m> such that <m>ar + bs = 1</m>.
</p>
</statement>
</corollary>
Let \(a\) and \(b\) be two integers that are relatively prime. Then there exist integers \(r\) and \(s\) such that \(ar + bs = 1\text{.}\)
Subsection 2.2.1 The Euclidean Algorithm
View Source for subsection
<subsection>
<title>The Euclidean Algorithm</title>
<p>
Among other things,
<xref ref="theorem-integers-gcd" /> allows us to compute the greatest common divisor of two integers.
</p>
<example xml:id="example-integers-gcd">
<title>Greatest Common Divisor of Two Integers</title>
<p>
Let us compute the greatest common divisor of <m>945</m> and <m>2415</m>.
First observe that
<md>
<mrow>2415 & = 945 \cdot 2 + 525</mrow>
<mrow>945 & = 525 \cdot 1 + 420</mrow>
<mrow>525 & = 420 \cdot 1 + 105</mrow>
<mrow>420 & = 105 \cdot 4 + 0</mrow>
</md>.
</p>
<p>
Reversing our steps, 105 divides 420, 105 divides 525, 105 divides 945, and 105 divides 2415.
Hence, 105 divides both 945 and 2415.
If <m>d</m> were another common divisor of 945 and 2415,
then <m>d</m> would also have to divide 105.
Therefore, <m>\gcd( 945, 2415 ) = 105</m>.
</p>
<p>
If we work backward through the above sequence of equations,
we can also obtain numbers <m>r</m> and <m>s</m> such that <m>945 r + 2415 s = 105</m>.
Observe that
<md>
<mrow>105 & = 525 + (-1) \cdot 420</mrow>
<mrow>& = 525 + (-1) \cdot [945 + (-1) \cdot 525]</mrow>
<mrow>& = 2 \cdot 525 + (-1) \cdot 945</mrow>
<mrow>& = 2 \cdot [2415 + (-2) \cdot 945] + (-1) \cdot 945</mrow>
<mrow>& = 2 \cdot 2415 + (-5) \cdot 945</mrow>
</md>.
</p>
<p>
So <m>r = -5</m> and <m>s= 2</m>.
Notice that <m>r</m> and <m>s</m> are not unique,
since <m>r = 41</m> and <m>s = -16</m> would also work.
</p>
</example>
<p>
To compute <m>\gcd(a,b) = d</m>,
we are using repeated divisions to obtain a decreasing sequence of positive integers <m>r_1 \gt r_2 \gt \cdots \gt r_n = d</m>; that is,
<md>
<mrow>b & = a q_1 + r_1</mrow>
<mrow>a & = r_1 q_2 + r_2</mrow>
<mrow>r_1 & = r_2 q_3 + r_3</mrow>
<mrow>& \vdots</mrow>
<mrow>r_{n - 2} & = r_{n - 1} q_{n} + r_{n}</mrow>
<mrow>r_{n - 1} & = r_n q_{n + 1}</mrow>
</md>.
</p>
<p>
To find <m>r</m> and <m>s</m> such that <m>ar + bs = d</m>,
we begin with this last equation and substitute results obtained from the previous equations:
<md>
<mrow>d & = r_n</mrow>
<mrow>& = r_{n - 2} - r_{n - 1} q_n</mrow>
<mrow>& = r_{n - 2} - q_n( r_{n - 3} - q_{n - 1} r_{n - 2} )</mrow>
<mrow>& = -q_n r_{n - 3} + ( 1+ q_n q_{n-1} ) r_{n - 2}</mrow>
<mrow>& \vdots</mrow>
<mrow>& = ra + sb</mrow>
</md>.
</p>
<p>
The algorithm that we have just used to find the greatest common divisor <m>d</m> of two integers <m>a</m> and <m>b</m> and to write <m>d</m> as the linear combination of <m>a</m> and <m>b</m> is known as the
<term>Euclidean algorithm</term>
<idx><h>Euclidean algorithm</h></idx>.
<idx><h>Algorithm</h><h>Euclidean</h></idx>
</p>
</subsection>
Among other things, Theorem 2.2.2 allows us to compute the greatest common divisor of two integers.
Example 2.2.4. Greatest Common Divisor of Two Integers.
View Source for example
<example xml:id="example-integers-gcd">
<title>Greatest Common Divisor of Two Integers</title>
<p>
Let us compute the greatest common divisor of <m>945</m> and <m>2415</m>.
First observe that
<md>
<mrow>2415 & = 945 \cdot 2 + 525</mrow>
<mrow>945 & = 525 \cdot 1 + 420</mrow>
<mrow>525 & = 420 \cdot 1 + 105</mrow>
<mrow>420 & = 105 \cdot 4 + 0</mrow>
</md>.
</p>
<p>
Reversing our steps, 105 divides 420, 105 divides 525, 105 divides 945, and 105 divides 2415.
Hence, 105 divides both 945 and 2415.
If <m>d</m> were another common divisor of 945 and 2415,
then <m>d</m> would also have to divide 105.
Therefore, <m>\gcd( 945, 2415 ) = 105</m>.
</p>
<p>
If we work backward through the above sequence of equations,
we can also obtain numbers <m>r</m> and <m>s</m> such that <m>945 r + 2415 s = 105</m>.
Observe that
<md>
<mrow>105 & = 525 + (-1) \cdot 420</mrow>
<mrow>& = 525 + (-1) \cdot [945 + (-1) \cdot 525]</mrow>
<mrow>& = 2 \cdot 525 + (-1) \cdot 945</mrow>
<mrow>& = 2 \cdot [2415 + (-2) \cdot 945] + (-1) \cdot 945</mrow>
<mrow>& = 2 \cdot 2415 + (-5) \cdot 945</mrow>
</md>.
</p>
<p>
So <m>r = -5</m> and <m>s= 2</m>.
Notice that <m>r</m> and <m>s</m> are not unique,
since <m>r = 41</m> and <m>s = -16</m> would also work.
</p>
</example>
Let us compute the greatest common divisor of \(945\) and \(2415\text{.}\) 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\text{.}
\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\text{.}\)
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\text{.}\) 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\text{.}
\end{align*}
So \(r = -5\) and \(s= 2\text{.}\) Notice that \(r\) and \(s\) are not unique, since \(r = 41\) and \(s = -16\) would also work.
To compute \(\gcd(a,b) = d\text{,}\) we are using repeated divisions to obtain a decreasing sequence of positive integers \(r_1 \gt r_2 \gt \cdots \gt r_n = d\text{;}\) 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}\text{.}
\end{align*}
To find \(r\) and \(s\) such that \(ar + bs = d\text{,}\) 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\text{.}
\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 .
Subsection 2.2.2 Prime Numbers
View Source for subsection
<subsection>
<title>Prime Numbers</title>
<p>
Let <m>p</m> be an integer such that <m>p \gt 1</m>.
We say that <m>p</m> is a <term>prime number</term>,
<idx><h>Prime integer</h></idx>
or simply <m>p</m> is <term>prime</term>,
if the only positive numbers that divide <m>p</m> are 1 and <m>p</m> itself.
An integer <m>n \gt 1</m> that is not prime is said to be <term>composite</term>.
<idx><h>Composite integer</h></idx>
</p>
<lemma xml:id="theorem-integers-prime-divisor">
<creator>Euclid</creator>
<statement>
<p>
Let <m>a</m> and <m>b</m> be integers and <m>p</m> be a prime number.
If <m>p \mid ab</m>, then either <m>p \mid a</m> or <m>p \mid b</m>.
</p>
</statement>
<proof>
<p>
Suppose that <m>p</m> does not divide <m>a</m>.
We must show that <m>p \mid b</m>.
Since <m>\gcd( a, p ) = 1</m>,
there exist integers <m>r</m> and <m>s</m> such that <m>ar + ps = 1</m>.
So
<me>
b = b(ar + ps) = (ab)r + p(bs)
</me>.
Since <m>p</m> divides both <m>ab</m> and itself,
<m>p</m> must divide <m>b = (ab)r + p(bs)</m>.
</p>
</proof>
</lemma>
<theorem xml:id="theorem-integers-infinite-primes">
<creator>Euclid</creator>
<statement>
<p>
There exist an infinite number of primes.
</p>
</statement>
<proof>
<p>
We will prove this theorem by contradiction.
Suppose that there are only a finite number of primes,
say <m>p_1, p_2, \ldots, p_n</m>.
Let <m>P = p_1 p_2 \cdots p_n + 1</m>.
Then <m>P</m> must be divisible by some <m>p_i</m> for <m>1 \leq i \leq n</m>.
In this case, <m>p_i</m> must divide
<m>P - p_1 p_2 \cdots p_n = 1</m>, which is a contradiction.
Hence, either <m>P</m> is prime or there exists an additional prime number
<m>p \neq p_i</m> that divides <m>P</m>.
</p>
</proof>
</theorem>
<theorem xml:id="theorem-fund-theorem-arithmetic">
<title>Fundamental Theorem of Arithmetic</title>
<idx><h>Fundamental Theorem</h><h>of Arithmetic</h></idx>
<statement>
<p>
Let <m>n</m> be an integer such that <m>n \gt 1</m>.
Then
<me>
n = p_1 p_2 \cdots p_k
</me>,
where <m>p_1, \ldots, p_k</m> are primes
(not necessarily distinct).
Furthermore, this factorization is unique; that is, if
<me>
n = q_1 q_2 \cdots q_l
</me>,
then <m>k = l</m> and the <m>q_i</m>'s are just the <m>p_i</m>'s rearranged.
</p>
</statement>
<proof>
<p>
<em>Uniqueness.</em> To show uniqueness we will use induction on <m>n</m>.
The theorem is certainly true for <m>n = 2</m> since in this case <m>n</m> is prime.
Now assume that the result holds for all integers <m>m</m> such that <m>1 \leq m \lt n</m>, and
<me>
n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l
</me>,
where <m>p_1 \leq p_2 \leq \cdots \leq p_k</m> and <m>q_1 \leq q_2 \leq \cdots \leq q_l</m>.
By <xref ref="theorem-integers-prime-divisor" />, <m>p_1 \mid q_i</m> for some
<m>i = 1, \ldots,
l</m> and <m>q_1 \mid p_j</m> for some <m>j = 1, \ldots, k</m>.
Since all of the <m>p_i</m>'s and <m>q_i</m>'s are prime,
<m>p_1 = q_i</m> and <m>q_1 = p_j</m>.
Hence, <m>p_1 = q_1</m> since <m>p_1 \leq p_j = q_1 \leq q_i = p_1</m>.
By the induction hypothesis,
<me>
n' = p_2 \cdots p_k = q_2 \cdots q_l
</me>
has a unique factorization.
Hence, <m>k = l</m> and <m>q_i = p_i</m> for <m>i = 1, \ldots, k</m>.
</p>
<p>
<em>Existence.</em> To show existence,
suppose that there is some integer that cannot be written as the product of primes.
Let <m>S</m> be the set of all such numbers.
By the Principle of Well-Ordering,
<m>S</m> has a smallest number, say <m>a</m>.
If the only positive factors of <m>a</m> are <m>a</m> and 1, then <m>a</m> is prime,
which is a contradiction.
Hence, <m>a = a_1 a_2</m> where
<m>1 \lt a_1 \lt a</m> and <m>1 \lt a_2 \lt a</m>.
Neither <m>a_1\in S</m> nor <m>a_2 \in S</m>,
since <m>a</m> is the smallest element in <m>S</m>.
So
<md>
<mrow>a_1 & = p_1 \cdots p_r</mrow>
<mrow>a_2 & = q_1 \cdots q_s</mrow>
</md>.
</p>
<p>
Therefore,
<me>
a = a_1 a_2 = p_1 \cdots p_r q_1 \cdots q_s
</me>.
So <m>a \notin S</m>, which is a contradiction.
</p>
</proof>
</theorem>
</subsection>
Let \(p\) be an integer such that \(p \gt 1\text{.}\) 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.
Lemma 2.2.5 (Euclid).
View Source for lemma
<lemma xml:id="theorem-integers-prime-divisor">
<creator>Euclid</creator>
<statement>
<p>
Let <m>a</m> and <m>b</m> be integers and <m>p</m> be a prime number.
If <m>p \mid ab</m>, then either <m>p \mid a</m> or <m>p \mid b</m>.
</p>
</statement>
<proof>
<p>
Suppose that <m>p</m> does not divide <m>a</m>.
We must show that <m>p \mid b</m>.
Since <m>\gcd( a, p ) = 1</m>,
there exist integers <m>r</m> and <m>s</m> such that <m>ar + ps = 1</m>.
So
<me>
b = b(ar + ps) = (ab)r + p(bs)
</me>.
Since <m>p</m> divides both <m>ab</m> and itself,
<m>p</m> must divide <m>b = (ab)r + p(bs)</m>.
</p>
</proof>
</lemma>
Let \(a\) and \(b\) be integers and \(p\) be a prime number. If \(p \mid ab\text{,}\) then either \(p \mid a\) or \(p \mid b\text{.}\)
Proof.
View Source for proof
<proof>
<p>
Suppose that <m>p</m> does not divide <m>a</m>.
We must show that <m>p \mid b</m>.
Since <m>\gcd( a, p ) = 1</m>,
there exist integers <m>r</m> and <m>s</m> such that <m>ar + ps = 1</m>.
So
<me>
b = b(ar + ps) = (ab)r + p(bs)
</me>.
Since <m>p</m> divides both <m>ab</m> and itself,
<m>p</m> must divide <m>b = (ab)r + p(bs)</m>.
</p>
</proof>
Suppose that \(p\) does not divide \(a\text{.}\) We must show that \(p \mid b\text{.}\) Since \(\gcd( a, p ) = 1\text{,}\) there exist integers \(r\) and \(s\) such that \(ar + ps = 1\text{.}\) So
\begin{equation*}
b = b(ar + ps) = (ab)r + p(bs)\text{.}
\end{equation*}
Since \(p\) divides both \(ab\) and itself, \(p\) must divide \(b = (ab)r + p(bs)\text{.}\)
Theorem 2.2.6 (Euclid).
View Source for theorem
<theorem xml:id="theorem-integers-infinite-primes">
<creator>Euclid</creator>
<statement>
<p>
There exist an infinite number of primes.
</p>
</statement>
<proof>
<p>
We will prove this theorem by contradiction.
Suppose that there are only a finite number of primes,
say <m>p_1, p_2, \ldots, p_n</m>.
Let <m>P = p_1 p_2 \cdots p_n + 1</m>.
Then <m>P</m> must be divisible by some <m>p_i</m> for <m>1 \leq i \leq n</m>.
In this case, <m>p_i</m> must divide
<m>P - p_1 p_2 \cdots p_n = 1</m>, which is a contradiction.
Hence, either <m>P</m> is prime or there exists an additional prime number
<m>p \neq p_i</m> that divides <m>P</m>.
</p>
</proof>
</theorem>
There exist an infinite number of primes.
Proof.
View Source for proof
<proof>
<p>
We will prove this theorem by contradiction.
Suppose that there are only a finite number of primes,
say <m>p_1, p_2, \ldots, p_n</m>.
Let <m>P = p_1 p_2 \cdots p_n + 1</m>.
Then <m>P</m> must be divisible by some <m>p_i</m> for <m>1 \leq i \leq n</m>.
In this case, <m>p_i</m> must divide
<m>P - p_1 p_2 \cdots p_n = 1</m>, which is a contradiction.
Hence, either <m>P</m> is prime or there exists an additional prime number
<m>p \neq p_i</m> that divides <m>P</m>.
</p>
</proof>
We will prove this theorem by contradiction. Suppose that there are only a finite number of primes, say \(p_1, p_2, \ldots, p_n\text{.}\) Let \(P = p_1 p_2 \cdots p_n + 1\text{.}\) Then \(P\) must be divisible by some \(p_i\) for \(1 \leq i \leq n\text{.}\) In this case, \(p_i\) must divide \(P - p_1 p_2 \cdots p_n = 1\text{,}\) which is a contradiction. Hence, either \(P\) is prime or there exists an additional prime number \(p \neq p_i\) that divides \(P\text{.}\)
Theorem 2.2.7. Fundamental Theorem of Arithmetic.
View Source for theorem
<theorem xml:id="theorem-fund-theorem-arithmetic">
<title>Fundamental Theorem of Arithmetic</title>
<idx><h>Fundamental Theorem</h><h>of Arithmetic</h></idx>
<statement>
<p>
Let <m>n</m> be an integer such that <m>n \gt 1</m>.
Then
<me>
n = p_1 p_2 \cdots p_k
</me>,
where <m>p_1, \ldots, p_k</m> are primes
(not necessarily distinct).
Furthermore, this factorization is unique; that is, if
<me>
n = q_1 q_2 \cdots q_l
</me>,
then <m>k = l</m> and the <m>q_i</m>'s are just the <m>p_i</m>'s rearranged.
</p>
</statement>
<proof>
<p>
<em>Uniqueness.</em> To show uniqueness we will use induction on <m>n</m>.
The theorem is certainly true for <m>n = 2</m> since in this case <m>n</m> is prime.
Now assume that the result holds for all integers <m>m</m> such that <m>1 \leq m \lt n</m>, and
<me>
n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l
</me>,
where <m>p_1 \leq p_2 \leq \cdots \leq p_k</m> and <m>q_1 \leq q_2 \leq \cdots \leq q_l</m>.
By <xref ref="theorem-integers-prime-divisor" />, <m>p_1 \mid q_i</m> for some
<m>i = 1, \ldots,
l</m> and <m>q_1 \mid p_j</m> for some <m>j = 1, \ldots, k</m>.
Since all of the <m>p_i</m>'s and <m>q_i</m>'s are prime,
<m>p_1 = q_i</m> and <m>q_1 = p_j</m>.
Hence, <m>p_1 = q_1</m> since <m>p_1 \leq p_j = q_1 \leq q_i = p_1</m>.
By the induction hypothesis,
<me>
n' = p_2 \cdots p_k = q_2 \cdots q_l
</me>
has a unique factorization.
Hence, <m>k = l</m> and <m>q_i = p_i</m> for <m>i = 1, \ldots, k</m>.
</p>
<p>
<em>Existence.</em> To show existence,
suppose that there is some integer that cannot be written as the product of primes.
Let <m>S</m> be the set of all such numbers.
By the Principle of Well-Ordering,
<m>S</m> has a smallest number, say <m>a</m>.
If the only positive factors of <m>a</m> are <m>a</m> and 1, then <m>a</m> is prime,
which is a contradiction.
Hence, <m>a = a_1 a_2</m> where
<m>1 \lt a_1 \lt a</m> and <m>1 \lt a_2 \lt a</m>.
Neither <m>a_1\in S</m> nor <m>a_2 \in S</m>,
since <m>a</m> is the smallest element in <m>S</m>.
So
<md>
<mrow>a_1 & = p_1 \cdots p_r</mrow>
<mrow>a_2 & = q_1 \cdots q_s</mrow>
</md>.
</p>
<p>
Therefore,
<me>
a = a_1 a_2 = p_1 \cdots p_r q_1 \cdots q_s
</me>.
So <m>a \notin S</m>, which is a contradiction.
</p>
</proof>
</theorem>
Let \(n\) be an integer such that \(n \gt 1\text{.}\) Then
\begin{equation*}
n = p_1 p_2 \cdots p_k\text{,}
\end{equation*}
where \(p_1, \ldots, p_k\) are primes (not necessarily distinct). Furthermore, this factorization is unique; that is, if
\begin{equation*}
n = q_1 q_2 \cdots q_l\text{,}
\end{equation*}
then \(k = l\) and the \(q_i\)’s are just the \(p_i\)’s rearranged.
Proof.
View Source for proof
<proof>
<p>
<em>Uniqueness.</em> To show uniqueness we will use induction on <m>n</m>.
The theorem is certainly true for <m>n = 2</m> since in this case <m>n</m> is prime.
Now assume that the result holds for all integers <m>m</m> such that <m>1 \leq m \lt n</m>, and
<me>
n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l
</me>,
where <m>p_1 \leq p_2 \leq \cdots \leq p_k</m> and <m>q_1 \leq q_2 \leq \cdots \leq q_l</m>.
By <xref ref="theorem-integers-prime-divisor" />, <m>p_1 \mid q_i</m> for some
<m>i = 1, \ldots,
l</m> and <m>q_1 \mid p_j</m> for some <m>j = 1, \ldots, k</m>.
Since all of the <m>p_i</m>'s and <m>q_i</m>'s are prime,
<m>p_1 = q_i</m> and <m>q_1 = p_j</m>.
Hence, <m>p_1 = q_1</m> since <m>p_1 \leq p_j = q_1 \leq q_i = p_1</m>.
By the induction hypothesis,
<me>
n' = p_2 \cdots p_k = q_2 \cdots q_l
</me>
has a unique factorization.
Hence, <m>k = l</m> and <m>q_i = p_i</m> for <m>i = 1, \ldots, k</m>.
</p>
<p>
<em>Existence.</em> To show existence,
suppose that there is some integer that cannot be written as the product of primes.
Let <m>S</m> be the set of all such numbers.
By the Principle of Well-Ordering,
<m>S</m> has a smallest number, say <m>a</m>.
If the only positive factors of <m>a</m> are <m>a</m> and 1, then <m>a</m> is prime,
which is a contradiction.
Hence, <m>a = a_1 a_2</m> where
<m>1 \lt a_1 \lt a</m> and <m>1 \lt a_2 \lt a</m>.
Neither <m>a_1\in S</m> nor <m>a_2 \in S</m>,
since <m>a</m> is the smallest element in <m>S</m>.
So
<md>
<mrow>a_1 & = p_1 \cdots p_r</mrow>
<mrow>a_2 & = q_1 \cdots q_s</mrow>
</md>.
</p>
<p>
Therefore,
<me>
a = a_1 a_2 = p_1 \cdots p_r q_1 \cdots q_s
</me>.
So <m>a \notin S</m>, which is a contradiction.
</p>
</proof>
Uniqueness. To show uniqueness we will use induction on \(n\text{.}\) The theorem is certainly true for \(n = 2\) since in this case \(n\) is prime. Now assume that the result holds for all integers \(m\) such that \(1 \leq m \lt n\text{,}\) and
\begin{equation*}
n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l\text{,}
\end{equation*}
where \(p_1 \leq p_2 \leq \cdots \leq p_k\) and \(q_1 \leq q_2 \leq \cdots \leq q_l\text{.}\) By Lemma 2.2.5, \(p_1 \mid q_i\) for some \(i = 1, \ldots,
l\) and \(q_1 \mid p_j\) for some \(j = 1, \ldots, k\text{.}\) Since all of the \(p_i\)’s and \(q_i\)’s are prime, \(p_1 = q_i\) and \(q_1 = p_j\text{.}\) Hence, \(p_1 = q_1\) since \(p_1 \leq p_j = q_1 \leq q_i = p_1\text{.}\) By the induction hypothesis,
\begin{equation*}
n' = p_2 \cdots p_k = q_2 \cdots q_l
\end{equation*}
has a unique factorization. Hence, \(k = l\) and \(q_i = p_i\) for \(i = 1, \ldots, k\text{.}\)
Existence. To show existence, suppose that there is some integer that cannot be written as the product of primes. Let \(S\) be the set of all such numbers. By the Principle of Well-Ordering, \(S\) has a smallest number, say \(a\text{.}\) If the only positive factors of \(a\) are \(a\) and 1, then \(a\) is prime, which is a contradiction. Hence, \(a = a_1 a_2\) where \(1 \lt a_1 \lt a\) and \(1 \lt a_2 \lt a\text{.}\) Neither \(a_1\in S\) nor \(a_2 \in S\text{,}\) since \(a\) is the smallest element in \(S\text{.}\) So
\begin{align*}
a_1 & = p_1 \cdots p_r\\
a_2 & = q_1 \cdots q_s\text{.}
\end{align*}
Therefore,
\begin{equation*}
a = a_1 a_2 = p_1 \cdots p_r q_1 \cdots q_s\text{.}
\end{equation*}
So \(a \notin S\text{,}\) which is a contradiction.
Subsection 2.2.3 Historical Note
View Source for subsection
<subsection>
<title>Historical Note</title>
<p>
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 <m>n</m>.
One problem in number theory is to find a function <m>f</m> such that <m>f(n)</m> is prime for each integer <m>n</m>.
Pierre Fermat (1601?<ndash />1665) conjectured that
<m>2^{2^n} + 1</m> was prime for all <m>n</m>,
but later it was shown by Leonhard Euler (1707<ndash />1783) that
<me>
2^{2^5} + 1 = \text{4,294,967,297}
</me>
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:
<m>4 = 2 + 2</m>, <m>6 = 3 + 3</m>,
<m>8 =3 + 5</m>, <m>\ldots</m>.
Although the conjecture has been verified for the numbers up through <m>4 \times 10^{18}</m>,
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.
</p>
<xi:include xmlns="http://www.w3.org/2001/XInclude" href="./sage/integers-info.xml" />
</subsection>
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\text{.}\) One problem in number theory is to find a function \(f\) such that \(f(n)\) is prime for each integer \(n\text{.}\) Pierre Fermat (1601?–1665) conjectured that \(2^{2^n} + 1\) was prime for all \(n\text{,}\) 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\text{,}\) \(6 = 3 + 3\text{,}\) \(8 =3 + 5\text{,}\) \(\ldots\text{.}\) Although the conjecture has been verified for the numbers up through \(4 \times 10^{18}\text{,}\) 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.
