Number Theory: An Introduction to Mathematics

II Divisibility..................................................

1 GreatestCommonDivisors

In the setNof all positive integers we can perform two basic operations: addition and
multiplication. In this chapter we will be primarily concerned with the second opera-
tion.

Multiplication has the following properties:

(M1)if ab=ac,then b=c; (cancellation law)

(M2)ab=ba for all a,b; (commutative law)

(M3)(ab)c=a(bc)for all a,b,c; (associative law)

(M4) 1 a=a for all a. (identity element)

For anya,b∈Nwe say thatb divides a,orthatbis afactorofa,orthatais a
multipleofbifa=ba′for somea′∈N. We writeb|aifbdividesaandb
aifbdoes
not dividea. For example, 2|6, since 6= 2 ×3, but 4
6. (We sometimes use×instead
of·for the product of positive integers.) The following properties of divisibility follow
at once from the definition:

(i)a|a and 1 |a for every a;
(ii)if b|a and c|b,then c|a;
(iii)if b|a,then b|ac for every c;
(iv)bc|ac if and only if b|a;

(v)if b|a and a|b,then b=a.

For anya,b∈Nwe say thatdis acommon divisorofaandbifd|aandd|b.We
say that a common divisordofaandbis agreatest common divisorif every com-
mon divisor ofaandbdividesd. The greatest common divisor ofaandbis uniquely
determined, if it exists, and will be denoted by(a,b).
The greatest common divisor ofaandbis indeed thenumericallygreatest com-
mon divisor. However, it is preferable not to define greatest common divisors in this
way, since the concept is then available for algebraic structures in which there is no
relation of magnitude and only the operation of multiplication is defined.

W.A. Coppel, Number Theory: An Introduction to Mathematics, Universitext, 83
DOI: 10.1007/978-0-387-89486-7_2, © Springer Science + Business Media, LLC 2009