616 NUMBERS of them, suppose , were wanting, the number N would not be divisible, by a. Hence the new decomposition if it exists must be a decomposition A r =a a b@ c7 . . . ; and here, if any two corresponding indices, say a, a , are different from each other, then one of them, suppose a, is the greater, and we have N+p a = bPcY ... = a a ~ a bP c7 . . . That is, we have the number N+p a expressed in two different ways as a product, the number a being a factor in the one case, but not a factor in the other case. Thus the two exponents cannot be unequal, that is, we must have a = a , and similarly we have /3 = /:? , y = y , ...; that is, there is only the original decomposition N=a a bPc7 . . . 3. The only numbers divisible by a number N = a a bPcV . . are the numbers a a bP c7 . . , where each exponent a is equal to or greater than the corresponding exponent a. And conversely the only numbers which divide JV are those of the form a a bP c~* . . . , where each index a is at most equal to the corresponding index a ; and in particular each or any of the indices a may be =0. Again, the least common multiple of two numbers N=a a bPci . , and X = a a bP cy . . . is a a Wy". . , where each index a" is equal to the largest of the corresponding indices a, a ; observe that any one or more of the indices a, /?, y, . . , a , /? , y , . . , may be = 0, so that the theorem extends to the case where either of the numbers N, N 1 , has prime factors which are not factors of the other number. And so the greatest common measure of two numbers N=a a bPc~* .. and JV = a a bP cy . . . is a a VcV. . , where each index a" is equal to the least of the corresponding indices a and a . 4. The divisors of J r a a bPc7 . . are the several terms of the product (1 +a . . + a a )(l + b . . + 6/ 3 )(l +c. . + c7), where unity and the number JV itself are reckoned each of them as a divisor. Hence the number of divisors is = (a + l)(/3 + l)(y + 1) . . . , and the sum of the divisors is - 1X6/3 + 1 -1 5. In N=a a bPtf . . the number of integers less than and prime to it is <^V), =W 1 - - l - -- l - - To find the numbers in question write down the series of numbers 1, 2, 3, . . . N ; strike out all the numbers divisible by a, then those divisible by 6, then those divisible by c . . , and so on ; there will remain only the numbers prime to N. For actually finding the numbers we may of course in striking out those divisible by b disregard the numbers already struck out as divisible by a, and in striking out with respect to c disregard the numbers already struck out as divisible by a or b, and so on ; but in order to count the remaining numbers it is more convenient to ignore the previous strikings out. Suppose, for a moment, there are only two prime factors a and b, then the number of terms struck out as divisible by a is = If. - , and the number of terms struck out as divisible by b is = 1 T . j ; but then each term divisible by ab will have been twice struck out: the number of these is = TV. r, and thus the number ab of the remaining terms is Nil + ) which is / 1 / 1 a 6 ah) N 1 ( 1 T ) . By treating in like manner the case of three or more prime factors a, b, c, . . we arrive at the general theorem. The formula gives <(!) = 1 ( v i A r =l, there is no factor 1 ], and it is necessary to consider </>(!) as being = 1. The explanation is that properly denotes the number of integers not greater than J T and prime to it ; so that in Jf= I we have 1 an integer not greater than N and prime to it ; but in every other
- ase the two definitions agree.
6. If N, N , are numbers prime to each other then f>(NN ) = ^(N}^-^ ), ancl so also f r an y num ber of numbers having no common divisor ; in particular ~ > and the theorem is at once verified. We have N=. where the summation extends to all the divisors N of N, unity and the number N itself being included ; thus . 7. The prime factor of the binomial function X N - is = x r ~ ^ x ~ , a rational and integral function of the degree <I>(N} ; say this is called [.r-^-l], and we have X N - 1 = H [x^ - 1], where the product extends to all the divisors N of N, unity and the number N included. For instance r.,.15 -n_( x ~l)( a; ~l) 8 7 i ~,5 ~/4 i , - 1], and we have 8. Congruence to a given modulus. A number x is congruent to 0, to the modulus TV", x = (mod. Jf), when x is divisible by JV ; two numbers y, y are congruent to the modulus TV, x = y (mod. N), when their difference x-y divides by N, or, what is the same thing, if x - y = (mod. N). Observe that, if xy = (mod. N), and x be prime to N, then y = (mod. JV). 9. Eesidues to a given modulus. For a given modulus N we can always find, and that in an infinity of ways, a set of N numbers, say N residues, such that every number whatever is, to the modulus N, congruent to one and only one of these residues. For instance, the residues may be 0, 1, 2, 3, ... N- 1 (the residue of a given number is here simply the positive remainder of the number when divided by N} ; or, N being odd, the system may be 0, 1, 2, . . ,(N-l and j r even, 0, 1, 2, ..i(,Y-2),+iiV. 10. Prime residues to a given modulus. Considering only the numbers which are prime to a given modulus N, we have here a set of <$>(N) numbers, say <(A r ) prime residues, such that every number prime to N is, to the modulus N, congruent to one and only one of these prime residues. For instance the prime residues may be the numbers less than N and prime to it. In particular, if N is a prime number p, then the residues may be the p-l numbers, 1, 2, 3, . . .p - 1. In all that follows the letter p, in the absence of any statement to the contrary, will be used to denote an odd prime other than unity. A theorem for p may hold good for the even prime 2, but it is in general easy to see whether this is so or not. 1 1 . Fermat s theorem, x?> ~ l - 1 = (mod. p}. The gener alized theorem is ^(^-1=0 (mod. N). The proof of the generalized theorem is as easy as that of the original theorem. Consider the series of the $>(N} numbers a, 6, c, ... each less than N and prime to it ; let x be any number prime to N, then each of the numbers xa, xb, xc, . . is prime to 2f, and no two of them are congruent to the modulus N, that is, we cannot have x(a - b) = (mod. N); in fact, x is prime to JV, and the difference a - b of two positive numbers each less than N will be less than N. Hence the numbers xa, xb, xc, . . . are in a different order congruent to the numbers a, b, c, . . . ; and multiplying to gether the numbers of each set we have x^^abc . = abc . .
