Difference between revisions of "Abstract Algebra: Preliminaries"

From Department of Mathematics at UTSA
Jump to navigation Jump to search
 
(43 intermediate revisions by the same user not shown)
Line 80: Line 80:
  
 
==Integers==
 
==Integers==
The set of integers consists of zero ({{num|0}}), the positive natural numbers ({{num|1}}, {{num|2}}, {{num|3}},&nbsp;...), also called ''whole numbers'' or ''counting numbers'', and their additive inverses (the '''negative integers''', i.e., −1, −2, −3,&nbsp;...). The set of integers is often denoted by the boldface ({{math|'''Z'''}}) or [[blackboard bold]] <math>(\mathbb{Z})</math> letter "Z"—standing originally for the German word ''Zahlen'' ("numbers").
+
The set of integers consists of zero (0), the positive natural numbers (1, 2, 3,&nbsp;...), also called ''whole numbers'' or ''counting numbers'', and their additive inverses (the '''negative integers''', i.e., −1, −2, −3,&nbsp;...). The set of integers is often denoted by the boldface ({{math|'''Z'''}}) or blackboard bold <math>(\mathbb{Z})</math> letter "Z"—standing originally for the German word ''Zahlen'' ("numbers").
  
 
<math>\mathbb{Z}</math> is a subset of the set of all rational numbers <math>\mathbb{Q}</math>, which in turn is a subset of the real numbers <math>\mathbb{R}</math>.  Like the natural numbers, <math>\mathbb{Z}</math> is countably infinite.
 
<math>\mathbb{Z}</math> is a subset of the set of all rational numbers <math>\mathbb{Q}</math>, which in turn is a subset of the real numbers <math>\mathbb{R}</math>.  Like the natural numbers, <math>\mathbb{Z}</math> is countably infinite.
 +
 +
=== Algebraic properties ===
 +
 +
Like the natural numbers, <math>\mathbb{Z}</math> is closed under the operations of addition and multiplication, that is, the sum and product of any two integers is an integer. However, with the inclusion of the negative natural numbers (and importantly,&nbsp;0), <math>\mathbb{Z}</math>, unlike the natural numbers, is also closed under subtraction.
 +
 +
The integers form a unital ring which is the most basic one, in the following sense: for any unital ring, there is a unique ring homomorphism from the integers into this ring. This universal property, namely to be an initial object in the category of rings, characterizes the ring&nbsp;<math>\mathbb{Z}</math>.
 +
 +
<math>\mathbb{Z}</math> is not closed under division, since the quotient of two integers (e.g.,&nbsp;1 divided by&nbsp;2) need not be an integer. Although the natural numbers are closed under exponentiation, the integers are not (since the result can be a fraction when the exponent is negative).
 +
 +
The following table lists some of the basic properties of addition and multiplication for any integers {{math|''a''}}, {{math|''b''}} and {{math|''c''}}:
 +
{|class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
 +
|+Properties of addition and multiplication on integers
 +
!
 +
!scope="col" |Addition
 +
!scope="col" |Multiplication
 +
|-
 +
!scope="row" |Closure:
 +
|{{math|''a'' + ''b''}} is an integer
 +
|{{math|''a'' × ''b''}} is an integer
 +
|-
 +
!scope="row"|Associativity:
 +
|{{math|''a'' + (''b'' + ''c'') <math>=</math> (''a'' + ''b'') + ''c''}}
 +
|{{math|''a'' × (''b'' × ''c'') <math>=</math> (''a'' × ''b'') × ''c''}}
 +
|-
 +
!scope="row" |Commutativity:
 +
|{{math|''a'' + ''b'' <math>=</math> ''b'' + ''a''}}
 +
|{{math|''a'' × ''b'' <math>=</math> ''b'' × ''a''}}
 +
|-
 +
!scope="row" |Existence of an identity element:
 +
|{{math|''a'' + 0 <math>=</math> ''a''}}
 +
|{{math|''a'' × 1 <math>=</math> ''a''}}
 +
|-
 +
!scope="row" |Existence of inverse elements:
 +
|{{math|''a'' + (−''a'') <math>=</math> 0}}
 +
|The only invertible integers (called units) are {{math|−1}} and&nbsp;{{math|1}}.
 +
|-
 +
!scope="row" |Distributivity:
 +
|colspan=2 align=center |{{math|''a'' × (''b'' + ''c'') <math>=</math> (''a'' × ''b'') + (''a'' × ''c'')}}  and  {{math|(''a'' + ''b'') × ''c'' <math>=</math> (''a'' × ''c'') + (''b'' × ''c'')}}
 +
|-
 +
!scope="row" |No zero divisors:
 +
| || | If {{math|''a'' × ''b'' <math>=</math> 0}}, then {{math|''a'' <math>=</math> 0}} or {{math|''b'' <math>=</math> 0}} (or both)
 +
|}
 +
 +
The first five properties listed above for addition say that <math>\mathbb{Z}</math>, under addition, is an abelian group. It is also a cyclic group, since every non-zero integer can be written as a finite sum 1 + 1 + ... + 1 or (−1) + (−1) + ... + (−1). In fact, <math>\mathbb{Z}</math> under addition is the ''only'' infinite cyclic group—in the sense that any infinite cyclic group is isomorphic to <math>\Z</math>.
 +
 +
The first four properties listed above for multiplication say that <math>\mathbb{Z}</math> under multiplication is a commutative monoid. However, not every integer has a multiplicative inverse (as is the case of the number 2), which means that <math>\mathbb{Z}</math> under multiplication is not a group.
 +
 +
All the rules from the above property table (except for the last), when taken together, say that <math>\mathbb{Z}</math> together with addition and multiplication is a commutative ring with unity. It is the prototype of all objects of such algebraic structure. Only those equalities of expressions are true in&nbsp;<math>\mathbb{Z}</math> for all values of variables, which are true in any unital commutative ring. Certain non-zero integers map to zero in certain rings.
 +
 +
The lack of zero divisors in the integers (last property in the table) means that the commutative ring&nbsp;<math>\mathbb{Z}</math> is an integral domain.
 +
 +
The lack of multiplicative inverses, which is equivalent to the fact that <math>\mathbb{Z}</math> is not closed under division, means that <math>\mathbb{Z}</math> is ''not'' a field. The smallest field containing the integers as a subring is the field of rational numbers. The process of constructing the rationals from the integers can be mimicked to form the field of fractions of any integral domain. And back, starting from an algebraic number field (an extension of rational numbers), its ring of integers can be extracted, which includes <math>\mathbb{Z}</math> as its subring.
 +
 +
Although ordinary division is not defined on <math>\mathbb{Z}</math>, the division "with remainder" is defined on them. It is called Euclidean division, and possesses the following important property: given two integers {{math|''a''}} and {{math|''b''}} with {{math|''b'' ≠ 0}}, there exist unique integers {{math|''q''}} and {{math|''r''}} such that {{math|''a'' <math>=</math> ''q'' × ''b'' + ''r''}} and {{math|0 ≤ ''r'' <  {{!}}''b''{{!}}}}, where {{math|{{!}}''b''{{!}}}} denotes the absolute value of {{math|''b''}}. The integer {{math|''q''}} is called the ''quotient'' and {{math|''r''}} is called the ''remainder'' of the division of {{math|''a''}} by {{math|''b''}}. The Euclidean algorithm for computing greatest common divisors works by a sequence of Euclidean divisions.
 +
 +
The above says that <math>\mathbb{Z}</math> is a Euclidean domain. This implies that <math>\mathbb{Z}</math> is a principal ideal domain, and any positive integer can be written as the products of primes in an essentially unique way. This is the fundamental theorem of arithmetic.
 +
 +
===Construction===
 +
[[File:Relative numbers representation.svg|thumb|alt=Representation of equivalence classes for the numbers −5 to 5
 +
|Red points represent ordered pairs of natural numbers. Linked red points are equivalence classes representing the blue integers at the end of the line.|upright=1.5]]
 +
In elementary school teaching, integers are often intuitively defined as the (positive) natural numbers, zero, and the negations of the natural numbers. However, this style of definition leads to many different cases (each arithmetic operation needs to be defined on each combination of types of integer) and makes it tedious to prove that integers obey the various laws of arithmetic. Therefore, in modern set-theoretic mathematics, a more abstract construction allowing one to define arithmetical operations without any case distinction is often used instead. The integers can thus be formally constructed as the equivalence classes of ordered pairs of natural numbers {{math|(''a'',''b'')}}.
 +
 +
The intuition is that {{math|(''a'',''b'')}} stands for the result of subtracting {{math|''b''}} from {{math|''a''}}. To confirm our expectation that 1 − 2 and 4 − 5 denote the same number, we define an equivalence relation {{math|~}} on these pairs with the following rule:
 +
:<math>(a,b) \sim (c,d) </math>
 +
precisely when
 +
:<math>a + d = b + c. </math>
 +
 +
Addition and multiplication of integers can be defined in terms of the equivalent operations on the natural numbers; by using {{math|[(''a'',''b'')]}} to denote the equivalence class having {{math|(''a'',''b'')}} as a member, one has:
 +
:<math>[(a,b)] + [(c,d)] := [(a+c,b+d)].</math>
 +
:<math>[(a,b)]\cdot[(c,d)] := [(ac+bd,ad+bc)].</math>
 +
 +
The negation (or additive inverse) of an integer is obtained by reversing the order of the pair:
 +
:<math>-[(a,b)] := [(b,a)].</math>
 +
 +
Hence subtraction can be defined as the addition of the additive inverse:
 +
:<math>[(a,b)] - [(c,d)] := [(a+d,b+c)].</math>
 +
 +
The standard ordering on the integers is given by:
 +
