    Next: The Euclidean algorithm Up: The integers Previous: Division   Contents

## The Euclidean Division

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:
1. and ,
2. 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 . Lemma 6.2.21   If , and with , and then .

Proof. If and then and thus . In particular, . Now note that if and then and thus . Therefore and hence .     Next: The Euclidean algorithm Up: The integers Previous: Division   Contents
root 2002-06-10