If you remember the the greatest common divisor (GCD) from elementary education, congrats! You're doing well so far. Where this treatment differs is to consider divisibility properties and the GCD as more abstract properties. Though this is still in the context of the integers (because it's introductory number theory, after all), the focus will be more on the structural properties of numbers more generally and how to prove these properties rather than simply calculating the GCD of a collection of numbers - though we will eventually get to that! The goal here is to build up a more generalized toolset and see how mathematical reasoning generally works in a setting with more comfortable objects and concepts. First, we will cover some general properties of integers and collections of integers that will be useful for proving subsequent statements later on. Note that we are not going to construct the integers through set-theoretic definitions, because that's a matter well beyond the scope of this treatment. It's often useful in mathematics to actually start in familiar territory - in this case, the familiar setting integers - take some known properties for granted, work out some details, and then come back later to backfill details. Think of the integers here as to math as "middle-sized dry goods" are to physics - the physics student often starts off with classical mechanics well before going to considering forces at the atomic level.
As to the structure of this page, it will often be the case that the subheading will be a summary of a property, definition, or theorem, followed by a full statement. After that will be commentary that is hopefully useful for understanding context of the statement, making reference to Dudley's text, or what material one might see elsewhere. This structure is chosen to make it easy to scan through the page to find a desired result by scrolling past headers, while also providing more conversational addenda in paragraph form following.
The integers consist of the positive natural numbers, their negatives, and zero.
This means we're considering the entire collection of $\{1, 2, 3,\dots\}$ (the positive natural numbers), $0$, the additive identity, and their additive inverses, $\{-1, -2, -3, \dots\}$, to create a set $\{ \dots, -3, -2, -1, 0, 1, 2, 3, \dots \}$. Note that by specifying the positive natural numbers, I am making no hard stance here on the apparently contentuous issue as to whether the natural numbers include zero! (Zero is neither positive nor negative - or, if you prefer, it is unsigned.) Do not wade into these debates, for each person generally uses whichever definition is most convenient for their own purposes. If you're in a field where you need to index starting at zero frequently, you might as well say it's in the naturals; if you're in a field where you index more frequently starting at one, you're more likely to start the naturals at one! It's that simple.
The sum of two integers is itself an integer; the difference of two integers is itself an integer; and the product of two integers is itself an integer.
This property is not explicitly stated in Dudley's text, but would likely be stated in a more abstract text, and it is an implicit observation that can sometimes be tkaen for granted. It also serves to introduce us to the main operations we'll be seeing in this context, as these are the operations that play nicely with integers. Note that division specifically does not work this way - or rather, we would say that the integers are not closed under division. The numbers $-1$ and $2$ are both integers, but $-\frac{1}{2}$ is not. Incorporating division into the integers requires you take the entire field of the rational numbers. And yes, field has a specific definition, particular to abstract algebra.
A nonempty set of integers that is bounded below/above contains a least/greatest element, respectively.
This is, in other texts, often called the well-ordering principle, and there is a non-negligble chance I may accidentally use that terminology instead. This boundedness property tells us another very useful thing: a set of integers that is bounded above and below both must be finite. Hopefully you can convince yourself of it. A more advanced setting might actually prove both of these properties of the integers, but
Note: A more advanced (advanced undergraduate or above) text might prove this starting from a construction of the integers, but this is not that text. It is simply stated as an observation at the beginning, as the reader is assumed to be familiar with the integers. This observation does not become relevant until we get to the greatest common divisor.
Def. We say that $a$ divides $b$ if and only if there is an integer $d$ (here, divisor) such that $ad = b$. We write this as $a \vert b$.
We've reached our first definition of this section! Now note that what is being said here. If $a$ divides $b$, then some multiple of $a$ equals $b$. We might also call $a$ a factor of $b$, which will be more useful terminology in the later context of factorization. Note that $a$ can be negative! For example, $-2$ divides $4$ since $(-2)(-2) = 4$. As an additional bit of notation, if $a$ does not divide $b$, we may denote it as $a \nmid b$, using the common convention of introducing a strikethrough to indicate that something does not hold. Here, we'll stop and consider a few simple exercises about divisibility of integers.
Exercise 1.1: Which integers divide 6?
Exercise 1.2 Which integers divide 1?
Exercise 1.3 Which integers divide zero? Can you provide a proof of this?
Exercise 1.4 Provide a proof or offer a counterexample if the statement is false: If $a \vert b$ and $b \vert c$, then $a \vert c$.
A lemma (pl. lemmata) is a "small" result that is useful in proving a more important result later on. This means that what might be a lemma in one context might be a theorem in another! It's weird and confusing, but don't worry too much about the distinction. Use and experience build judgement as to what the "main" result. Here, since we're building up to the greatest common divisor, that these results are called lemmata suggest they will be useful for showing results related to the GCD.
Lemma 1.1. The divisor of two numbers is also a divisor of their sum.
Statement: If $d \vert a$ and $d \vert b$, then $d \vert (a+b)$.
Proof: By definition, there are integers $f$ and $g$ such that $df = a$ and $dg = b$. Therefore, $d(f+g) = (a+b)$. Since $f$ and $g$ are integers, $(f+g)$ is an integer by closure, and so $d \vert (a+b)$.
Observe that the strategy here essentially requires taking two equations, summing them, and re-grouping the terms. This is a common strategy for proofs of this type, and it will be seen even more frequently later on. Also, note that the converse of this statement does not hold! As a example for why the converse fails, consider that $8+7 = 15$, and $3 \vert 15$ and $5 \vert 15$, but $3 \nmid 8$, $3 \nmid 7$, $5 \nmid 8$, and $3 \nmid 8$.
Lemma 1.2. The divisor of a collection of integers is a divisor of any linear combination of those integers.
Note: The text does not use this vocabulary in calling it a linear combination, but the recognition of this as such is very useful shorthand and is standard in other contexts. Essentially, it's stating that, given a collection of values, we can take any multiple of any particular element, and any sums of those subsequent multiples. The notation below might actually be clearer than the words.
Statement: If $d \vert a_1$, $d \vert a_2$, $\dots$, $d \vert a_n$, then $d \vert (c_1 a_1 + c_2 a_2 + \cdots + c_n a_n)$ for any integers $c_1, c_2, \dots, c_n$.
Proof: By definition, there are integers $q_1, q_2, \dots q_n$ such that $dq_1 = a_1$, $dq_2 = a_2$, $\dots$, $dq_n = a_n$. Therefore, $c_1a_1 + c_2a_2 + \cdots + c_na_n = d(c_1q_1 + c_2q_2 + \cdots + c_nq_n)$. By closure of integers under multiplication and addition, the term in the parentheses is itself an integer, proving the statement.
This is one of the earliest results that gives way to some practical(ish) calculations: what cash values are impossible with a fixed number of coins? The trick is to set up two linear equations, take the difference, and exploit divisibility properties. The exercise in Dudley on this example is totally worthwhile, but will not be replicated because I don't want copyright folks breathing down my neck for reproducing his text verbatim for each exercise and example.
Def. We say $d$ is the greatest common divisor (or GCD) of $a$ and $b$ if and only if
We may use the notation $d = (a, b)$ to denote this property.
Note 1: The parenthesis notation is common if you're restricting your writing to number theory and divisibility, but it is also common to see $d = gcd(a,b)$ as well - and this is strongly prefered if there is any chance of confusion with the notation for ordered pairs. Here, $(a,b)$ is fine because of the very restricted topic. If we were talking about points on the Euclidean plane as well in other parts, we would absolutely need the more explicit notation.
Note 2: The existence of the GCD requires greatest integer property. As long as $a$ and $b$ are not both $0$ (recall: all integers divide $0$), then the set of divisors is bounded above by the greatest of these two integers and their negatives (and below by the least of those four). The collection of divisors is therefore finite, and contains a greatest element, which is what part (ii) does - picks out that element. It may be worth considering briefly that, subsequently, the largest value the GCD of $a$ and $b$ may take on is the value of the lesser magnitude. (Given an integer $a$, the magnitude of $a$ is the absolute value of $a$, or $\lvert a \rvert$. We need to specify this in case either of $a$ or $b$ are negative.)
This also means $(0,0)$ is undefined, since those sets of divisors are unbounded. Going foward in proofs and exercises, we will generally assume an arbitrary $(a,b)$ is such that $a$ and $b$ are not both zero, and the greated common divisor is defined.
Exercise 1.5. What is $(n,1)$? What about $(n,0)$?
Exercise 1.6. If $d$ is a positive integer, what is $(d,nd)$?
Aside: It's D&D!
Note: The concept of primality, and of relative primes (co-primes) will be discussed more heavily in the next chapter, but using the term here explicitly serves to foreshadow the importance of this theorem.
Theorem 1.1. If $(a,b) = d$, then $\left(\frac{a}{d}, \frac{b}{d}\right) = 1$.
Note: The proof of this theorem uses a common strategy that is employed throughout math. It exploits the fact that if you can put a lower bound and an upper bound on a value, and those bounds are the same, then the result is that value. This strategy is often leveraged when you have inequalities available by other theorems or lemmata and definitions. The last step is explicitly stated here, but is generally omitted from proofs of this nature as apparent to the reader.
Proof: Let $c = \left(\frac{a}{d}, \frac{b}{d}\right)$. First, we will show that $c \geq 1$. From exercise 1.5, we showed that $1$ divides any integer, so it is a lower bound on any GCD; therefore, $c \geq 1$. Next, we will show that $c \leq 1$. Since the GCD is $c$, $c \vert \frac{a}{d}$ and $c \vert \frac{b}{d}$. Specifically, there is a pair of integers, $q$ and $r$, such that $cq = \frac{a}{d}$ and $cr = \frac{b}{d}$. Rearranging these equalities gives us that $(cd)q = a$ and $(cd)r = b$. From this we see that $cd$ is a common divisor of both $a$ and $b$, and the product $cd$ cannot be greater than $d$ - else $d$ would not be the greatest common divisor. Since $d$ is positive, it follows then that $c \leq 1$. Having shown $c \geq 1$ and $c \leq 1$, we must conclude that $c = 1$.
This is a reasonable place to stop and review what's been covered so far. We've gone over the definitions of divisibility and the greatest common divisor, and a few related results about how these behave structurally within the context of the integers. We've introduced the idea of relatively prime numbers, foreshadowing prime factor decomposition in a later lesson. In the next lesson, we'll be looking at integer division (with remainders) and the Euclidean algorithm for finding the GCD without enumerating lists of divisors. At the end follows a few exercises suggested by Dudley with solutions using what's been covered so far.
Exercise 1.7. Prove that if $a \vert b$ and $b \vert a$, then $a = b$ or $a = -b$.
Exercise 1.8. Prove that if $a \vert b$ and $a \gt 0$, then $(a,b) = a$.
Exercise 1.9. Prove that $((a,b),b) = (a,b)$.
Exercise 1.10. Prove: If $a \vert b$ and $c \vert d$, then $ac \vert bd$.
Exercise 1.11. Prove: If $d \vert a$ and $d \vert b$, then $d^2 \vert ab$.
Exercise 12. If $N = abc+1$, prove that $(N,a)=(N,b)=(N,c)=1$.
Background: Mathematics 3D Blender Illustration
Credit: MasterTux
Source: creazilla
License: CC0-1.0
Modifications: Rotated and darkened