Read an Excerpt
Elements of Number Theory
By I. M. Vinogradov, Saul Kravetz Dover Publications, Inc.
Copyright © 1954 Dover Publications, Inc.
All rights reserved.
ISBN: 978-0-486-16035-1
CHAPTER 1
DIVISIBILITY THEORY
§1. Basic Concepts and Theorems
a. The theory of numbers is concerned with the study of the properties of integers. By integers we mean not only the numbers of the natural number sequence 1,2,3, ... (the positive integers) but also zero and the negative integers: –1, –2, –3,....
As a rule, in presenting the theoretical material, we will use letters only to denote integers. In the cases in which letters may denote non-integers, if this is not clear in itself, we will mention it specifically.
The sum, difference and product of two integers a and b are also integers, but the quotient resulting from the division of a by b (if b is different from zero) may be an integer or a non-integer.
b. In the case in which the quotient resulting from the division of a by b is an integer, denoting it by q , we have a = bq, i.e. a is equal to the product of b by an integer. We will then say that a is divisible by b or that b divides a. Here a is said to be a multiple of b and b is said to be a divisor of the number a. The fact that b divides a is written as: b\a.
We have the following two theorems.
1.If a is a multiple of m, and m is a multiple of b, then a is a multiple of b.
Indeed, it follows from a = a1m, m = m1b that a = a1m1b, where a1m1 is an integer. But this proves the theorem.
2.If we know that in an equation of the form k + l + ... + n = p + q + ... + s, all terms except one are multiples of b, then this one term is also a multiple of b.
Indeed, let the exceptional term be k. We have
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],
proving our theorem.
c. In the general case, which includes the particular case in which a is divisible by b, we have the theorem:
Every integer a is uniquely representable in terms of the positive integer b in the form
a = bq + r, 0 < r < b
Indeed, we obtain one such representation of a by taking bq to be equal to the largest multiple of b which does not exceed a. Assuming that we also have a = bq1 + r1, 0 < r1< b, we find that 0 = b(q – q1) + r – r1, from which it follows (2, b) that r – r1 is a multiple of b. But since [absolute value of r – r1] < b, the latter is only possible if r – r1 = 0, i.e. if r = r1, from which it also follows that q = q1.
The number q is called the partial quotient and the number r is called the remainder resulting from the division of a by b.
Examples. Let b = 14. We have
177 = 14 12 + 9, 0 < 9 < 14;
-64 = 14 (-5) + 6, 0 < 6 < 14;
154 = 14 11 + 0, 0 = 0 < 14.
§2. The Greatest Common Divisor
a. In what follows we shall consider only the positive divisors of numbers. Every integer which divides all the integers a, b, ..., l is said to be a common divisor of them. The largest of these common divisors is said to be their greatest common divisor and is denoted by the symbol (a, b, ..., l). In view of the finiteness of the number of common divisors the existence of the greatest common divisor is evident. If (a, bL ..., l) = 1, then a, b, ..., l are said to be relatively prime. If each of the numbers a, b, ..., l is relatively prime to any other of them, then a, b, ..., l are said to be pairwise prime . It is evident that pairwise prime numbers are also relatively prime; in the case of two numbers the concepts of "pairwise prime" and "relatively prime" coincide.
Examples. The numbers 6, 10, 15 are relatively prime since (6,10, 15) = 1. The numbers 8, 13, 21 are pairwise prime since (8, 13) = (8, 21) = (13, 21) = 1.
b. We first consider the common divisors of two numbers.
1.If a is a multiple of b, then the set of common divisors of the numbers a and b coincides with the set of divisors of b; in particular, (a, b) = b.
Indeed, every common divisor of the numbers a and b is a divisor of b. Conversely, if a is a multiple of b, then (1, b, §1) every divisor of the number b is also a divisor of the number a, i.e. it is a common divisor of the numbers a and b. Thus the set of common divisors of the numbers a and b coincides with the set of divisors of b, but since the greatest divisor of the number b is b itself, we have (a, b) = b,
2.If
a = bq + c,
then the set of common divisors of the numbers a and b coincides with the set of common divisors of the numbers b and c; in particular, (a, b) = (b, c).
Indeed, the above equation shows that every common divisor of the numbers a and b divides c (2, b, §1) and therefore is a common divisor of the numbers b and c. Conversely, the same equation shows that every common divisor of the numbers b and c divides a and consequently is a common divisor of the numbers a and b. Therefore the common divisors of the numbers a and b are just those numbers which are also common divisors of the numbers b and c; in particular, the greatest of these divisors must also coincide, i.e. (a, b) = (b, c).
c. In order to obtain the least common divisor as well as to deduce its most important properties, Euclid's algorithm is applied. The latter consists of the following process. Let a and b be positive integers. By c, §1, we find the sequence of equations:
(1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
which terminates when we obtain some rn+1 = 0. The latter must occur since the sequence b, r2, r3, ... as a decreasing sequence of integers cannot contain more than b positive integers.
d. Considering the equations of (1), proceeding from the top down, (b) shows that the common divisors of the numbers a and b are identical with the common divisors of the numbers b and r2, are moreover identical with the common divisors of the numbers r2 and r3, of the numbers rand r4, ..., of the numbers rn-1 and rn, and finally with the divisors of the number rn. Along with this, we have
(a, b) = (b, r2) = (r2, r3) = ... = (rn-1, rn) = rn.
We arrive at the following results.
1.The set of common divisors of the numbers a and b coincides with the set of divisors of their greatest common divisor.
2.This greatest common divisor is equal to rn, i.e. the last non-zero remainder in Euclid's algorithm.
Example, We apply Euclid's algorithm to the evaluation of (525, 231). We find (the auxiliary calculations are given on the left)
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
Here the last positive remainder is r4 = 21. This means that (525, 231) = 21.
e.1.If m denotes any positive integer, we have (am, hm) = (a, b)m.
2.If δ is any common divisor of the numbers a and b, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; in particular, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] the quotients resulting from the division of two numbers by their greatest common divisor are relatively prime numbers.
Indeed, multiply each of the terms of the equations (1) by m. We obtain new equations, where a, b, r2, ..., rn are replaced by am, bm, r2m, ..., rnm. Therefore (am, bm) = rnm, showing that proposition 1 is true.
Applying proposition 1, we find that
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII];
and this proves proposition 2.
f.1.If (a, b) = 1, then (ac, b) = (c, b).
Indeed, (ac, b) divides ac and bc, which implies (1, d) that it also divides (ac, bc) which is equal to c by 1, e; but (ac, b) also divides b and therefore also divides (c, b). Conversely, (c, b) divides ac and b, and therefore also divides (ac, b). Thus (ac, b) and (c, b) divide each other and are therefore equal to one another.
2.If (a, b) = 1 and ac is divisible by b, then c is divisible by b.
Indeed, since (a, b) = 1, we have (ac, b) = (c, b). But if ac is a multiple of b, then (1, b) we have (ac, b) = b, which means that (c, b) = b, i.e. c is a multiple of b.
3.If each a1, a2, ..., am is relatively prime to each b1, b2, ..., bn, then the product a1a2 ... am is relatively prime to the product b1b2 ... bn.
Indeed (theorem 1), we have
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],
and moreover, setting a1a2 ... am = A, in the same way we find
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
g. The problem of finding the greatest common divisor of more than two numbers reduces to the same problem for two numbers. Indeed, in order to find the greatest common divisor of the numbers a1, a2, ..., an we form the sequence of numbers:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
The number dn is also the greatest common divisor of all the given numbers.
Indeed (1, d), the common divisors of the numbers a1 and a2 coincide with the divisors of d2; therefore the common divisors of the numbers a1, a2 and a3 coincide with the common divisors of the numbers d2 and a3, i.e. coincide with the divisors of d3. Moreover, we can verify that the common divisors of the numbers a1, a2, a3, a4 coincide with the divisors of d4 and so forth, and finally, that the common divisors of the numbers a1, a2, ..., an coincide with the divisors of dn. But since the largest divisor of dn is dn itself, it is the greatest common divisor of the numbers a1, a2, ..., an.
Considering the above proof, we can see that theorem 1, d is true for more than two numbers also. Theorems 1, e and 2, e are also true, because multiplication by m or division by δ of all the numbers a1, a2, ..., an causes all the numbers d1, d2, ..., dn to be multiplied by m or to be divided by δ.
§3. The Least Common Multiple
a. Any integer which is a multiple of each of a set of given numbers, is said to be their common multiple. The smallest positive common multiple is called the least common multiple.
b. We first consider the least common multiple of two numbers. Let M be any common multiple of the integers a and b. Since it is a multiple of a, M = ak, where k is an integer. But M is also a multiple of b, and hence
ak/b
must also be an integer which, setting (a, b) = d, a = a1d, b = b1d , can be represented in the form a1k/b1, where (a1, b1) = 1 (2, e, §2). Therefore (2, f, §2) k must be divisible by b1, k = b1t = b/d t, where t is an integer. Hence
M = ab/d t.
Conversely, it is evident that every M of this form is a multiple of a as well as b, and therefore, this form gives all the common multiples of the numbers a and b.
The smallest positive one of these multiples, i.e. the least common multiple, is obtained for t = 1. It is
m = ab/d.
Introducing m, we can rewrite the formula we have obtained for M as:
M = mt.
The last and the next to the last equations lead to the theorems:
1.The common multiples of two numbers are identical with the multiples of their least common multiple.
2.The least common multiple of two numbers is equal to their product divided by their greatest common divisor.
c. Assume that we are now required to find the least common multiple of more than two numbers a1, a2, ..., an. Letting the symbol m(a, b) denote the least common multiple of the numbers a and b, we form the sequence of numbers:
m(a1, a2) = m2, m(m2, a3) = m3, ..., m(mn- 1, an) = mn.
The mn obtained in this way will be the least common multiple of all the given numbers.
Indeed (1, b), the common multiples of the numbers a1 and a2 coincide with the multiples of m2, and hence the common multiples of the numbers a1, a2 and a3 coincide with the common multiples of m2 and a3, i.e. they coincide with the multiples of m3. It is then clear that the common multiples of the numbers a1, a2, a3, a4 coincide with the multiples of m4, and so forth, and finally, that the common multiples of the numbers a1, a2, ..., an coincide with the multiples of mn, and since the smallest positive multiple of mn is mn itself, it is also the least common multiple of the numbers a1, a2, ..., an.
(Continues...)
Excerpted from Elements of Number Theory by I. M. Vinogradov, Saul Kravetz. Copyright © 1954 Dover Publications, Inc.. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
