Greatest Common Divisor (GCD)

Every divisor of a also divides 0.

So the common divisors of a and 0 are exactly the divisors of a.

The greatest positive divisor of a is

Therefore,

The common divisors of a and a are exactly the divisors of a.

The greatest positive divisor of a is

Therefore,

The only positive divisor of 1 is 1.

Therefore, the only possible positive common divisor of a and 1 is 1.

Hence

A positive integer d divides a if and only if it divides |a|.

Similarly,

Therefore, a, b and |a|, |b| have exactly the same positive common divisors.

Hence

for any integer k.

We show that the two pairs have exactly the same common divisors.

Suppose

Then

so

Therefore, every common divisor of a and b is also a common divisor of a + kb and b.

Now suppose

Then

so

Hence

Therefore, every common divisor of a + kb, b is also a common divisor of a, b.

So the two pairs have exactly the same common divisors.

Hence

Similarly,

If

then

Since

we have

Using Property 5,

Therefore,

Using symmetry,

Hence

In particular, if r is the remainder when a is divided by b, then

so

Find all possible values of

as n ranges over the positive integers.

Find all possible values of