hence a must divide abcd...; but each of the factors of this product is a prime, therefore a must divide one of them, a suppose. But a and a are both prime; therefore a must be equal to a. Hence bcd... =ẞyd...; and as before, ẞ must be equal to one of the factors of bcd...; and so on. Hence the factors in aẞyd... are equal to those in abcd..., and therefore N can only be resolved into prime factors in one way. 412. To find the number of divisors of a composite number. Let N denote the number, and suppose N=a'b'c"..., where a, b, c, are different prime numbers and p, q, r, ... are positive integers. Then it is clear that each term of the product ... (1 + a + a2 + + a3) (1 + b + b2 + + b2) ( 1 + c + c2 + + c')... ... ... ... is a divisor of the given number, and that no other number is a divisor; hence the number of divisors is the number of terms in the product, that is, (p+1)(q+1) (~ + 1)...... This includes as divisors, both unity and the number itself. 413. To find the number of ways in which a composite number can be resolved into two factors. Let N denote the number, and suppose N = a'b'c"........, where a, b, c... are different prime numbers and p, q, r... are positive integers. Then each term of the product (1 + a + a2 + + a2) (1 + b + b2 + ... + b2) (1 +c + c3 + + c′)... ... ... is a divisor of N; but there are two divisors corresponding to each way in which N can be resolved into two factors; hence the required number is This supposes N not a perfect square, so that one at least of the quantities p, q, r, is an odd number. ... If N is a perfect square, one way of resolution into factors is N× √N, and to this way there corresponds only one divisor N. If we exclude this, the number of ways of resolution is and to this we must add the one way N× √N; thus we obtain for the required number 414. To find the number of ways in which a composite number can be resolved into two factors which are prime to each other. As before, let the number N = a'b'c".... Of the two factors one must contain a", for otherwise there would be some power of a in one factor and some power of a in the other factor, and thus the two factors would not be prime to each other. Similarly b' must occur in one of the factors only; and so on. Hence the required number is equal to the number of ways in which the product abc... can be resolved into two factors; that is, the number of ways is 1 2 (1 + 1) (1 + 1) (1 + 1)... or 2′′-', where n is the number of different prime factors in N. 415. To find the sum of the divisors of a number. Let the number be denoted by a'b'c"..., as before. Then each term of the product (1 + a + a2 + + a3) (1 + b + b2 + + b') (1 + c + c2 + +c")... ... ... ... is a divisor, and therefore the sum of the divisors is equal to this product; that is, Also 21600 can be resolved into two factors prime to each other in 23-1, or 4 ways. Example 2. If n is odd shew that n (n2-1) is divisible by 24. Since n is odd, n-1 and n+1 are two consecutive even numbers; hence one of them is divisible by 2 and the other by 4. Again n-1, n, n+1 are three consecutive numbers; hence one of them is divisible by 3. Thus the given expression is divisible by the product of 2, 3, and 4, that is, by 24. Example 3. Find the highest power of 3 which is contained in |100. Of the first 100 integers, as many are divisible by 3 as the number of times that 3 is contained in 100, that is, 33; and the integers are 3, 6, 9,...99. Of these, some contain the factor 3 again, namely 9, 18, 27,...99, and their number is the quotient of 100 divided by 9. Some again of these last integers contain the factor 3 a third time, namely 27, 54, 81, the number of them being the quotient of 100 by 27. One number only, 81, contains the factor 3 four times. Hence the highest power required=33 +11+3+1=48. This example is a particular case of the theorem investigated in the next article. 416. To find the highest power of a prime number a which is contained in n. Let the greatest integer contained in n n n 39 *** a' a2' a3, respectively be denoted by I (22), I (~), I(),... Then among the numbers ... 1, 2, 3, n, there are I () which contain a at least once, namely which the numbers a, 2a, 3a, 4a, Similarly there are I ... contain a2 at least once, and I (2) and so on. which contain a3 at least once; Hence the highest power of a contained in [n is 417. In the remainder of this chapter we shall find it convenient to express a multiple of n by the symbol M (n). 418. To prove that the product of r consecutive integers is divisible by r. Let P stand for the product of r consecutive integers, the least of which is n; then = r times the product of r− 1 consecutive integers. Hence if the product of r r-1, we have 1 consecutive integers is divisible by 1 ... 49 Now P1r, and therefore P, is a multiple of [r; therefore also P, P are multiples of r. We have thus proved that if the product of r-1 consecutive integers is divisible by r-1, the product of r consecutive integers is divisible by r; but the product of every two consecutive integers is divisible by 2; therefore the product of every three consecutive integers is divisible by 3; and so on generally. This proposition may also be proved thus: By means of Art. 416, we can shew that every prime factor is contained in |~ +r as often at least as it is contained in \n \r. This we leave as an exercise to the student. 419. If p is a prime number, the coefficient of every term in the expansion of (a + b), except the first and last, is divisible by p. With the exception of the first and last, every term has a coefficient of the form where r may have any integral value not exceeding p-1. Now this expression is an integer; also since p is prime no factor of r is a divisor of it, and since p is greater than r it cannot divide any factor of r; that is, (p-1) (p − 2)... (p − r + 1) must be divisible by r. Hence every coefficient except the first and the last is divisible by p. 420. If p is a prime number, to prove that (a + b + c + d + ...)3 = a2 + b2 + c3 + d3 + Write ẞ for b+c+...; then by the preceding article Again (a + ß)2 = a2 + ß3 + M(p). B2 = (b + c + d + .)” = (b+y)" suppose ; ... = b2 + y2 + M (p). By proceeding in this way we may establish the required result. 421. [Fermat's Theorem.] If p is a prime number and N is prime to p, then N-1-1 is a multiple of p. We have proved that (a+b+c+d+ ...)” = a2 + b2 + c2 + d3 + + M (p); ... let each of the quantities a, b, c, d, ... be equal to unity, and suppose they are N in number; then But N is prime to p, and therefore Noo1 – 1 is a multiple of p. COR. p = 2. Since Ρ is prime, p-1 is an even number except when Therefore p-1 p-1 2 Hence either N + 1 or N2 - 1 is a multiple of p, that is N11 2 Kp±1, where K is some positive integer. 422. It should be noticed that in the course of Art. 421 it was shewn that No – N= M (p) whether N is prime to p or not; this result is sometimes more useful than Fermat's theorem. also n - n= n (n −1)=n(n+1) (n - 1) (n* + n +1). Now (n − 1) n (n + 1) is divisible by 3; hence n2 n is divisible by 6 x 7, or 42. Example 2. If p is a prime number, shew that the difference of the pth powers of any two numbers exceeds the difference of the numbers by a multiple of p. Let x, y that is, be the numbers; then xP-x=M (p) and y-y=M (p), whence we obtain the required result. Example 3. Prove that every square number is of the form 5n or 5n+1. If N is not prime to 5, we have N2=5n where n is some positive integer. If N is prime to 5 then N-1 is a multiple of 5 by Fermat's theorem; thus either N2-1 or N2+1 is a multiple of 5; that is, Ñ2=5n±1. |