## The greatest common divisor and least common multiple

In this section, we introduce two commonly used and useful notations in number theory, the greatest common divisor and least common multiple.

Definition 1.2.11   Let and be integers. The greatest common divisor of is the largest integer satisfying both and . The greatest common divisor is denoted by either or simply by when there is no ambiguity.

The greatest common divisor of and is simply the largest positive integer which divides both and .

Definition 1.2.12   When then we say that are relatively prime.

Example 1.2.13   , , .

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.

Definition 1.2.14   Let and be integers. The least common multiple of is the smallest integer satisfying both and . The least common multiple is denoted by either or sometimes simply by (also, is sometimes used).

Example 1.2.15   , , .

The lcm can be computed from the gcd (which can be computed using the Euclidean algorithm) using the following fact.

Proposition 1.2.16   Let be integers.
(1)
.

(2)
If then .

(3)
If and then .

(4)
If and and then .

(5)
if and only if and .

(6)
If and then .

(7)
If and then .

(8)
If then .

(9)
For any integers we have .

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 .

Exercise 1.2.17   Find and and verify that their product is .

Exercise 1.2.18   Find all integers such that and .

Exercise 1.2.19   Find and guaranteed by the division algorithm for and .

Exercise 1.2.20   Show that if then .

Exercise 1.2.21   Prove the claim in the first proof of the division algorithm, theorem 1.2.7.

Exercise 1.2.22   For any integer , prove that:

(a) divides ,

(b) divides .

Exercise 1.2.23   Prove that if then . (In other words, and are relatively prime.)

Exercise 1.2.24   Show that for any integers and , divides .

Exercise 1.2.25   Prove that every square integer is of the form or , where is an integer.

Exercise 1.2.26   Prove that does not divide , for any integer .

Exercise 1.2.27   Prove that if does not divide an odd integer , then 24 divides .

Exercise 1.2.28   Find

(a) ,

(b) ,

(c) .

(d) ,

(e) .

Exercise 1.2.29   Suppose is an odd integer. Find a formula for .

Suppose is an even integer. Find a formula for .

Exercise 1.2.30   Verify that (6) in Proposition 1.2.16 is true.

Exercise 1.2.31   Verify that (8) in Proposition 1.2.16 is true.

Exercise 1.2.32   Verify that (9) in Proposition 1.2.16 is true.

Exercise 1.2.33   Suppose is an integer. Find .

Exercise 1.2.34   Suppose is an odd integer. Find .

Suppose is an even integer. Find .

Exercise 1.2.35 (a)   Find .

(b) Find .

(c) Find .

Exercise 1.2.36   Let denote the combinatorial symbol choose (also called a binomial coefficient), where is factorial. This is the coefficient of in the binomial expansion of ,

These can be computed by hand using Pascal's triangle,

Check , for .

Exercise 1.2.37   Factor all the integers .

Exercise 1.2.38   Show that , for . Show that , for . Is there some such that ?

David Joyner 2007-09-03