:<math>[(a,b)] < [(c,d)]</math> if and only if <math>a+d < b+c.</math>
 +
 +
It is easily verified that these definitions are independent of the choice of representatives of the equivalence classes.
 +
 +
Every equivalence class has a unique member that is of the form {{math|(''n'',0)}} or {{math|(0,''n'')}} (or both at once). The natural number {{math|''n''}} is identified with the class {{math|[(''n'',0)]}} (i.e., the natural numbers are embedded into the integers by map sending {{math|''n''}} to {{math|[(''n'',0)]}}), and the class {{math|[(0,''n'')]}} is denoted {{math|−''n''}} (this covers all remaining classes, and gives the class {{math|[(0,0)]}} a second time since {{math|−0 <math>=</math> 0.}}
 +
 +
Thus, {{math|[(''a'',''b'')]}} is denoted by
 +
:<math>\begin{cases} a - b, & \mbox{if }  a \ge b  \\ -(b - a),  & \mbox{if } a < b. \end{cases}</math>
 +
 +
If the natural numbers are identified with the corresponding integers (using the embedding mentioned above), this convention creates no ambiguity.
 +
 +
This notation recovers the familiar representation of the integers as {{math|{..., −2, −1, 0, 1, 2, ...} }}.
 +
 +
Some examples are:
 +
:<math>\begin{align}
 +
0 &= [(0,0)] &= [(1,1)] &= \cdots & &= [(k,k)] \\
 +
1 &= [(1,0)] &= [(2,1)] &= \cdots & &= [(k+1,k)] \\
 +
-1 &= [(0,1)] &= [(1,2)] &= \cdots & &= [(k,k+1)] \\
 +
2 &= [(2,0)] &= [(3,1)] &= \cdots & &= [(k+2,k)] \\
 +
-2 &= [(0,2)] &= [(1,3)] &= \cdots & &= [(k,k+2)].
 +
\end{align}</math>
  
 
==Division algorithm==
 
==Division algorithm==
 +
<p>One rather important aspect of the divisibility of integers is that if <span class="math-inline"><math>a, b \in \mathbb{Z}</math></span> then <span class="math-inline"><math>a</math></span> can be written as the product of some quotient <span class="math-inline"><math>q</math></span> with <span class="math-inline"><math>b</math></span> plus a remainder <span class="math-inline"><math>r</math></span>. For example, if <span class="math-inline"><math>a = 11</math></span> and <span class="math-inline"><math>b = 3</math></span>, then <span class="math-inline"><math>a = 3(b) + 2</math></span> where <span class="math-inline"><math>q = 3</math></span> and <span class="math-inline"><math>r = 2</math></span>.</p>
 +
<p>The following theorem known as the Division Algorithm shows us that for any pair of integers <span class="math-inline"><math>a, b \in \mathbb{Z}</math></span> where <span class="math-inline"><math>b > 0</math></span> that the form <span class="math-inline"><math>a = bq + r</math></span> exists and is unique.</p>
 +
<blockquote style="background: white; border: 1px solid black; padding: 1em;">
 +
<td><strong>Theorem 1 (The Division Algorithm):</strong> Let <span class="math-inline"><math>a, b \in \mathbb{Z}</math></span> with <span class="math-inline"><math>b > 0</math></span>. Then there exists unique <span class="math-inline"><math>q, r \in \mathbb{Z}</math></span> where <span class="math-inline"><math>0 \leq r < b</math></span> and such that <span class="math-inline"><math>a = bq + r</math></span>.</td>
 +
</blockquote>
 +
<p><em>The value of <span class="math-inline"><math>r</math></span> is often called the <strong>Remainder</strong> when <span class="math-inline"><math>a</math></span> is divided by <span class="math-inline"><math>b</math></span>. That is, <span class="math-inline"><math>a</math></span> is equal to some multiple <span class="math-inline"><math>q</math></span>, known as the <strong>Quotient</strong> of <span class="math-inline"><math>b</math></span>, plus a remainder <span class="math-inline"><math>r</math></span> for which <span class="math-inline"><math>0 \leq r < b</math></span>.</em></p>
 +
<ul>
 +
<li><strong>Proof:</strong> Let <span class="math-inline"><math>a, b \in \mathbb{Z}</math></span> with <span class="math-inline"><math>b > 0</math></span> and consider the following set <span class="math-inline"><math>A</math></span>:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad A = \{ a - bq : q \in \mathbb{N} \} = \{ a, a - b, a - 2b, ... \}. \end{align}</math></div>
 +
<ul>
 +
<li>Consider <span class="math-inline"><math>B \subset A</math></span> of nonnegative elements in <span class="math-inline"><math>A</math></span>. If <span class="math-inline"><math>a > 0</math></span> then <span class="math-inline"><math>a \in B</math></span> and if <span class="math-inline"><math>a < 0</math></span> then <span class="math-inline"><math>a - ba = a(1 - b) \in B</math></span>, so <span class="math-inline"><math>B</math></span> is a nonempty set. Moreover, <span class="math-inline"><math>B</math></span> is a nonempty subset of integers and so by the Well-Ordering principle there exists a least element of <span class="math-inline"><math>B</math></span>, say <span class="math-inline"><math>r \in B</math></span> is this least element. Since <span class="math-inline"><math>r \in B</math></span> we have that <span class="math-inline"><math>r = a - bn</math></span> for some <span class="math-inline"><math>n \in \mathbb{N}</math></span> and so:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad a = bq + r \end{align}</math></div>
 +
<ul>
 +
<li>So <span class="math-inline"><math>a</math></span> if of the form we desire. Now since <span class="math-inline"><math>r \in B</math></span> and every element in <span class="math-inline"><math>B</math></span> is nonnegative then we have that <span class="math-inline"><math>0 \leq r</math></span>. Suppose that <span class="math-inline"><math>r \geq b</math></span>. Then <span class="math-inline"><math>r = b + p</math></span> where <span class="math-inline"><math>p \geq 0</math></span> and so:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad a = bq + r = bq + (b + p) = b(q + 1) + p \end{align}</math></div>
 +
<ul>
 +
<li>Therefore <span class="math-inline"><math>p = a - b(q + 1) \geq 0</math></span> and so <span class="math-inline"><math>p \in B</math></span>. Since <span class="math-inline"><math>b > 0</math></span> and <span class="math-inline"><math>q+1 > q</math></span> we have that <span class="math-inline"><math>0 \leq p < r</math></span>. But this implies that <span class="math-inline"><math>r</math></span> is not the least element of <span class="math-inline"><math>B</math></span> which is a contradiction, so our assumption that <span class="math-inline"><math>r \geq b</math></span> is false, and so <span class="math-inline"><math>0 \leq r < b</math></span>.</li>
 +
</ul>
 +
<ul>
 +
<li>We lastly show that <span class="math-inline"><math>q</math></span> and <span class="math-inline"><math>r</math></span> are unique for <span class="math-inline"><math>a = bq + r</math></span> and <span class="math-inline"><math>0 \leq r < b</math></span>. Suppose that <span class="math-inline"><math>a = bq_1 + r_1</math></span> and <span class="math-inline"><math>a = bq_2 + r_2</math></span> where <span class="math-inline"><math>0 \leq r_1, r_2 < b</math></span>. Then by subtracting these two equations we get:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad 0 = bq_1 - bq_2 + r_1 - r_2 \\ \quad 0 =b(q_1 - q_2) + r_1 - r_2 \\ \quad r_2 - r_1 = b(q_1 - q_2) \end{align}</math></div>
 +
<ul>
 +
<li>Therefore <span class="math-inline"><math>r_2 - r_1</math></span> is a multiple of <span class="math-inline"><math>b</math></span>. Since <span class="math-inline"><math>0 \leq r_1 < b</math></span> and <span class="math-inline"><math>0 \leq r_2 < b</math></span> we must have that <span class="math-inline"><math>-b < r_2 - r_1 < b</math></span>. The only multiple of <span class="math-inline"><math>b</math></span> such that <span class="math-inline"><math>-b < r_2 - r_1 < b</math></span> is <span class="math-inline"><math>0</math></span>, so:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad r_2 - r_1 = 0 \\ \quad r_1 = r_2 \end{align}</math></div>
 +
<ul>
 +
<li>Since <span class="math-inline"><math>r_1 = r_2 = r</math></span>, we have that <span class="math-inline"><math>0 = b(q_1 - q_2)</math></span>. Since <span class="math-inline"><math>b > 0</math></span> this implies that <span class="math-inline"><math>q_1 - q_2 = 0</math></span> and so <span class="math-inline"><math>q_1 = q_2</math></span>. Therefore <span class="math-inline"><math>a</math></span> can be uniquely expressed in the form <span class="math-inline"><math>a = bq + r</math></span> where <span class="math-inline"><math>0 \leq r < b</math></span>. <span class="math-inline"><math>\blacksquare</math></span></li>
 +
</ul>
  
 
==Congruence modulo m==
 
==Congruence modulo m==
 +
<blockquote style="background: white; border: 1px solid black; padding: 1em;"><td><strong>Definition:</strong> If <span class="math-inline"><math>a, b, m \in \mathbb{Z}</math></span> then we say that <span class="math-inline"><math>a</math></span> is <strong>Congruent</strong> to <span class="math-inline"><math>b</math></span> modulo <span class="math-inline"><math>m</math></span> denoted <span class="math-inline"><math>a \equiv b \pmod m</math></span> if <span class="math-inline"><math>m \mid (a - b)</math></span>.</td>
 +
</blockquote>
 +
<p><em>The congruence of two integers is an equivalence relation which we can describe in other words. We say that <span class="math-inline"><math>a</math></span> and <span class="math-inline"><math>b</math></span> are said to be congruent modulo <span class="math-inline"><math> m </math></span> if <span class="math-inline"><math>a</math></span> divided by <span class="math-inline"><math>m</math></span> leaves the same remaining as <span class="math-inline"><math>b</math></span> divided by <span class="math-inline"><math>m</math></span>.</em></p>
 +
<p>For example, <span class="math-inline"><math>3 \equiv 7 \pmod 2</math></span> since <span class="math-inline"><math>2 \mid (3 - 7) = -4</math></span>. Notice also that when <span class="math-inline"><math>3</math></span> and <span class="math-inline"><math>7</math></span> are divided by <span class="math-inline"><math>2</math></span> they both leave the same remainder, <span class="math-inline"><math>1</math></span>.</p>
 +
<p>We can denote the remainder of an integer <span class="math-inline"><math>a</math></span> when divided by <span class="math-inline"><math>m</math></span> as simply <span class="math-inline"><math>a \pmod m</math></span>. For example, <span class="math-inline"><math>1 = 3 \pmod 2</math></span> since the remaining of <span class="math-inline"><math>3</math></span> when divided by <span class="math-inline"><math>2</math></span> is <span class="math-inline"><math>1</math></span>. We should note that from <a href="/the-division-algorithm">The Division Algorithm</a> that the remainder <span class="math-inline"><math>r</math></span> when an integer <span class="math-inline"><math>a</math></span> is divided by <span class="math-inline"><math>m</math></span> satisfies the inequality <span class="math-inline"><math>0 \leq r < m</math></span>. Therefore we note that for all nonnegative integers <span class="math-inline"><math>a</math></span> and positive integers <span class="math-inline"><math>m</math></span> that:</p>
 +
<div style="text-align: center;"><math>\begin{align} \quad 0 \leq a \pmod m < m \end{align}</math></div>
 +
<p>In other words, for all nonnegative integers <span class="math-inline"><math>a</math></span> and positive integers <span class="math-inline"><math>m</math></span>, the set of possible remainders when <span class="math-inline"><math>a</math></span> is divided by <span class="math-inline"><math>m</math></span> is <span class="math-inline"><math>\{ 0, 1, 2, ..., m - 1 \}</math></span>.</p>
 +
<p>Consequentially, we can define the set of odd integers and the set of even numbers in terms of these elements in the set of even integers being congruent to one another and elements in the set of odd numbers being congruent to one another.</p>
 +
<blockquote style="background: white; border: 1px solid black; padding: 1em;">
 +
<td><strong>Definition:</strong> An integer <span class="math-inline"><math>z \in \mathbb{Z}</math></span> is said to be <strong>Odd</strong> if <span class="math-inline"><math>z \equiv 1 \pmod 2</math></span> or <strong>Even</strong> if <span class="math-inline"><math>z \equiv 0 \pmod 2</math></span>.</td>
 +
</blockquote>
 +
<p>We will now look at some basic theorems regarding integer congruence modulo <span class="math-inline"><math>m</math></span>.</p>
 +
<blockquote style="background: white; border: 1px solid black; padding: 1em;">
 +
<td><strong>Theorem 1:</strong> Let <span class="math-inline"><math>a, b, c, d, m \in \mathbb{Z}</math></span>. Then:<br />
 +
<strong>a)</strong> If <span class="math-inline"><math>a \equiv b \pmod m</math></span> then <span class="math-inline"><math>b \equiv a \pmod m</math></span>.<br />
 +
