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.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.