The theory of numbers, by Robert D. Carmichael ...

20

THEORY OF NUMBERS

integers a and p satisfying this relation; for, if so, d would be
a divisor of the first member of the equation and not of the
second. Thus we have the following theorem:
IV. A necessary and suilfcient condition that m and n are
relatively prime is that there exist integers a and 3 such that
am - On I.
The theory of the greatest common divisor of three or more
numbers is based directly on that of the greatest common
divisor of two numbers; consequently it does not require to
be developed in detail.
EXERCISES
i. If d is the greatest common divisor of m and n, then m/d and n/d are relatively prime.
2. If d is the greatest common divisor of m and n and k is prime to n, then
d is the greatest common divisor of kmn and n.
3. The number of multiplies of b in the sequence a, 2a, 3a,..., ba is equal
to the greatest common divisor of a and b.
4. If the sum or the difference of two irreducible f-actions is an integer, the
denominators of the fractions are equal.
5. The algebraic sum of any number of irreducible fractions, whose denominators are primeeach to each, cannot be an integer.
6*. The number of divisions to be effected in finding the greatest common
divisor of two numbers by the Euclidian' algorithm does not exceed five times
the number of digits in the smaller number (when this number is written in the
usual scale of io).
~ o1. THE LEAST COMMON MULTIPLE OF TWO OR MORE
INTEGERS
I. The common multiples of two or more numbers are the
multiples of their least common multiple.
This may be readily proved by means of the unique factorization theorem. The method is obvious. We shall, however,
give a proof independent of this theorem.
Consider first the case of two numbers; denote them by
m and n and their greatest common divisor by d. Then we
have
m=diL, n=dy,
where A and v are relatively prime integers. The common
multiples sought are multiples of m and are all comprised in the