<strong>b)</strong> <span class="math-inline"><math>a \equiv a \pmod m</math></span>.<br />
 +
<strong>c)</strong> If <span class="math-inline"><math>a \equiv b \pmod m</math></span> and <span class="math-inline"><math>b \equiv c \pmod m</math></span> then <span class="math-inline"><math>a \equiv c \pmod m</math></span>.<br />
 +
<strong>d)</strong> If <span class="math-inline"><math>a \equiv b \pmod m</math></span> and <span class="math-inline"><math>c \equiv d \pmod m</math></span> then <span class="math-inline"><math>(a + c) \equiv (b + d) \pmod m</math></span>.<br />
 +
<strong>e)</strong> If <span class="math-inline"><math>a \equiv b \pmod m</math></span> and <span class="math-inline"><math>c \equiv d \pmod m</math></span> then <span class="math-inline"><math>ac \equiv bd \pmod m</math></span>.</td>
 +
</blockquote>
 +
<ul>
 +
<li><strong>Proof of a)</strong> Suppose that <span class="math-inline"><math>a \equiv b \pmod m</math></span>. Then <span class="math-inline"><math>m \mid (a - b)</math></span> so there exists an integer <span class="math-inline"><math>k</math></span> such that:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad mk = a - b \\ \quad -mk = b - a \\ \quad m(-k) = b - a \end{align}</math></div>
 +
<ul>
 +
<li>Therefore <span class="math-inline"><math>m \mid (b - a)</math></span> so <span class="math-inline"><math>b \equiv a \pmod m</math></span>. <span class="math-inline"><math>\blacksquare</math></span></li>
 +
</ul>
 +
<ul>
 +
<li>We have that <span class="math-inline"><math>m \mid 0 = (a - a)</math></span> for any integer <span class="math-inline"><math>a</math></span>. Therefore <span class="math-inline"><math>a \equiv a \pmod m</math></span>. <span class="math-inline"><math>\blacksquare</math></span></li>
 +
</ul>
 +
<ul>
 +
<li><strong>Proof of c)</strong> Suppose that <span class="math-inline"><math>a \equiv b \pmod m</math></span> and <span class="math-inline"><math>b \equiv c \pmod m</math></span>. Then <span class="math-inline"><math>m \mid (a - b)</math></span> and <span class="math-inline"><math>m \mid (b - c)</math></span> and there exists integers <span class="math-inline"><math>k_1</math></span> and <span class="math-inline"><math>k_2</math></span> such that:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad mk_1 = a - b \quad \mathrm{and} \quad mk_2 = b - c \end{align}</math></div>
 +
<ul>
 +
<li>From the second equation we have that <span class="math-inline"><math>b = mk_2 + c</math></span>. Substituting this into the first equation gives us:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad mk_1 = a - (mk_2 + c) \\ \quad mk_1 + mk_2 = a - c \\ \quad m(k_1 + k_2) = a - c \end{align}</math></div>
 +
<ul>
 +
<li>Therefore <span class="math-inline"><math>m \mid (a - c)</math></span> so <span class="math-inline"><math>a \equiv c \pmod m</math></span>. <span class="math-inline"><math>\blacksquare</math></span></li>
 +
</ul>
 +
<ul>
 +
<li><strong>Proof of d):</strong> Suppose that <span class="math-inline"><math>a \equiv b \pmod m</math></span> and <span class="math-inline"><math>c \equiv d \pmod m</math></span>. Then <span class="math-inline"><math>m \mid (a - b)</math></span> and <span class="math-inline"><math>m \mid (c - d)</math></span>, so there exists integers <span class="math-inline"><math>k_1</math></span> and <span class="math-inline"><math>k_2</math></span> such that:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad mk_1 = a - b \quad \mathrm{and} \quad mk_2 = c - d \end{align}</math></div>
 +
<ul>
 +
<li>Adding these equations together gives us:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad mk_1 + mk_2 = (a - b) + (c - d) \\ \quad m(k_1 + k_2) = (a + c) - (b + d) \end{align}</math></div>
 +
<ul>
 +
<li>Therefore <span class="math-inline"><math>m \mid (a + c) - (b + d)</math></span> so <span class="math-inline"><math>(a + c) \equiv (b + d) \pmod m</math></span> <span class="math-inline"><math>\blacksquare</math></span></li>
 +
</ul>
 +
<ul>
 +
<li><strong>Proof of e):</strong> Suppose that <span class="math-inline"><math>a \equiv b \pmod m</math></span> and <span class="math-inline"><math>c \equiv d \pmod m</math></span>. Then <span class="math-inline"><math>m \mid (a - b)</math></span> and <span class="math-inline"><math>m \mid (c - d)</math></span>, so there exists integers <span class="math-inline"><math>k_1</math></span> and <span class="math-inline"><math>k_2</math></span> such that:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad mk_1 = a - b \quad \mathrm{and} \quad mk_2 = c - d \\ \quad a = b + mk_1 \quad \mathrm{and} \quad c = d +mk_2 \end{align}</math></div>
 +
<ul>
 +
<li>Multiplying these equations together yields:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad ac = (b + mk_1)(d + mk_2) \\ \quad ac = bd + bmk_2 + dmk_1 + m^2k_1k_2 \\ \quad ac - bd = m(bk_2 + dk_1 + mk_1k_2) \end{align}</math></div>
 +
<ul>
 +
<li>Therefore <span class="math-inline"><math>m \mid (ac - bd)</math></span> so <span class="math-inline"><math>ac \equiv bd \pmod m</math></span>. <span class="math-inline"><math>\blacksquare</math></span></li>
 +
</ul>
  
 
==Algebra on <math>\Z_m</math>==
 
==Algebra on <math>\Z_m</math>==
 +
Let <math>n \in \N</math>. Since the relation of congruence modulo n is an equivalence relation on <math>\Z</math>, we can discuss its equivalence classes. Recall that in this situation, we refer to the equivalence classes as congruence classes.
 +
<blockquote style="background: white; border: 1px solid black; padding: 1em;">
 +
Definition of the integers modulo <math>n</math>: Let <math>n \in \N</math>. The set of congruence classes for the relation of congruence modulo <math>n</math> on <math>\Z</math> is the set of <strong>integers modulo <math>n</math></strong>, or the set of integers mod <math>n</math>. We will denote this set of congruence classes by <math>\Z_n</math>.
 +
