LII. THEORY OF NUMBERS. 684. Throughout the present Chapter the word number is used as an abbreviation for positive integer. 685. A number which can be divided exactly by no number except itself and unity is called a prime number, or shortly a prime. 686. Two numbers are said to be prime to each other when there is no number, except unity, which will divide each of them exactly. Instead of saying that two numbers are prime to each other, the same thing is expressed by saying that one of them is prime to the other. 687. If a number p divides a product ab, and is prime to one factor a, it must divide the other factor b. Suppose a greater than p; perform the operation of finding the greatest common measure of a and p; let q, I'‚ L′′ ̋‚ ... be the successive quotients, and r, r', r',... the corresponding remainders. Thus a = pq+r, p=rq+r', r = r'q"+r", ... multiply each member of each of these equations by b, and divide br tions that br Ρ is an integer, it follows from the first of these equa is an integer; then from the second of these equations is an integer; then from the third is an integer; and so br" on. But, since a and p are prime to each other, the last of the bx 1 remainders r, r', r", ... is unity; therefore is an integer; that Р is, b is divisible by p. 688. When the numerator and denominator of a fraction are prime to each other the fraction cannot be reduced to an equivalent fraction in lower terms. α Suppose that a is prime to b, and, if possible, let & be equal therefore b divides ab'; but b is prime to a, therefore b divides b′ (Art. 687); but this is impossible, since b' is less than 6 by sup a position. Hence cannot be reduced to an equivalent fraction in lower terms. b ̄b'' 689. If a is prime to b, and, then a' and b’' must be the same multiples of a and b respectively. = b divides b'; hence b' nb, where n is some integer; therefore a = na. 690. If a prime number p divides a product abcd... it must divide one of the factors of that product. For since p is a prime number, if p does not divide a it is prime to it, and therefore it must divide bed... (Art. 687). Similarly, if Р does not divide b, it is prime to it, and therefore it must divide cd... By proceeding in this way we shall prove that Ρ must divide one of the factors of the product. 691. If a prime number divides a", where n is any positive integer, it must divide a. This follows from the preceding Article by supposing all the factors equal. 692. If a number n is divisible by p, p', p",... and each of these divisors is prime to all the others, n is also divisible by the product pp'p"... For since n is divisible by p, we have n= =pq, where q is some integer. Since p' divides pq and is prime to p, p' must divide q; hence q=p'q, where is some integer; thus n=pp'q', and is therefore divisible by pp'. By proceeding thus we may shew that n is divisible by pp'p"... to c. 693. If a and b be each of them prime to c, then ab is prime For if ab is not prime to c, suppose ab=nr and c=ns, where n, r, and s are integers; then, since a and b are prime to c, they are prime to ns, and therefore to n; but ab = nr, therefore a 2° - n b therefore b is a multiple of n (Art. 689). Hence b is both prime ton and a multiple of n, which is impossible. Therefore ab is prime to c. 694. If a and b are prime to each other, am and ba are prime to each other; m and n being any positive integers. For since a is prime to b, it follows that a×a or a2 is prime to b (Art. 693); similarly a2x a or a3 is prime to b; and so on; thus a" is prime to b. Again, since a" is prime to b, it follows that a" is prime to b× b or b2; and so on. 695. No rational integral algebraical formula can represent prime numbers only. For, if possible, suppose that the formula a + bx + cx2 + dx3 + ... represents prime numbers only; suppose when x = m that the formula takes the value p, so that Put for x, in the formula, m +np, and suppose the value then to be p'; thus p' = a + b (m + np) + c (m + np)2 + d (m + np)3 + . ... where M (p) denotes some multiple of p; thus p' is divisible by P, and is therefore not a prime. 696. The number of prime numbers is infinite. ... For if the number of prime numbers be not infinite, suppose p the greatest prime number; the product of all the prime numbers up to p, that is, 2.3.5.7.11 p is divisible by each of these prime numbers; add unity to this product, and we obtain a number which is not divisible by any of these prime numbers; this number is therefore either itself a prime number, or is divisible by some prime number greater than p; thus p is not the greatest prime number, which is contrary to the supposition. Hence the number of prime numbers is infinite. 697. If a is prime to b, and the quantities a, 2a, 3a,...... (b-1) a, are divided by b, the remainders will all be different. For, if possible, suppose that two of these quantities ma and m'a when divided by b leave the same remainder, so that nb +r and m'a = n'b+r; then therefore ma= hence m-m' is a multiple of b (Art. 689); but this is impossible, since m and m' are both less than b. 698. A number can be resolved into prime factors in only one way. = = αβγδ ...... Let N denote the number; suppose N= abcd ................, where a, b, c, d,..... are prime numbers equal or unequal. Suppose, if possible, that N also = aßyd.............., where a, ß, y, d, ......... are other prime numbers. Then abcd...... aßyd......; hence a must divide abcd......, and therefore must divide one of the factors of this product; but these factors are all prime numbers; hence a must be equal to one of them, a suppose. Divide by a or a, then bcd......=ẞyd......; from this we can prove that B must be equal to one of the factors in bed .............. ..; and so on. Thus the factors in abcd...... cannot be different from those in αβγδ...... 099. To find the highest power of a prime number a which is contained in the product [m. Let Im denote the greatest integer contained in a m a and so on; then the highest power of the prime number a which is contained in m is For among the numbers 1, 2, 3, m, there are I ...... which a contain a at least once, namely the numbers a, 2a, 3a, 4a,. are I 3 ...... which contain a2 at least once; there which contain a3 at least once; and so on. of these expressions is the required highest power. The sum This proposition will be illustrated by considering a numerical example. Suppose for instance that m= 14 and a = 2; then we have to find the highest power of 2 which is contained in 14. power is 11. That is, 2" will divide [14, and no higher power of 2 will divide |14. Now let us examine in what way this number 11 arises. Of the factors 1, 2, 3, 4, 14 there are seven which we can divide at once by 2, namely 2, 4, 6, 8, 10, 12, 14. There are three factors which can be divided by 2 a second time, namely 4, 8, 12. There is one factor which can be divided by 2 a third time, namely 8. Thus we see the way in which 7 + 3 + 1, that is 11, arises. |