1: Well-Ordering and Division
- Page ID
- 28624
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
In this chapter, we present three basic tools that will often be used in proving properties of the integers. We start with a very important property of integers called the well-ordering principle. We then state what is known as the pigeonhole principle, and then we proceed to present an important method called mathematical induction.
- 1.1: The Well-Ordering Principle and Mathematical Induction
- The Well-Ordering Principle states that every non-empty set of natural numbers has a least element. The principle of mathematical induction is a valuable tool for proving results about integers.
- 1.2: Algebraic Operations with Integers
- On a set of integers, there are two basic binary operations, namely addition (denoted by +) and multiplication (denoted by ⋅), which satisfy the following well-known properties: Commutativity of addition and multiplication, Associativity of addition and multiplication, and Distributivity of multiplication over addition
- 1.3: Divisibility and the Division Algorithm
- We now discuss the concept of divisibility and its properties.
- 1.4: Representations of Integers in Different Bases
- In this section, we show how any positive integer can be written in terms of any positive base integer expansion in a unique way. Normally we use decimal notation to represent integers, we will show how to convert an integer from decimal notation into any other positive base integer notation and vise versa. Using the decimal notation in daily life is more traditional probably only because we have ten fingers.
- 1.5: The Greatest Common Divisor
- In this section we define the greatest common divisor (gcd) of two integers and discuss its properties. We also prove that the greatest common divisor of two integers is a linear combination of these integers.
- 1.6: The Euclidean Algorithm
- In this section we describe a systematic method that determines the greatest common divisor of two integers, due to Euclid and thus called the Euclidean algorithm.
Thumbnail: Subtraction-based animation of the Euclidean algorithm. (CC BY-SA 3.0; Proteins via Wikipedia)