</blockquote>
 +
 +
<math>\Z = [0] \cup [1] \cup [2] \cup \cdot\cdot\cdot \cup [n - 1]</math>.
 +
 +
In addition, we know that each integer is congruent to precisely one of the integers 0, 1, 2, ..., <math>n - 1</math>. This tells us that one way to represent <math>\Z_n</math> is
 +
 +
<math>\Z_n = \{[0], [1], [2], ... [n - 1]\}</math>.
 +
 +
Consequently, even though each integer has a congruence class, the set <math>\Z_n</math> has only <math>n</math> distinct congruence classes.
 +
 +
<p>The set of integers <math>\Z</math> is more than a set. We can add and multiply integers. That is, there are the arithmetic operations of addition and multiplication on the set <math>\Z</math>, and we know that <math>\Z</math> is closed with respect to these two operations.</p>
 +
 +
<p>One of the basic problems dealt with in modern algebra is to determine if the arithmetic operations on one set &ldquo;transfer&rdquo; to a related set. In this case, the related set is <math>\Z_n</math>. For example, in the integers modulo 5, <math>\Z_5</math>, is it possible to add the congruence classes [4] and [2] as follows?</p>
 +
 +
<p><math>\begin{array} {rcl} {[4] \oplus [2]} & = & {[4 + 2]} \\ {} & = & {[6]} \\ {} & = & {[1].} \end{array}</math></p>
 +
 +
<p>We have used the symbol &#778; to denote addition in <math>\Z_5</math> so that we do not confuse it with addition in <math>\Z</math>. This looks simple enough, but there is a problem. The congruence classes [4] and [2] are not numbers, they are infinite sets. We have to make sure that we get the same answer no matter what element of [4] we use and no matter what element of [2] we use. For example,</p>
 +
 +
<p><math>9 \equiv 4</math> (mod 5) and so [9] = [4]. Also,<br />
 +
<math>7 \equiv 2</math> (mod 5) and so [7] = [2].</p>
 +
 +
<p>Do we get the same result if we add [9] and [7] in the way we did when we added [4] and [2]? The following computation confirms that we do:</p>
 +
 +
<p><math>\begin{array} {rcl} {[9] \oplus [7]} & = & {[9 + 7]} \\ {} & = & {[16]} \\ {} & = & {[1].} \end{array}</math></p>
 +
 +
<p>The left side shows the properties in terms of the congruence relation and the right side shows the properties in terms of the congruence classes.</p>
 +
 +
<table class="mt-responsive-table">
 +
        <tr>
 +
            <td class="mt-noheading lt-math-7078">
 +
            <p>If <math>a \equiv 3</math> (mod 6) and <math>b \equiv 4</math> (mod 6), then</p>
 +
 +
            <ul>
 +
                <li class="lt-math-7078"><math>(a + b) \equiv (3 + 4)</math> (mod 6);</li>
 +
                <li class="lt-math-7078"><math>(a \cdot b) \equiv (3 \cdot 4)</math> (mod 6).</li>
 +
            </ul>
 +
            </td>
 +
            <td class="mt-noheading lt-math-7078">
 +
            <p>If <math>[a] = [3]</math> and <math>[b] = [4]</math> in <math>\Z_6</math>, then</p>
 +
 +
            <ul>
 +
                <li class="lt-math-7078"><math>[a + b] = [3 + 4]</math>;</li>
 +
                <li class="lt-math-7078"><math>[a \cdot b] = [3 \cdot 4]</math>.</li>
 +
            </ul>
 +
            </td>
 +
        </tr>
 +
</table>
 +
 +
<p>These are illustrations of general properties that we have already proved in Theorem 3.28. We repeat the statement of the theorem here because it is so important for defining the operations of addition and multiplication in <math>\Z_n</math>.</p>
 +
 +
<blockquote style="background: white; border: 1px solid black; padding: 1em;">
 +
 +
<p>Let <math>n</math> be a natural number and let <math>a</math>, <math>b</math>, <math>c</math>, and <math>d</math> be integers. Then</p>
 +
 +
<ol>
 +
    <li class="lt-math-7078">If <math>a \equiv b</math> (mod <math>n</math>) and <math>c \equiv d</math> (mod <math>n</math>), then <math>(a + c) \equiv (b + d)</math> (mod <math>n</math>).</li>
 +
    <li class="lt-math-7078">If <math>a \equiv b</math> (mod <math>n</math>) and <math>c \equiv d</math> (mod <math>n</math>), then <math>ac \equiv bd</math> (mod <math>n</math>).</li>
 +
    <li class="lt-math-7078">If <math>a \equiv b</math> (mod <math>n</math>) and <math>m \in \N</math>, then <math>a^m \equiv b^m</math> (mod <math>n</math>).</li>
 +
</ol>
 +
 +
</blockquote>
 +
 +
<p>Since <math>x \equiv y</math> (mod <math>n</math>) if and only if <math>[x] = [y]</math>, we can restate the result of this Theorem 3.28 in terms of congruence classes in <math>\Z_n</math>.</p>
 +
 +
<blockquote style="background: white; border: 1px solid black; padding: 1em;">
 +
 +
<p>Let <math>n</math> be a natural number and let <math>a</math>, <math>b</math>, <math>c</math>, and <math>d</math> be integers. Then, in <math>\Z_n</math>.</p>
 +
 +
<ol>
 +
    <li class="lt-math-7078">If <math>[a] = [b]</math> and <math>[c] = [d]</math>, then <math>[a + c] = [b + d]</math>.</li>
 +
    <li class="lt-math-7078">If <math>[a] = [b]</math> and <math>[c] = [d]</math>, then <math>[a \cdot c] = [b \cdot d]</math>.</li>
 +
    <li class="lt-math-7078">If <math>[a] = [b]</math> and <math>m \in \N</math>, then <math>[a]^m = [b]^m</math>.</li>
 +
</ol>
 +
</blockquote>
 +
 +
<p>Now, we know that the following formal definition of addition and multiplication of congruence classes in <math>\Z_n</math> is independent of the choice of the elements we choose from each class. We say that these definitions of addition and multiplication are <strong>well defined</strong>. </p>
  
 
==GCD, LCM, and Bézout's identity==
 
==GCD, LCM, and Bézout's identity==
 +
===Greatest Common Divisor===
 +
<blockquote style="background: white; border: 1px solid black; padding: 1em;">
 +
<td><strong>Definition:</strong> If <span class="math-inline"><math>a, b \in \mathbb{Z}</math></span> then the <strong>Greatest Common Divisor</strong> of <span class="math-inline"><math>a</math></span> and <span class="math-inline"><math>b</math></span> denoted <span class="math-inline"><math>\gcd (a, b)</math></span> or <span class="math-inline"><math>(a, b)</math></span> is an integer <span class="math-inline"><math>d \in \mathbb{Z}</math></span> such that:<br />
 +
<strong>1.</strong> <span class="math-inline"><math>d \mid a</math></span> and <span class="math-inline"><math>d \mid b</math></span>.<br />
 +
<strong>2.</strong> If <span class="math-inline"><math>c \in \mathbb{Z}</math></span>, <span class="math-inline"><math>c \mid a</math></span>, and <span class="math-inline"><math>c \mid b</math></span> then <span class="math-inline"><math>c \leq d</math></span>.</td>
 +
</blockquote>
 +
 +
<p>Note that the number <span class="math-inline"><math>1 \in \mathbb{Z}</math></span> has the property such that <span class="math-inline"><math>1 \mid a</math></span> and <span class="math-inline"><math>1 \mid b</math></span> for all <span class="math-inline"><math>a, b \in \mathbb{Z}</math></span> and so we see that the greatest common divisor of any two integers is always at least <span class="math-inline"><math>1</math></span>. As a result, we only need to compare positive divisors of <span class="math-inline"><math>a</math></span> and <span class="math-inline"><math>b</math></span>. Furthermore, if <span class="math-inline"><math>a | b</math></span> then it's not hard to verify that <span class="math-inline"><math>\text{gcd} (a, b) = | a |</math></span>.</p>
 +
<p>Let's look at an example of finding the greatest common divisor among two integers <span class="math-inline"><math>a, b \in \mathbb{Z}</math></span>.</p>
 +
<p>Consider the integers <span class="math-inline"><math>a = 14</math></span> and <span class="math-inline"><math>b = 35</math></span>. The factors of <span class="math-inline"><math>a</math></span> are <span class="math-inline"><math>1, 2, 7, 14</math></span> and the factors of <span class="math-inline"><math>b</math></span> are <span class="math-inline"><math>1, 5, 7, 35</math></span>. Both <span class="math-inline"><math>a</math></span> and <span class="math-inline"><math>b</math></span> share the factor <span class="math-inline"><math>7</math></span> and it is the largest factor they share, and so:</p>
 +
<div style="text-align: center;"><math>\begin{align} \quad \gcd (14, 35) = 7 \end{align}</math></div>
 +
<p>As we elaborated on just moments ago, the greatest common divisor of any two integers is always at least <span class="math-inline"><math>1</math></span>. We give a special name to pairs of integers for which their greatest common divisor is <span class="math-inline"><math>1</math></span> which we define below.</p>
 +
<blockquote style="background: white; border: 1px solid black; padding: 1em;">
 +
<td><strong>Definition:</strong> If <span class="math-inline"><math>a, b \in \mathbb{Z}</math></span> and <span class="math-inline"><math>\gcd (a, b) = 1</math></span> then <span class="math-inline"><math>a</math></span> and <span class="math-inline"><math>b</math></span> are said to be <strong>Relatively Prime</strong> to each other.</td>
 +
