Proposition 6.2.18
Given ,
there exists a unique pair of integers
such that
and
.

The number is called the quotient and the number is called the remainder in the division of by .

Proof.
Take the largest possible such that
and put
.
Then
since
but
. Now suppose
that
with ,
and
.
Then
and
. But
so that and hence .

It is clear that if, and only if, in the above.

Definition 6.2.19
Given ,
then
is the greatest common divisor of and if:

and ,

if and then (
).

The greatest common divisor (henceforth gcd) of and is
written or
.
The gcd is obviously unique: if and are both gcd's then
they both divide each other and are therefore equal.

Theorem 6.2.20 (Existence of the gcd)
For ,
exists. Moreover there exist integers
and such that
.

Proof.
Consider the set
. Then
so let be the least
member of . Now
such that
, so that if and then
.
Now write
with ,
,
. We
have
. So , as otherwise
: contrary to minimal. Similiarly, and thus
is the gcd of and .