Integers are the building blocks of the theory of numbers. This chapter contains somewhat very simple and obvious observations starting with properties of integers and yet the proofs behind those observations are not as simple. In this chapter we introduce basic operations on integers and some algebraic definitions that will be necessary to understand basic concepts in this book. We then introduce the Well ordering principle which states basically that every set of positive integers has a smallest element. Proof by induction is also presented as an efficient method for proving several theorems throughout the book. We proceed to define the concept of divisibility and the division algorithm. We then introduce the elementary but fundamental concept of a greatest common divisor (gcd) of two integers, and the Euclidean algorithm for finding the gcd of two integers. We end this chapter with Lame’s Lemma on an estimate of the number of steps in the Euclidean algorithm needed to find the gcd of two integers.
- 1.2: The Well Ordering Principle and Mathematical Induction
- In this section, 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.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.7: Lame’s Theorem
- In this section, we give an estimate to the number of steps needed to find the greatest common divisor of two integers using the Euclidean algorithm. To do this, we have to introduce the Fibonacci numbers for the sake of proving a lemma that gives an estimate on the growth of Fibonacci numbers in the Fibonacci sequence. The lemma that we prove will be used in the proof of Lame’s theorem.