</blockquote>
 +
<p>For example, consider the numbers <span class="math-inline"><math>a = 5</math></span> and <span class="math-inline"><math>b = 8</math></span>. The greatest common divisor between these numbers is:</p>
 +
<div style="text-align: center;"><math>\begin{align} \quad \gcd (5, 8) = 1 \end{align}</math></div>
 +
<p>Therefore <span class="math-inline"><math>5</math></span> and <span class="math-inline"><math>8</math></span> are relatively prime to each other.</p>
 +
<blockquote style="background: white; border: 1px solid black; padding: 1em;">
 +
<td><strong>Theorem 1:</strong> If <span class="math-inline"><math>a, b, c \in \mathbb{Z}</math></span>, <span class="math-inline"><math>c \mid a</math></span>, and <span class="math-inline"><math>c \mid b</math></span> then <span class="math-inline"><math>c \mid \gcd (a, b)</math></span>.</td>
 +
</blockquote>
 +
 +
===Lowest Common Multiple===
 +
<blockquote style="background: white; border: 1px solid black; padding: 1em;">
 +
For all <math>a, b \in \Z : a b \ne 0</math>, there exists a smallest <math>m \in \Z : m > 0</math> such that <math>a | m</math> and <math>b | m</math>.
 +
 +
This <math>m</math> is called the '''lowest common multiple of <math>a</math> and <math>b</math>''', and denoted <math>\text{lcm} \{a, b\}</math>.
 +
</blockquote>
 +
 +
===Finding GCD and LCM with Prime Decomposition===
 +
Let <math>m, n \in \Z</math>.
 +
 +
Let:
 +
:<math>m = p_1^{k_1} p_2^{k_2} \dotsm p_r^{k_r}</math>
 +
:<math>n = p_1^{l_1} p_2^{l_2} \dotsm p_r^{l_r}</math>
 +
:<math>p_i | m \lor p_i | n, 1 \le i \le r</math>.
 +
 +
 +
That is, the primes given in these prime decompositions may be divisors of ''either'' of the numbers <math>m</math> or <math>n</math>.
 +
 +
 +
Note that if one of the primes <math>p_i</math> does not appear in the prime decompositions of either one of <math>m</math> or <math>n</math>, then its corresponding index <math>k_i</math> or <math>l_i</math> will be zero.
 +
 +
 +
Then the following results apply:
 +
 +
:<math>\text{gcd} \{m, n\} = p_1^{\min \{k_1, l_1\} } p_2^{\min \{k_2, l_2\} } \ldots p_r^{\min \{k_r, l_r\} }</math>
 +
 +
:<math>\text{lcm} \{m, n\} = p_1^{\max \{k_1, l_1\} } p_2^{\max \{k_2, l_2\} } \ldots p_r^{\max \{k_r, l_r\} }</math>
 +
 +
===Bézout's Identity===
 +
Let ''a'' and ''b'' be integers with greatest common divisor ''d''. Then there exist integers ''x'' and ''y'' such that ''ax'' + ''by'' = ''d''. More generally, the integers of the form ''ax'' + ''by'' are exactly the multiples of ''d''.
 +
 +
====Proof====
 +
Given any nonzero integers {{mvar|a}} and {{mvar|b}}, let <math>S=\{ax+by \mid x,y\in\mathbb{Z} \text{ and } ax+by>0\}.</math> The set {{mvar|S}} is nonempty since it contains either {{mvar|a}} or {{math|–''a''}} (with {{math|1=''x'' = ±1}} and {{math|1=''y'' = 0}}). Since {{mvar|S}} is a nonempty set of positive integers, it has a minimum element <math>d = as + bt</math>, by the Well-ordering principle. To prove that {{mvar|d}} is the greatest common divisor of {{mvar|a}} and {{mvar|b}}, it must be proven that {{mvar|d}} is a common divisor of {{mvar|a}} and {{mvar|b}}, and that for any other common divisor {{mvar|c}}, one has {{math|''c'' ≤ ''d''}}.
 +
 +
The Euclidean division of {{mvar|a}} by {{mvar|d}} may be written
 +
:<math>a=dq+r\quad\text{with}\quad 0\le r<d.</math>
 +
The remainder {{mvar|r}} is in <math>S\cup \{0\}</math>, because
 +
:<math>
 +
\begin{align}
 +
r  & = a - qd \\
 +
& = a - q(as+bt)\\
 +
& = a(1-qs) - bqt.
 +
\end{align}
 +
</math>
 +
Thus {{mvar|r}} is of the form <math>ax+by</math>, and hence <math>r\in S\cup \{0\}</math>. However, {{math|0 ≤ ''r'' < ''d''}}, and {{mvar|d}} is the smallest positive integer in {{mvar|S}}: the remainder {{mvar|r}} can therefore not be in {{mvar|S}}, making {{mvar|r}} necessarily 0. This implies that {{mvar|d}} is a divisor of {{mvar|a}}. Similarly {{mvar|d}} is also a divisor of {{mvar|b}}, and {{mvar|d}} is a common divisor of {{mvar|a}} and {{mvar|b}}.
 +
 +
Now, let {{mvar|c}} be any common divisor of {{mvar|a}} and {{mvar|b}}; that is, there exist {{mvar|u}} and {{mvar|v}} such that
 +
{{math|1=''a'' = ''cu''}} and {{math|1=''b'' = ''cv''}}. One has thus
 +
:<math>\begin{align}d&=as + bt\\
 +
& =cus+cvt\\
 +
&=c(us+vt).\end{align} </math>
 +
That is {{mvar|c}} is a divisor of {{mvar|d}}, and, therefore {{math|''c'' ≤ ''d.''}}
  
 
==Primes==
 
==Primes==
 +
<p>Recall that an integer <span class="math-inline"><math>p > 1</math></span> is a prime number if the only divisors of <span class="math-inline"><math>p</math></span> are <span class="math-inline"><math>\pm 1</math></span> and <span class="math-inline"><math>\pm p</math></span>, and an integer <span class="math-inline"><math>p > 1</math></span> that is not a prime number is called a composite number.</p>
 +
<p>We will now look at a very famous, simple, and important theorem which states that there exists infinitely many primes.</p>
 +
<table class="wiki-content-table">
 +
<tr>
 +
