In this section, we introduce two commonly used and useful notations in number theory, the greatest common divisor and least common multiple.
The greatest common divisor of and is simply the largest positive integer which divides both and .
To return to the question above, we now know that the set of all possible sums and differences of two integers and is of the form , for some . What is ? This question is answered in the section on the Euclidean algorithm later in this chapter
As we saw above, the gcd is the largest integers which divides both and . Somewhat analogous to this is the least integer which both and divide.
The lcm can be computed from the gcd (which can be computed using the Euclidean algorithm) using the following fact.
The reader can use the examples above to verify (1) in the cases .
proof of (1): We will show that . Note that , since divides . Therefore, .
Since , we know that is a multiple of . Similarly, (why?) implies that .
Now (why?) and since divides . Therefore, divides . Similarly, divides . Thus:
Since we have shown the inequality in both directions, we must have equality.
Later, part (1) of this proposition shall be proven again, but as a consequence of the Fundamental Theorem of Arithmetic.
We prove (2) below since it will be used in the proof of the Fundamental Theorem of Arithmetic.
proof of (2): For the proof of this part, we shall use a result which will not be proven until later in this chapter. Assume . Let . By the Euclidean algorithm (Theorem 1.4.3 below), there are integers such that , so . Since divides and (by assumption), it divides , hence .
Part (4) shall also be proven later as a consequence of the Fundamental Theorem of Arithmetic. Parts (3), (6), (8), (9) are left as exercises.
proof of (7): We will prove this by contradiction. Suppose that . Then is not an integer, and we may write it as:
Multiplying both sides of the above inequality by the positive integer gives: . Let . Then:
But and , so is a common multiple of and which is less than the least common multiple , by the above inequality. Thus we have reached a contradiction, and our original assumption was false. We conclude that .
(a) divides ,
(b) divides .
Suppose is an even integer. Find a formula for .
Suppose is an even integer. Find .
(b) Find .
(c) Find .
These can be computed by hand using Pascal's triangle,
Check , for .