Prime Numbers, The Greatest Common Divisor Worksheet - Math 289

ADVERTISEMENT

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
m
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 find their
greatest common divisor? We do division with remainder:
(1)
9081 = 3 · 3270
729..
Now gcd(9081, 3270) = gcd(3270, 729). We have simplified our problem! Now we can play
this game again:
(2)
3270 = 4 · 729 + 354.
1

ADVERTISEMENT

00 votes

Related Articles

Related forms

Related Categories

Parent category: Education
Go
Page of 8