<td><strong>Theorem 1 (Euclid's Theorem of the Existence of Infinitely Many Primes):</strong> There are infinitely many prime numbers.</td>
 +
</tr>
 +
</table>
 +
<ul>
 +
<li><strong>Proof:</strong> We will carry this proof out by contradiction. Suppose that instead there are a finite number of primes. Then we can list all of these primes:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>
 +
\begin{align} \quad p_1, p_2, ..., p_k \end{align}</math></div>
 +
<ul>
 +
<li>Consider the number <span class="math-inline"><math>n = p_1p_2...p_k + 1</math></span>. We have already seen that every integer <span class="math-inline"><math>n > 1</math></span> has a prime divisor. Let this divisor be <span class="math-inline"><math>p_i</math></span> for some <span class="math-inline"><math>i \in \{ 1, 2, ..., k \}</math></span>. Then <span class="math-inline"><math>p_i \mid n</math></span> and <span class="math-inline"><math>p_i \mid p_1p_2...p_i...p_k</math></span>. But this implies that <span class="math-inline"><math>p_i \mid 1</math></span> which is a contradiction since all <span class="math-inline"><math>p_i \geq 2</math></span> and the only divisors of <span class="math-inline"><math>1</math></span> are <span class="math-inline"><math>\pm 1</math></span>.</li>
 +
</ul>
 +
<ul>
 +
<li>Therefore the assumption that there were finitely many primes was false and so there are infinitely many primes. <span class="math-inline"><math>\blacksquare</math></span></li>
 +
</ul>
 +
 
===Euclid's Lemma===
 
===Euclid's Lemma===
 +
 +
<blockquote style="background: white; border: 1px solid black; padding: 1em;">'''Euclid's lemma''': If a prime {{math|''p''}} divides the product {{math|''ab''}} of two integers {{math|''a''}} and {{math|''b''}}, then {{math|''p''}} must divide at least one of those integers {{math|''a''}} and {{math|''b''}}.</blockquote>
 +
 +
For example, if {{math|''p'' <math>=</math> 19}}, {{math|''a'' <math>=</math> 133}}, {{math|''b'' <math>=</math> 143}}, then {{math|''ab'' <math>=</math> 133 &times; 143 <math>=</math> 19019}}, and since this is divisible by 19, the lemma implies that one or both of 133 or 143 must be as well. In fact, {{math| 133 <math>=</math> 19 × 7}}.
 +
 +
A common proof of Euclid's lemma involves the Bézout's identity, which was unknown at Euclid's time. Bézout's identity states that if {{math|''x''}} and {{math|''y''}} are relatively prime integers (i.e. they share no common divisors other than 1 and -1) there exist integers {{math|''r''}} and {{math|''s''}} such that
 +
:<math>
 +
rx+sy = 1.
 +
</math>
 +
Let {{math|''a''}} and {{math|''n''}} be relatively prime, and assume that {{math|''n'' <math>=</math>''ab''}}. By Bézout's identity, there are {{math|''r''}} and {{math|''s''}} making
 +
:<math>
 +
rn+sa = 1.
 +
</math>
 +
Multiply both sides by {{math|''b''}}:
 +
:<math>
 +
rnb+sab = b.
 +
</math>
 +
The first term on the left is divisible by {{math|''n''}}, and the second term is divisible by {{math|''ab''}}, which by hypothesis is divisible by {{math|''n''}}. Therefore their sum, {{math|''b''}}, is also divisible by {{math|''n''}}. This is the generalization of Euclid's lemma mentioned above.
  
 
==Fundamental Theorem of Arithmetic==
 
==Fundamental Theorem of Arithmetic==
 +
 +
The Fundamental Theorem of Arithmetic, also known as the Unique Prime Factorization theorem, is as follows:
 +
 +
<blockquote style="background: white; border: 1px solid black; padding: 1em;">
 +
<td><strong>Theorem 1 (The Unique Prime Factorization Theorem):</strong> If <span class="math-inline"><math>n \in \mathbb{Z}</math></span> and <span class="math-inline"><math>n > 1</math></span> then <span class="math-inline"><math>n</math></span> can be written as a product of primes uniquely apart from the ordering of the primes in the product (<math> n = p_1p_2...p_k </math> for unique primes <math> p_1, p_2, ..., p_k </math>).</td>
 +
</blockquote>
 +
<p><em>If <span class="math-inline"><math>n \in \mathbb{Z}</math></span> and <span class="math-inline"><math>n < -1</math></span> then <span class="math-inline"><math>n</math></span> can also be written as a product of primes multiplied by <span class="math-inline"><math>-1</math></span>.</em></p>
 +
<ul>
 +
<li><strong>Proof:</strong> We first show that if <span class="math-inline"><math>n \in \mathbb{Z}</math></span> and <span class="math-inline"><math>n > 1</math></span> then <span class="math-inline"><math>n</math></span> can be written as a product of primes. We saw on the <a href="/prime-and-composite-numbers">Prime and Composite Numbers</a> page that if every <span class="math-inline"><math>n \in \mathbb{Z}</math></span> and <span class="math-inline"><math>n > 1</math></span> is divisible by a prime number. Let <span class="math-inline"><math>p_1</math></span> be this prime number. Then for some <span class="math-inline"><math>n_2 \in \{1, 2, ... \}</math></span> we have that:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad n = p_1n_1 \end{align}</math></div>
 +
<ul>
 +
<li>If <span class="math-inline"><math>n_1 = 1</math></span> then <span class="math-inline"><math>n = p_1</math></span> and we're done. If <span class="math-inline"><math>n_1</math></span> is prime then let <span class="math-inline"><math>p_2 = n_1</math></span> and so <span class="math-inline"><math>n = p_1p_2</math></span> and we're done. If <span class="math-inline"><math>n_1</math></span> is composite then <span class="math-inline"><math>n_1 > 1</math></span> and so once again, <span class="math-inline"><math>n_1</math></span> is divisible by a prime, say <span class="math-inline"><math>p_2</math></span>, where <span class="math-inline"><math>n_1 = p_2n_2</math></span>. Therefore:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad n = p_1p_2n_2 \end{align}</math></div>
 +
<ul>
 +
<li>If <span class="math-inline"><math>n_2 = 1</math></span> then <span class="math-inline"><math>n = p_1p_2</math></span> and we're done. If <span class="math-inline"><math>n_2</math></span> is prime then let <span class="math-inline"><math>p_3 = n_2</math></span> and so <span class="math-inline"><math>n = p_1p_2p_3</math></span> and we're done. If <span class="math-inline"><math>n_2</math></span> is composite then <span class="math-inline"><math>n_2 > 1</math></span> and again, <span class="math-inline"><math>n_2</math></span> is divisible by a prime, say <span class="math-inline"><math>p_3</math></span>, where <span class="math-inline"><math>n_2 = p_3n_3</math></span>.</li>
 +
</ul>
 +
<ul>
 +
<li>Note that <span class="math-inline"><math>n_1 > n_2 > ... \geq 1</math></span>. This sequence of integers is bounded below by <span class="math-inline"><math>1</math></span> and hence must terminate at some point. Therefore, for some <span class="math-inline"><math>k \in \{ 1, 2, ... \}</math></span> we have that:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad n = p_1p_2...p_k \end{align}</math></div>
 +
<ul>
 +
<li>Therefore <span class="math-inline"><math>n</math></span> can be written as a product of primes. We will now show that this factorization is unique. Suppose that <span class="math-inline"><math>n = p_1p_2...p_k</math></span> and <span class="math-inline"><math>n = q_1q_2...q_r</math></span> so that then:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad p_1p_2...p_k = q_1q_2...q_r \end{align}</math></div>
 +
<ul>
 +
<li>Since <span class="math-inline"><math>p_1 \mid n</math></span> we must have <span class="math-inline"><math>p_1 \mid q_1q_2...q_r</math></span>. Therefore <span class="math-inline"><math>p_1 = q_i</math></span> for some <span class="math-inline"><math>i \in \{1, 2, ... r \}</math></span>. Without loss of generality, assume that <span class="math-inline"><math>p_1 = q_1</math></span>. Therefore:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad p_2p_3...p_k = q_2q_3...q_r \end{align}</math></div>
 +
<ul>
 +
<li>Since <span class="math-inline"><math>p_2 \mid n</math></span> we must also have <span class="math-inline"><math>p_2 \mid q_2q_3...q_r</math></span>. Therefore <span class="math-inline"><math>p_2 = q_i</math></span> for some <span class="math-inline"><math>i \in \{2, 3, ... r \}</math></span>. Without loss of generality, assume that <span class="math-inline"><math>p_2 = q_2</math></span>. Therefore:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad p_3p_4...p_k = q_3q_4...q_r \end{align}</math></div>
 +
<ul>
 +
<li>We continue in this process. We note that we won't run out of primes <span class="math-inline"><math>p</math></span> before primes <span class="math-inline"><math>q</math></span>, otherwise this implies a prime <span class="math-inline"><math>q</math></span> is equal to <span class="math-inline"><math>1</math></span>. Furthermore, we won't run out of primes <span class="math-inline"><math>q</math></span> before primes <span class="math-inline"><math>p</math></span>, otherwise this implies a prime <span class="math-inline"><math>p</math></span> is equal to <span class="math-inline"><math>1</math></span>. Therefore <span class="math-inline"><math>k =r</math></span> and we eventually get:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \quad p_k = q_r \end{align}</math></div>
 +
<ul>
 +
<li>Therefore the prime factorization <span class="math-inline"><math>n = p_1p_2...p_k</math></span> is unique. <span class="math-inline"><math>\blacksquare</math></span></li>
 +
</ul>
  
 
== Licensing ==  
 
== Licensing ==  
 
Content obtained and/or adapted from:
 
Content obtained and/or adapted from:
 
* [https://en.wikipedia.org/wiki/Natural_number Natural number, Wikipedia] under a CC BY-SA license
 
* [https://en.wikipedia.org/wiki/Natural_number Natural number, Wikipedia] under a CC BY-SA license
 +
* [https://en.wikipedia.org/wiki/Integer Integer, Wikipedia] under a CC BY-SA license
 
* [https://en.wikipedia.org/wiki/Mathematical_induction Mathematical induction, Wikipedia] under a CC BY-SA license
 
* [https://en.wikipedia.org/wiki/Mathematical_induction Mathematical induction, Wikipedia] under a CC BY-SA license
 +
* [https://en.wikipedia.org/wiki/Euclid%27s_lemma Euclid's lemma, Wikipedia] under a CC BY-SA license
 +
* [https://en.wikipedia.org/wiki/Prime_number Prime number, Wikipedia] under a CC BY-SA license
 
* [http://mathonline.wikidot.com/abstract-algebra Abstract Algebra, mathonline.wikidot.com] under a CC BY-SA license
 
* [http://mathonline.wikidot.com/abstract-algebra Abstract Algebra, mathonline.wikidot.com] under a CC BY-SA license
 +
* [https://math.libretexts.org/Bookshelves/Mathematical_Logic_and_Proof/Book%3A_Mathematical_Reasoning__Writing_and_Proof_(Sundstrom)/7%3A_Equivalence_Relations/7.4%3A_Modular_Arithmetic Modular Arithmetic, LibreTexts: Mathematics] under a CC BY-SA license

Latest revision as of 12:38, 19 November 2021

Natural numbers

The natural numbers are those numbers used for counting (as in "there are six coins on the table") and ordering (as in "this is the third largest city in the country"). In common mathematical terminology, words colloquially used for counting are "cardinal numbers", and words used for ordering are "ordinal numbers". The natural numbers can, at times, appear as a convenient set of codes (labels or "names"), that is, as what linguists call nominal numbers, forgoing many or all of the properties of being a number in a mathematical sense.

Some definitions begin the natural numbers with 0, corresponding to the non-negative integers {0, 1, 2, 3, ...}, whereas others start with 1, corresponding to the positive integers {1, 2, 3, ...}. Texts that exclude zero from the natural numbers sometimes refer to the natural numbers together with zero as the whole numbers, while in other writings, that term is used instead for the integers (including negative integers).

The natural numbers are a basis from which many other number sets may be built by extension: the integers, by including (if not yet in) the neutral element 0 and an additive inverse (n) for each nonzero natural number n; the rational numbers, by including a multiplicative inverse () for each nonzero integer n (and also the product of these inverses by integers); the real numbers by including with the rationals the limits of (converging) Cauchy sequences of rationals; the complex numbers, by including with the real numbers the unresolved square root of minus one (and also the sums and products thereof); and so on. This chain of extensions make the natural numbers canonically embedded (identified) in the other number systems.

In common language, particularly in primary school education, natural numbers may be called counting numbers to intuitively exclude the negative integers and zero, and also to contrast the discreteness of counting to the continuity of measurement — a hallmark characteristic of real numbers.

Well-ordering principle

Consider the following set which we define to be the set of natural numbers:

Now consider any subset of . For example, let us consider the subsets , , and . The subset describes a finite set containing two integers. The subset describes the infinite set of all odd natural numbers, and the subset describes the infinite set of all even natural numbers. Notice that in each of these cases we can identify a least element of the subset. For example, the least element in is , the least element in is , and the least element in is .

In fact, it is impossible to construct a nonempty subset of that does not contain a least element. We describe this very important result below in the following theorem.

Theorem 1 (The Well-Ordering Principle of the Natural Numbers): Let be a nonempty subset of the natural numbers . Then there exists a least element , that is, for all .

We do not have the tools to prove Theorem 1 although it is a rather intuitively obvious result. Nevertheless, we should note that while Theorem 1 holds true for the set of natural numbers, it does not hold true for all sets of real numbers. For example, consider the set of rational numbers :

Any subset of the rational numbers need not have a least element. For example, consider the following subset of rational numbers between and noninclusive, that is, . We claim that has no least element. To prove this, assume that does have a least element, say is such that for all . Since we have that where Since we must have that too since and so:

Consider the number in the middle of and . This number is . Since and we have that and , so indeed, and which is a contradiction to our assumption that a least element exists in .

It's important to note that while not every subset of the rational numbers contains a least element, there are still subsets of that do contain a least element.

Induction

Mathematical induction is a mathematical proof technique. It is essentially used to prove that a statement P(n) holds for every natural number n = 0, 1, 2, 3, . . . ; that is, the overall statement is a sequence of infinitely many cases P(0), P(1), P(2), P(3), . . . . Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder:

"Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step)."

— Concrete Mathematics, page 3 margins.


A proof by induction consists of two cases. The first, the base case (or basis), proves the statement for n = 0 without assuming any knowledge of other cases. The second case, the induction step, proves that if the statement holds for any given case n = k, then it must also hold for the next case n = k + 1. These two steps establish that the statement holds for every natural number n. The base case does not necessarily begin with n = 0, but often with n = 1, and possibly with any fixed natural number n = N, establishing the truth of the statement for all natural numbers n ≥ N.

Description

The simplest and most common form of mathematical induction infers that a statement involving a natural number n (that is, an integer n ≥ 0 or 1) holds for all values of n. The proof consists of two steps:

  1. The initial or base case: prove that the statement holds for 0, or 1.
  2. The induction step, inductive step, or step case: prove that for every n, if the statement holds for n, then it holds for n + 1. In other words, assume that the statement holds for some arbitrary natural number n, and prove that the statement holds for n + 1.

The hypothesis in the inductive step, that the statement holds for a particular n, is called the induction hypothesis or inductive hypothesis. To prove the inductive step, one assumes the induction hypothesis for n and then uses this assumption to prove that the statement holds for n + 1.

Authors who prefer to define natural numbers to begin at 0 use that value in the base case; those who define natural numbers to begin at 1 use that value.

Example

Mathematical induction can be used to prove the following statement P(n) for all natural numbers n.

This states a general formula for the sum of the natural numbers less than or equal to a given number; in fact an infinite sequence of statements: , , , etc.

Proposition. For any ,

Proof. Let P(n) be the statement We give a proof by induction on n.

Base case: Show that the statement holds for the smallest natural number n = 0.

P(0) is clearly true:

Inductive step: Show that for any k ≥ 0, if P(k) holds, then P(k+1) also holds.

Assume the induction hypothesis that for a particular k, the single case n = k holds, meaning P(k) is true:

It follows that:

Algebraically, the right hand side simplifies as:

Equating the extreme left hand and right hand sides, we deduce that:

That is, the statement P(k+1) also holds true, establishing the inductive step.

Conclusion: Since both the base case and the inductive step have been proved as true, by mathematical induction the statement P(n) holds for every natural number n. ∎

Integers

The set of integers consists of zero (0), the positive natural numbers (1, 2, 3, ...), also called whole numbers or counting numbers, and their additive inverses (the negative integers, i.e., −1, −2, −3, ...). The set of integers is often denoted by the boldface (Z) or blackboard bold letter "Z"—standing originally for the German word Zahlen ("numbers").

is a subset of the set of all rational numbers , which in turn is a subset of the real numbers . Like the natural numbers, is countably infinite.

Algebraic properties

Like the natural numbers, is closed under the operations of addition and multiplication, that is, the sum and product of any two integers is an integer. However, with the inclusion of the negative natural numbers (and importantly, 0), , unlike the natural numbers, is also closed under subtraction.

The integers form a unital ring which is the most basic one, in the following sense: for any unital ring, there is a unique ring homomorphism from the integers into this ring. This universal property, namely to be an initial object in the category of rings, characterizes the ring .

is not closed under division, since the quotient of two integers (e.g., 1 divided by 2) need not be an integer. Although the natural numbers are closed under exponentiation, the integers are not (since the result can be a fraction when the exponent is negative).

The following table lists some of the basic properties of addition and multiplication for any integers a, b and c:

Properties of addition and multiplication on integers
Addition Multiplication
Closure: a + b is an integer a × b is an integer
Associativity: a + (b + c) (a + b) + c a × (b × c) (a × b) × c
Commutativity: a + b b + a a × b b × a
Existence of an identity element: a + 0 a a × 1 a
Existence of inverse elements: a + (−a) 0 The only invertible integers (called units) are −1 and 1.
Distributivity: a × (b + c) (a × b) + (a × c) and (a + b) × c (a × c) + (b × c)
No zero divisors: If a × b 0, then a 0 or b 0 (or both)

The first five properties listed above for addition say that , under addition, is an abelian group. It is also a cyclic group, since every non-zero integer can be written as a finite sum 1 + 1 + ... + 1 or (−1) + (−1) + ... + (−1). In fact, under addition is the only infinite cyclic group—in the sense that any infinite cyclic group is isomorphic to .

The first four properties listed above for multiplication say that under multiplication is a commutative monoid. However, not every integer has a multiplicative inverse (as is the case of the number 2), which means that under multiplication is not a group.

All the rules from the above property table (except for the last), when taken together, say that together with addition and multiplication is a commutative ring with unity. It is the prototype of all objects of such algebraic structure. Only those equalities of expressions are true in  for all values of variables, which are true in any unital commutative ring. Certain non-zero integers map to zero in certain rings.

The lack of zero divisors in the integers (last property in the table) means that the commutative ring  is an integral domain.

The lack of multiplicative inverses, which is equivalent to the fact that is not closed under division, means that is not a field. The smallest field containing the integers as a subring is the field of rational numbers. The process of constructing the rationals from the integers can be mimicked to form the field of fractions of any integral domain. And back, starting from an algebraic number field (an extension of rational numbers), its ring of integers can be extracted, which includes as its subring.

Although ordinary division is not defined on , the division "with remainder" is defined on them. It is called Euclidean division, and possesses the following important property: given two integers a and b with b ≠ 0, there exist unique integers q and r such that a q × b + r and 0 ≤ r < |b|, where |b| denotes the absolute value of b. The integer q is called the quotient and r is called the remainder of the division of a by b. The Euclidean algorithm for computing greatest common divisors works by a sequence of Euclidean divisions.

The above says that is a Euclidean domain. This implies that is a principal ideal domain, and any positive integer can be written as the products of primes in an essentially unique way. This is the fundamental theorem of arithmetic.

Construction

Representation of equivalence classes for the numbers −5 to 5
Red points represent ordered pairs of natural numbers. Linked red points are equivalence classes representing the blue integers at the end of the line.

In elementary school teaching, integers are often intuitively defined as the (positive) natural numbers, zero, and the negations of the natural numbers. However, this style of definition leads to many different cases (each arithmetic operation needs to be defined on each combination of types of integer) and makes it tedious to prove that integers obey the various laws of arithmetic. Therefore, in modern set-theoretic mathematics, a more abstract construction allowing one to define arithmetical operations without any case distinction is often used instead. The integers can thus be formally constructed as the equivalence classes of ordered pairs of natural numbers (a,b).

The intuition is that (a,b) stands for the result of subtracting b from a. To confirm our expectation that 1 − 2 and 4 − 5 denote the same number, we define an equivalence relation ~ on these pairs with the following rule:

precisely when

Addition and multiplication of integers can be defined in terms of the equivalent operations on the natural numbers; by using [(a,b)] to denote the equivalence class having (a,b) as a member, one has:

The negation (or additive inverse) of an integer is obtained by reversing the order of the pair:

Hence subtraction can be defined as the addition of the additive inverse:

The standard ordering on the integers is given by:

if and only if

It is easily verified that these definitions are independent of the choice of representatives of the equivalence classes.

Every equivalence class has a unique member that is of the form (n,0) or (0,n) (or both at once). The natural number n is identified with the class [(n,0)] (i.e., the natural numbers are embedded into the integers by map sending n to [(n,0)]), and the class [(0,n)] is denoted n (this covers all remaining classes, and gives the class [(0,0)] a second time since −0 0.

Thus, [(a,b)] is denoted by

If the natural numbers are identified with the corresponding integers (using the embedding mentioned above), this convention creates no ambiguity.

This notation recovers the familiar representation of the integers as {..., −2, −1, 0, 1, 2, ...} .

Some examples are:

Division algorithm

One rather important aspect of the divisibility of integers is that if then can be written as the product of some quotient with plus a remainder . For example, if and , then where and .

The following theorem known as the Division Algorithm shows us that for any pair of integers where that the form exists and is unique.

Theorem 1 (The Division Algorithm): Let with . Then there exists unique where and such that .

The value of is often called the Remainder when is divided by . That is, is equal to some multiple , known as the Quotient of , plus a remainder for which .

  • Proof: Let with and consider the following set :
  • Consider of nonnegative elements in . If then and if then , so is a nonempty set. Moreover, is a nonempty subset of integers and so by the Well-Ordering principle there exists a least element of , say is this least element. Since we have that for some and so:
  • So if of the form we desire. Now since and every element in is nonnegative then we have that . Suppose that . Then where and so:
  • Therefore and so . Since and we have that . But this implies that is not the least element of which is a contradiction, so our assumption that is false, and so .
  • We lastly show that and are unique for and . Suppose that and where . Then by subtracting these two equations we get:
  • Therefore is a multiple of . Since and we must have that . The only multiple of such that is , so:
  • Since , we have that . Since this implies that and so . Therefore can be uniquely expressed in the form where .

Congruence modulo m

Definition: If then we say that is Congruent to modulo denoted if .

The congruence of two integers is an equivalence relation which we can describe in other words. We say that and are said to be congruent modulo if divided by leaves the same remaining as divided by .

For example, since . Notice also that when and are divided by they both leave the same remainder, .

We can denote the remainder of an integer when divided by as simply . For example, since the remaining of when divided by is . We should note that from <a href="/the-division-algorithm">The Division Algorithm</a> that the remainder when an integer is divided by satisfies the inequality . Therefore we note that for all nonnegative integers and positive integers that:

In other words, for all nonnegative integers and positive integers , the set of possible remainders when is divided by is .

Consequentially, we can define the set of odd integers and the set of even numbers in terms of these elements in the set of even integers being congruent to one another and elements in the set of odd numbers being congruent to one another.

Definition: An integer is said to be Odd if or Even if .

We will now look at some basic theorems regarding integer congruence modulo .

Theorem 1: Let . Then:

a) If then .
b) .
c) If and then .
d) If and then .

e) If and then .

  • Proof of a) Suppose that . Then so there exists an integer such that:
  • Therefore so .
  • We have that for any integer . Therefore .
  • Proof of c) Suppose that and . Then and and there exists integers and such that:
  • From the second equation we have that . Substituting this into the first equation gives us:
  • Therefore so .
  • Proof of d): Suppose that and . Then and , so there exists integers and such that:
  • Adding these equations together gives us:
  • Therefore so
  • Proof of e): Suppose that and . Then and , so there exists integers and such that:
  • Multiplying these equations together yields:
  • Therefore so .

Algebra on

Let . Since the relation of congruence modulo n is an equivalence relation on , we can discuss its equivalence classes. Recall that in this situation, we refer to the equivalence classes as congruence classes.

Definition of the integers modulo : Let . The set of congruence classes for the relation of congruence modulo on is the set of integers modulo , or the set of integers mod . We will denote this set of congruence classes by .

.

In addition, we know that each integer is congruent to precisely one of the integers 0, 1, 2, ..., . This tells us that one way to represent is

.

Consequently, even though each integer has a congruence class, the set has only distinct congruence classes.

The set of integers is more than a set. We can add and multiply integers. That is, there are the arithmetic operations of addition and multiplication on the set , and we know that is closed with respect to these two operations.

One of the basic problems dealt with in modern algebra is to determine if the arithmetic operations on one set “transfer” to a related set. In this case, the related set is . For example, in the integers modulo 5, , is it possible to add the congruence classes [4] and [2] as follows?

We have used the symbol ̊ to denote addition in so that we do not confuse it with addition in . This looks simple enough, but there is a problem. The congruence classes [4] and [2] are not numbers, they are infinite sets. We have to make sure that we get the same answer no matter what element of [4] we use and no matter what element of [2] we use. For example,

(mod 5) and so [9] = [4]. Also,
(mod 5) and so [7] = [2].

Do we get the same result if we add [9] and [7] in the way we did when we added [4] and [2]? The following computation confirms that we do:

The left side shows the properties in terms of the congruence relation and the right side shows the properties in terms of the congruence classes.

If (mod 6) and (mod 6), then

  • (mod 6);
  • (mod 6).

If and in , then

  • ;
  • .

These are illustrations of general properties that we have already proved in Theorem 3.28. We repeat the statement of the theorem here because it is so important for defining the operations of addition and multiplication in .

Let be a natural number and let , , , and be integers. Then

  1. If (mod ) and (mod ), then (mod ).
  2. If (mod ) and (mod ), then (mod ).
  3. If (mod ) and , then (mod ).

Since (mod ) if and only if , we can restate the result of this Theorem 3.28 in terms of congruence classes in .

Let be a natural number and let , , , and be integers. Then, in .

  1. If and , then .
  2. If and , then .
  3. If and , then .

Now, we know that the following formal definition of addition and multiplication of congruence classes in is independent of the choice of the elements we choose from each class. We say that these definitions of addition and multiplication are well defined.

GCD, LCM, and Bézout's identity

Greatest Common Divisor

Definition: If then the Greatest Common Divisor of and denoted or is an integer such that:

1. and .

2. If , , and then .

Note that the number has the property such that and for all and so we see that the greatest common divisor of any two integers is always at least . As a result, we only need to compare positive divisors of and . Furthermore, if then it's not hard to verify that .

Let's look at an example of finding the greatest common divisor among two integers .

Consider the integers and . The factors of are and the factors of are . Both and share the factor and it is the largest factor they share, and so:

As we elaborated on just moments ago, the greatest common divisor of any two integers is always at least . We give a special name to pairs of integers for which their greatest common divisor is which we define below.

Definition: If and then and are said to be Relatively Prime to each other.

For example, consider the numbers and . The greatest common divisor between these numbers is:

Therefore and are relatively prime to each other.

Theorem 1: If , , and then .

Lowest Common Multiple

For all , there exists a smallest such that and .

This is called the lowest common multiple of and , and denoted .

Finding GCD and LCM with Prime Decomposition

Let .

Let:

.


That is, the primes given in these prime decompositions may be divisors of either of the numbers or .


Note that if one of the primes does not appear in the prime decompositions of either one of or , then its corresponding index or will be zero.


Then the following results apply:

Bézout's Identity

Let a and b be integers with greatest common divisor d. Then there exist integers x and y such that ax + by = d. More generally, the integers of the form ax + by are exactly the multiples of d.

Proof

Given any nonzero integers a and b, let The set S is nonempty since it contains either a or a (with x = ±1 and y = 0). Since S is a nonempty set of positive integers, it has a minimum element , by the Well-ordering principle. To prove that d is the greatest common divisor of a and b, it must be proven that d is a common divisor of a and b, and that for any other common divisor c, one has cd.

The Euclidean division of a by d may be written

The remainder r is in , because

Thus r is of the form , and hence . However, 0 ≤ r < d, and d is the smallest positive integer in S: the remainder r can therefore not be in S, making r necessarily 0. This implies that d is a divisor of a. Similarly d is also a divisor of b, and d is a common divisor of a and b.

Now, let c be any common divisor of a and b; that is, there exist u and v such that a = cu and b = cv. One has thus

That is c is a divisor of d, and, therefore cd.

Primes

Recall that an integer is a prime number if the only divisors of are and , and an integer that is not a prime number is called a composite number.

We will now look at a very famous, simple, and important theorem which states that there exists infinitely many primes.

Theorem 1 (Euclid's Theorem of the Existence of Infinitely Many Primes): There are infinitely many prime numbers.
  • Proof: We will carry this proof out by contradiction. Suppose that instead there are a finite number of primes. Then we can list all of these primes:
  • Consider the number . We have already seen that every integer has a prime divisor. Let this divisor be for some . Then and . But this implies that which is a contradiction since all and the only divisors of are .
  • Therefore the assumption that there were finitely many primes was false and so there are infinitely many primes.

Euclid's Lemma

Euclid's lemma: If a prime p divides the product ab of two integers a and b, then p must divide at least one of those integers a and b.

For example, if p 19, a 133, b 143, then ab 133 × 143 19019, and since this is divisible by 19, the lemma implies that one or both of 133 or 143 must be as well. In fact, 133 19 × 7.

A common proof of Euclid's lemma involves the Bézout's identity, which was unknown at Euclid's time. Bézout's identity states that if x and y are relatively prime integers (i.e. they share no common divisors other than 1 and -1) there exist integers r and s such that

Let a and n be relatively prime, and assume that n ab. By Bézout's identity, there are r and s making

Multiply both sides by b:

The first term on the left is divisible by n, and the second term is divisible by ab, which by hypothesis is divisible by n. Therefore their sum, b, is also divisible by n. This is the generalization of Euclid's lemma mentioned above.

Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic, also known as the Unique Prime Factorization theorem, is as follows:

Theorem 1 (The Unique Prime Factorization Theorem): If and then can be written as a product of primes uniquely apart from the ordering of the primes in the product ( for unique primes ).

If and then can also be written as a product of primes multiplied by .

  • Proof: We first show that if and then can be written as a product of primes. We saw on the <a href="/prime-and-composite-numbers">Prime and Composite Numbers</a> page that if every and is divisible by a prime number. Let be this prime number. Then for some we have that:
  • If then and we're done. If is prime then let and so and we're done. If is composite then and so once again, is divisible by a prime, say , where . Therefore:
  • If then and we're done. If is prime then let and so and we're done. If is composite then and again, is divisible by a prime, say , where .
  • Note that . This sequence of integers is bounded below by and hence must terminate at some point. Therefore, for some we have that:
  • Therefore can be written as a product of primes. We will now show that this factorization is unique. Suppose that and so that then:
  • Since we must have . Therefore for some . Without loss of generality, assume that . Therefore:
  • Since we must also have . Therefore for some . Without loss of generality, assume that . Therefore:
  • We continue in this process. We note that we won't run out of primes before primes , otherwise this implies a prime is equal to . Furthermore, we won't run out of primes before primes , otherwise this implies a prime is equal to . Therefore and we eventually get:
  • Therefore the prime factorization is unique.

Licensing

Content obtained and/or adapted from: