Example 1.4.1.
\(\gcd(6,15)=3\text{,}\) \(\gcd(3,18)=3\text{,}\) \(\gcd(4,9)=1\text{.}\)
Section 1.4 Basic facts about the integers
The integers are the building blocks of mathematics and we will list here a few facts that will soon be needed.
Subsection 1.4.1 Even and Odd integers
An integer \(n\) is even if it is twice another integer. Another way to say this is that \(m\) is divisible by 2. So \(n\) is even if \(n=2m\) where \(m\) is another integer. For example, 10 is even because it is twice 5.
An integer is odd if it is one more than twice another integer, which is the same as saying that it is not divisible by 2. So \(n\) is odd if \(n=2m+1\) for some other integer \(m\text{.}\) For example, 9 is odd because it is one more than twice 4. We could also say an odd integer is 1 less than twice another integer, or \(n=2m-1\text{.}\) So 9 is 1 less than twice 5. Every integer is either even or odd. So the negation of “\(n\) is even” is “\(n\) is odd”.
So the positive even integers (or positive even natural numbers) are the elements of the set
\begin{equation*}
\{2,4,6,\ldots\} = \{x\in {\mathbb N}| x=2m \mbox{ for some } m\in {\mathbb N}\}
\end{equation*}
and the positive odd integers are the elements of the set
\begin{equation*}
\{1,3,5,\ldots\} = \{x\in {\mathbb N}| x=2m+1 \mbox{ for some } m\in {\mathbb N}\}.
\end{equation*}
Subsection 1.4.2 Divisibility
If \(n\) and \(m\) are integers, and \(m\neq 0\text{,}\) we say that \(n\) is divisible by \(m\) if \(n=km\) for some integer \(k\text{.}\) In this case we say that \(k\) is the quotient of the division. We also say that \(k\) and \(m\) are factors, or divisors of \(n\text{.}\) Another way of saying that \(n\) is divisible by \(m\) is saying that \(n/m\) is an integer. Note that according to this definition, 0 is divisble by any \(m\neq 0\) (using \(k=0\) as the quotient).
Given two integers \(n\) and \(m\text{,}\) the greatest common divisor (often abbreviated by \(\gcd(m,n)\) ) of \(n\) and \(m\) is the largest integer that is a divisor of both. So if \(d=\gcd(m,n)\) then \(d\) divides both \(n\) and \(m\text{,}\) and there is no integer larger than \(d\) that does the same.
A rational number can be written in many different ways, because we can always multiply or divide both numerator and denominator by the same number. So for example
\begin{equation*}
\frac{4}{6}=\frac{2}{3}=\frac{10}{15}.
\end{equation*}
But given any rational number \(\frac{p}{q}\text{,}\) we can divide both \(p\) and \(q\) by their gcd and obtain a fraction in lowest terms, meaning that it cannot be written using lower values of numerator or denominator. So \(\frac{2}{3}\) is the lowest terms form for \(\frac{4}{6}\) and \(\frac{10}{15}\text{.}\)
Subsection 1.4.3 The Well-Ordering Principle
We now notice one property of the natural numbers that the integers and the rationals do not have: \(\mathbb N\) has a least element, the number 1, because \(1\lt n\) for all \(n\in {\mathbb N}, n\neq 1\text{.}\) In fact this property is shared with any subset of \(\mathbb N\text{.}\) It is an axiom, that is, a statement that is taken to be true without proof.
Axiom 1.4.2. The Well-Ordering Principle.
Suppose \(S\) is a non-empty subset of \(\mathbb N\text{.}\) Then \(S\) has a least element.
So for example the least element of the even numbers is \(2\text{.}\) The Well-Ordering Principle (that we abbreviate as WOP) surely makes sense, because our intutition tells us that of course, if we have a set of positive integers, one of them must be the smallest. But, as it often happens when we are dealing with sets that contain infinitely many elements, this property cannot be proved from the other properties of the natural numbers.
We stress that the WOP is a special property of the positive integers. For \(\mathbb Z\text{,}\) WOP fails in an obvious way: just consider \(\mathbb Z\) itself. What is its smallest element? Of course it does not exist, because we can take negative integers as large as we want. In the case of the rational numbers \(\mathbb Q\text{,}\) there is another, more subtle reason why the WOP fails, quite different from the fact that we can take larger and larger negative numbers. We can consider the set
\begin{equation*}
S=\left\{\left. \frac{1}{n} \right| n\in {\mathbb N} \right\}.
\end{equation*}
Then \(S\) is a non-empty subset of \(\mathbb Q\text{,}\) but it has no least element. This should be intuitively clear, because we can make \(n\) larger and larger and get \(1/n\) as small as we want, and there will not be a smallest value. We will discuss this in more depth in the next chapter.
