Number Theory • Topic 6

GCD (Greatest Common Divisor)

The GCD connects divisibility with linear combinations.

Definition

Definition (GCD)

The greatest common divisor of integers

a

and

b

(not both zero), denoted

g cd (a, b)

or simply

(a, b)

, is the largest positive integer

d

such that

d ∣ a

and

d ∣ b

To compute

g cd (a, b)

efficiently:

a = b q + r ⟹ g cd (a, b) = g cd (b, r)

Repeat until remainder is 0.

Example

g cd (252, 105)

Integers

a, b

are coprime (or relatively prime) if

g cd (a, b) = 1

Exercise (Problem 1)

Prove that

g cd (n, n + 1) = 1

for any integer

n

Exercise (Problem 2)

Prove that for any positive integer

n

, the fraction

\frac{21 n + 4}{14 n + 3}

is irreducible.

Exercise (Problem 3)

g cd (a, b) = 1

, prove that

g cd (a + b, a - b)

is either 1 or 2.