1: Introduction
- Page ID
- 8823
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.1: Algebraic Operations With Integers
- While the set of all positive integers, denoted by N, is defined by N={1,2,3,4,...}. On Z, there are two basic binary operations, namely addition (denoted by +) and multiplication (denoted by ⋅), that satisfy some basic properties from which every other property for Z emerges.
- 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.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 simply better because we have ten fingers which facilitates all the mathematical operations.
- 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. This method is called the Euclidean algorithm.
- 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.
Contributors and Attributions
Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.