Prime Numbers, The Greatest Common Divisor Worksheet

Prime Numbers, The Greatest Common Divisor Worksheet - Math 289

MATH 289

PROBLEM SET 4: NUMBER THEORY

1. The greatest common divisor

If d and n are integers, then we say that d divides n if and only if there exists an integer

q such that n = qd. Notice that if d divides n and m, then d also divides n + m and n

and an + bm for all integers a, b.

Theorem 1. If n and m are integers and m = 0, then there exists an integer q such that

n = qm + r

where 0 ≤ r < |m|.

Proof. First reduce to the case that n ≥ 0. Then use induction on n. (Exercise.)

A useful variation is the following result.

Theorem 2. If n and m are integers and m = 0, then there exists an integer q such that

n = qm + r

where

|m|/2 ≤ r < |m|/2.

Suppose that n and m are integers, not both equal to 0. The greatest common divisor

of n and m is the largest positive integer d such that d divides both n and m. We denote

the greatest common divisor of n and m by gcd(n, m). We will also use the convention that

gcd(0, 0) = 0. The following observation will be useful.

Lemma 3. If n, m, q ∈ Z, then We have gcd(n, m) = gcd(m, n

qm).

Proof. The case n = m = 0 is clear. Assume that at least one of n and m is nonzero. Now

gcd(n, m) divides n, m and n

qm, hence

gcd(n, m) ≤ gcd(m, n

qm).

On the other hand, gcd(m, n

qm) divides m, n

qm and n = (n

qm) + qm. so

gcd(m, n

qm) ≤ gcd(n, m).

Example 4. Suppose we have two large integers, say 9081 and 3270. How do we ﬁnd their

greatest common divisor? We do division with remainder:

(1)

9081 = 3 · 3270

729..

Now gcd(9081, 3270) = gcd(3270, 729). We have simpliﬁed our problem! Now we can play

this game again:

(2)

3270 = 4 · 729 + 354.

Prime Numbers, The Greatest Common Divisor Worksheet - Math 289