Page:Encyclopædia Britannica, Ninth Edition, v. 17.djvu/675

(mod. N), or, since a, b, c, . . are each prime to A", and therefore also the product abc . . is prime to JV, we have arW>= 1, or say #W> -1=0 (mod. A*). In particular, if N be a prime number =p, then <t>(Jf) is = p - 1, and the theorem is xi j - l l=0 (mod. p), x being now any number not divisible by p. 12. The general congruence f(x) = (mod. p f(x} is written to denote a rational and integral function with integer coefficients which may without loss of generality be taken to be each of them less than p ; it is assumed that the coefficient a of the highest power of x is not = 0. If there is for x an integer value a such that /(a) = (mod. p, throughout), then a is said to be a root of the congru ence/^) = ; we may, it is clear, for a substitute any value whatever a a + kp, or say any value a which is = a, but such value a is considered not as a different root but as the same root of the congruence. We have thus /(a) = ; and therefore f(x) = f(x~) /(a), = (x af(x where f^x) is a function of like form with f(x), that is, with integer coefficients, but of the next inferior order n - 1 . Suppose there is another root b of the congruence, that is, an integer value b such that f(b] = ; we have then (b - )/ 1 (^) = 0, and b - a is not = (for then b would be the same root as a). Hence fi(b) = 0, and f(x) = (x - a) (f^x) -/!(&)}_, = (x - a) (x - b) f z (x where f 2 (x) is an integral function such as f(x), but of the order n - 2 ; and so on, that is, if there exist n different (non-congruent) roots of the congruence f(x) = 0, then f(x) = A(x- a)(x -b) . . , (x - k), and the congruence may be written A(x - a)(x - &) . . (x - k) = 0. And this cannot be satisfied by any other value I ; for if so we should have A(l - a)(l - b) ... (I - k) = 0, that is, some one of the con gruences (l-a) = 0, &c., would have to be satisfied, and I would be the same as one of the roots a, b, c, . . . k. That is, a congruence of the order n cannot have more than n roots, and if it have precisely n roots , b, c, . . k, then the form is f(x) = A (x - a)(x - b) . . . (x - k), = 0. Observe that a congruence may have equal roots, viz., if the form be f(x) = A(x- a) a (x - b)P . . . , = 0, then the roots a, b, . . are to be counted a times, /3 times, . . . respect ively ; but clearly the whole number of roots a + /3 + . . is at most = n. It is hardly necessary to remark that this theory of a congruence of the order n is precisely analogous to that of an equation of the order n, when only real roots are attended to. The theory of the imaginary roots of a congruence Avill be considered further on (see No. 41). 13. The linear congruence a,r = c(mod. b). This is equivalent to the indeterminate equation ax + by = c ; if a and b are not prime to each other, but have a greatest common measure q, this must also divide c ; supposing the division performed, the equation becomes a x + b y = c, where a and b are prime to each other, or, what is the same thing, we have the congruence a x = c (mod. b ). This can always be solved, for, if we consider the b numbers 0, 1, 2, .../-!, one and only one of these will be = c (mod. b ). Multiplying these by any number a prime to b , and taking the remainders in regard to b , we reproduce in a different order the same series of numbers 0, 1, 2, ... b -l ; that is, in the series a, 2 , . . . (b -l) a there will be one and only one term = c (mod. Z/), or, calling the term in question a, we have x = a as the solution of the congruence ax = c (mod. b ) ; a a - c is then a multiple of b , say it is = - b (3, and the corresponding value of y is y fi. We may for a write a + mb , m being any positive or negative integer, not excluding zero (but, as already remarked, this is not considered as a distinct solution of the congruence) ; the corresponding value of y is clearly = /3 - ma . The value of x can be found by a process similar to that for finding the greatest common measure of the two 617 numbers a and c ; this is what is really done in the appa rently tentative process which at once presents itself for small numbers, thus Gx = 9 (mod. 35), we have 36^ = 54, or, rejecting multiples of 35, x = 19, or, if we please x = 35m +19. ^ In particular, we can always find a number such that a = 1 (mod. b ) ; and we have then x = c as the solution of the congruence ax = c. The value of f may be written = ( m d- V), where stands for that integer value which satisfies the original congruence a = 1 (mod. I ) ; and the value of x may then be written x = (mod. I ). a Another solution of the linear congruence is given in No. 21. 14. Wilson s theorem, 1.2. 3. ..p -1 + 1=0 (mod. p). It has been seen that for any prime number p the con gruence xP~ l - 1 =0 (mod. p) of the order p - 1 has the p - 1 roots 1, 2, ...p- 1 ; we have therefore a? ~ l - 1 = (x - l)(x - 2) . . . (x -jT^l), or, comparing the terms independent of x, it appears that 1.2.3...jt>-l=-l, that is, 1 . 2 . 3 . . .p~^~l + 1=0 (mod./)), the required theorem. For instance, where p = 5, then 1.2.3.4+1 = (mod. 5), and where = 7, then 1.2.3.4.5.6 + 1 = 0(mod. 7). 15. A proof on wholly different principles may be given. Suppose, to fix the ideas, p = 7 ; consider on a circle 7 points, the summits of a regular heptagon, and join these in any manner so as to form a heptagon ; the whole number of heptagons is . 1 . 2 . 3 . 4 . 5 . 6. Now of these we have |(7-1), = 3, which are regular heptagons (convex or stellated) ; the number of remaining heptagons must be divisible by 7, for with any one such heptagon we con nect the 6 heptagons which can be obtained from it by making it rotate through successive angles of | 360. That is, l . 1 . 2 . 3 . 4 . 5 . 6 - 1(7 - 1) = (mod. 7), whence 1.2.3.4.5.6-7 + 1=0, or finally 1.2.3.4.5.6 + 1=0 (mod. 7). It is clear that the proof applies without altera tion to the case of any prime number p. If p is not a prime number, then 1.2.3...p-l=0 (mod. p) ; hence the theorem shows directly whether a number p is or is not a prime number ; but it is not of any practical utility for this purpose. 16. Prime roots of a prime number application to the binomial equation X? - 1 = 0. Take, for instance, p = 7. By what precedes we have x 6 - 1 = |> 6 - 1] [x 3 - 1] [x 2 -l][x- 1], = (x 2 - x + l)(x* + x + 1) (x + l)(x - 1 ] ) ; and we have x 5 - 1 = (x - l)(x - 1}(x - 3)(x - 4}(x - 5)(x - 6) (mod. 7) ; whence also = (a- - l)(x - 2) (a? - 3}(x - 4)(z - 5) (a: - 6). These two decompositions must agree together, and we in fact have =x-Q, x-l=x-l. In particiilar, we thus have 3, 5, as the roots of the con gruence x- - x + 1 = 0, that is, [X Q - 1] = 0, and these roots 3, 5, are not the roots of any other of the congruences [s*_l]sO, 2 -1] = 0, [>-l] = 0; that is, writing a = 3 or 5 in the series of numbers a, a 2 , a 3 , a 4 , a 5 , a 6 , we have a 6 as the first term which is = 1 (mod. 7) ; the series in fact are 3,9, 27, 81, 243, 729 =3,2,6,4,5,1, 5, 25, 125, 625, 3125, 15625 = 5, 4, 6, 2, 3, 1. And so in general the congruence x?~ l - 1 =0 (mod. p) has the p - 1 real roots 1, 2, 3, . . .p - 1 ; hence the con gruence [xP~ l - 1] = 0, which is of the order <j>(p - 1), has this number <f>(p - 1) of real roots ; and, calling any one of XVII. 78