Similarly $ (¿^) = ¿a (1 − }), $ (cv)=cr( 1 − 1), &c. b2 But, by the preceding article, $ (aa. b3.cr...) = $ (αa). $ (b3). $ (c¥).......; Hence (N)-N(1-) (1-3) (1-1).... = where a, b, c,...are the different prime factors of N, and unity is considered to be prime to a, b, c, &c. 389. The following is an extension of Fermat's Theorem : If a and m are two numbers prime to one another, and (m) the number of integers, including unity, which are less than m and prime to m; then a (m) − 1 = 0 (mod. m). Let the (m) integers less than m and prime to m be denoted by 1, a, B, y,..., (m-1). Then the products a. 1, az, aẞ, ay,..., a (m-1) must all leave different remainders when divided by m, for if any two, ra and sa suppose, left the same remainder, (rs) a would be a multiple of m, which is impossible since a is prime to m and rs is less than m. Moreover the remainders must all be prime to m, since the two factors of any one of the products are both prime to m; and therefore as the (m) remainders are all different, and are all prime to m, they must be, in some order or other, the (m) numbers 1, a, ß, y... Hence a. aa. aẞ......a (m-1)=1.a. B. y... (m1) (mod. m); {a$ (m) — 1} 1. a. ẞ...(m − 1) = 0 (mod. m). Hence as 1.a.B...(m-1) is prime to m, we have a (m)-1=0 (mod. m). If m be a prime number, & (m) = m −1, and we have Fermat's Theorem. 390. We shall conclude this chapter by considering the following examples : Ex. 1. Shew that 32n+2 - 8n - 9 is a multiple of 64. 32n+2 − 8n − 9 = (1+8)n+1 − 8n − 9=1+ (n+1) 8+ M (82) – 8n — 9 — M (82). Ex. 2. Shew that 32 - 32n2+24n-1=0 (mod. 512). Let then Un=32 − 32n2 + 24n −1; Hence Un+1-9u=256n2 - 256n=256n (n − 1) = M (512), since n (n-1) is divisible by 2. And since Un+1-9un = 0 (mod. 512), it follows that un+1=0 (mod. 512) provided un = 0 (mod. 512). The theorem is therefore true for all values of u provided it is true for n=1, which is the case since u1=0. Ex. 3. Shew that no prime factor of n2+1 can be of the form 4m - 1. Every prime number, except 2, is of the form 2k+1. Let then 2k+1 be a prime factor of n2+1. Then n is prime to 2k+1, and therefore by Fermat's theorem n2 = M(2k+1) + 1. But, by supposition, n+1=M(2k+1); n2k = {M(2k + 1) − 1 }* = M (2k + 1) + ( − 1)*. Since n2=M(2k+1)+1 and n2=M(2k+1)+(-1) it follows that k must be even, and therefore every prime factor of n2+1 is of the form 4m +1, and therefore no prime factor can be of the form 4m - 1. Since the product of any number of factors of the form 4m+1 is of the same form, it follows that every odd divisor of n2 + 1 is of the form 4m +1. Ex. 4. Shew that every whole number is a divisor of a series of nines followed by zeros. Divide the successive powers of 10 by the number, n suppose, then there can only be n different remainders including zero, and hence any particular remainder must recur. Let then 10x and 10" leave the same remainder when divided by n: then 10% – 10 is divisible by n and is of the required form. EXAMPLES XXXIX. 1. Prove the following :— (i) 231+1 - 9n3 + 3n − 2 = M (54). (ii) 52+1 + n3 − 5n3 + 4n − 5 = M (120). (iii) 42"+1 +3′′+2=0 (mod. 13). (iv) 311+2+2.43n+1 = 0 (mod. 17). 2. Shew that, if a be a prime number, and b be prime to 2 b2 will give different re 3. Shew that, if 4n+1 be a prime number, it will be a factor of 2n}+ 1; and that, if 4n-1 be a prime, it will be a factor of 2n} – 1. 4. Shew that, if n be a prime number, and r be less than n; then will · 1 nr + (-1)"1 = M (n). 5. Shew that, if m and n are prime to one another, every odd divisor of m2 + n2 is of the form 4k+ 1. where 2, 3, 5,... are the prime numbers in order. 7. Shew that the arithmetic mean of all numbers less than n and prime to it (including unity) is Įn. ... be its 8. Shew that, if N be any number, and a, b, c, different prime factors; then the sum of all the numbers less the sum of the squares of all such numbers is and 9. If (m) denote the number of integers less than m and prime to it; and if d1, da, d,... be the different divisors of n; then will Σ & (d) = n. a 10. Shew that, if a fraction where b is a prime number prime to 10, be reduced to a decimal, the number of digits in the recurring period will be either b-1 or one of its sub-multiples; and shew that if there are b-1 figures in the recurring period, the sum of the first half of the figures added to the last half will consist wholly of nines. Shew also that, if b be not a prime, but only prime to 10, the number of figures in its recurring period will be (b) or one of its sub-multiples, where (b) is the number of integers less than b and prime to b. 1 11. If be converted to a circulating decimal with p-1 figures in its recurring period, shew that p must be prime and that the recurring period being multiplied by 2, 3,......(p-1) will reproduce its own digits in the same order. 12. Shew that, if 1 P has a circulating period of p figures, 1 Q of r figures,..., and if P, Q, R,... are prime, will have a circulating period of n figures, where n is the L.C.M. of p, q, r.......... CHAPTER XXIX. INDETERMINATE EQUATIONS. 391. WE have already seen that a single equation with more than one unknown quantity, or n equations with more than n unknown quantities, can be satisfied in an indefinite number of ways, provided there is no restriction on the values which the unknown quantities may have. If, however, the values of the unknown quantities are subject to any restriction, n equations may suffice to determine the values of more than n unknown quantities. We shall in the present chapter consider some cases of equations in which the unknown quantities are restricted to integral values. = c, ax-by= = c, 392. It is clear that every equation of the first degree with two unknown quantities x and y can be reduced to one or other of the forms ax + by where a, b, c are positive integers. By changing into x and y into will become ax + by ax + by c; hence in order to shew how to find integral solutions of any equation of the first degree in x and y, it is only necessary to consider the two types = = c, and ax by y, ax + by = C = c will become ax + by =c and ax - by = c. Now, it is evident that the equation ax + by=c cannot be satisfied by integral values of x and y, if a and b have any common factor which is not also a factor of c; and, if a, b and c have any common factor, the equation can be |