We have complex theories in which all the foregoing notions (integer, unity, zero, prime, composite) occur; that which first presented itself was the theory with the unit i (i 2 = - 1); we have here complex numbers, a + bi, where a and b are in the before-mentioned (ordinary) sense positive or negative integers, not excluding zero; we have the zero 0, = 0 + 0i, and the four units 1, - 1, i, — i. A number other than zero is here either prime or else composite; for instance, 3, 7, 11, are prime numbers, and 5, = (2 + i)(2 - i), 9, = 3.3, 13, = (3 + 2t)(3 - 2i), are composite numbers (generally any positive real prime of the form 4/2, + 3 is prime, but any positive real prime of the form 4n + 1 is a sum of two squares, and is thus composite). And disregarding unit factors we have, as in the ordinary theory, the theorem that every composite number is, in a determinate way, a product of prime factors.

There is, in like manner, a complex theory involving the cube roots of unity—if α be an imaginary cube root of unity (α 2 + α + 1 = 0), then the integers of this theory are a + ba (α and b real positive or negative integers, including zero)—a complex theory with the fifth roots of unity—if α be an imaginary fifth root of unity (α 4 4- a 3 + a 2 + a + 1 =0), then the integers of the theory are a + ba + ca 2 + da 3 (a, b, c, d, real positive or negative integers, including zero); and so on for the roots of the orders 7, 11, 13, 17, 19. In all these theories, or at any rate for the orders 3, 5, 7 (see No. 37, post), we have the foregoing theorem: disregarding unit factors, a number other than zero is either prime or composite, and every composite number is, in a determinate way, a product of prime factors. But coming to the 23d roots of unity the theorem ceases to be true. Observe that it is a particular case of the theorem that, if A r be a prime number, any integer power of A r has for factors only the lower powers of A^,— for instance, N' i — N.N' 2 ∙, there is no other decomposition N" i = AB. This is obviously true in the ordinary theory, and it is true in the complex theories preceding those for the 3d, 5th, and 7th roots of unity, and probably in those for the other roots preceding the 23d roots; but it is not true in the theory for the 23d roots of unity. We have, for instance, 47, a number not decomposable into factors, but 47 3 , = AB, is a product of two numbers each of the form a + ba +.. + X,∙α 21 (a a 23d root). The theorem recovers its validity by the introduction into the theory of Kummer’s notion of an ideal number.

The complex theories above referred to would be more accurately described as theories for the complex numbers involving the periods of the roots of unity: the units are the roots either of the equation x p ~ 1 + x p ~ 2 ... + x +~∖, p-ι

(p a prime number) or of any equation x e +.. ± 1 = 0 belonging to a factor of the function of the order p — 1 (in particular, this may be the quadric equation for the periods each of ⅛(p — 1) roots); they are the theories which were first and have been most completely considered, and which led to the notion of an ideal number. But a yet higher generalization which has been made is to consider the complex theory, the units whereof are the roots of any given irreducible equation which has integer numbers for its coefficients.

There is another complex theory the relation of which to the foregoing is not very obvious, viz., Galois’s theory of the numbers composed with the imaginary roots of an irreducible congruence, F(x) ≡ 0 (modulus a prime number p) ; the nature of this will be indicated in the sequel.

In any theory, ordinary or complex, we have a first part, which has been termed (but the name seems hardly wide enough) the theory of congruences; a second part, the theory of homogeneous forms (this includes in particular the theory of the binary quadratic forms (a, b, c)(x, y) 2 ); and a third part, comprising those miscellaneous investigations which do not come properly under either of the foregoing heads.

Ordinary Theory, First Part.

1. We are concerned with the integer numbers 0, ±1, ±2, ±3, <fcc., or in the first place with the positive integer numbers 1, 2, 3, 4, 5, 6, <tc. Some of these, 1, 2, 3, 5, 7, <tc., are prime, others, 4, = 2 2 , 6, = 2.3, <fcc., are composite; and we have the fundamental theorem that a composite number is expressible, and that in one way only, as a product of prime factors, N=a a bβcΙ... (a, b, c,. . primes other than 1; a, β, γ,.. positive integers).

Gauss makes the proof to depend on the following steps: (1) the product of two numbers each smaller than a given prime number is not divisible by this number; (2) if neither of two numbers is divisible by a given prime number the product is not so divisible; (3) the like as regards three or more numbers; (4) a composite number cannot be resolved into factors in more than one way.

2. Proofs will in general be onlyindicated or be altogether omitted, but, as a specimen of the reasoning in regard to whole numbers, the proofs of these fundamental propositions are given at length. (1) Let p be the prime number, a a number less than p, and if possible let there be a number b less than p, and such that ab is divisible by ∕>; it is further assumed that b is the only number, or, if there is more than one, then that b is the least number having the property in question; b is greater than 1, for a being less than p is not divisible by p. Now p as a prime number is not divisible by b, but must lie between two consecutive multiples mb and (m + l)δ of b. Hence, ab being divisible by p, mab is also divisible by p ; moreover, ap is divisible by p, and hence the difference of these numbers, = a(ρ - mb), must also be divisible by p, or, writing p — mb = b', we have ab' divisible by p, where b ’ is less than b ; so that b is not the least number for which ab is divisible byp. (2) If a and b are neither of them divisible by p, then a divided byp leaves a remainder a which is less than p, say we have a = mp + a; and similarly b divided by p leaves a remainder β which is less than p, say we have b = np + β ; then ab = (mp + α)(np + β), = (mnp + no. + mβ) p + aβ, and aβ is not divisible by p, therefore ab is not divisible by p. (3) The like proof applies to the product of three or more factors a, b, c,... (4) Suppose that the number W, = a a b^ct . . . (a, b, c, . . . prime numbers other than 1), is decomposable in some othçr way into prime factors; we can have no prime factor p, other than a, b, c, . . . , for no such number can divide a a bβcΥ ...; and we must have each of the numbers a, b,c,..., for if any one of them, suppose α, were wanting, the number √V would not be divisible, by a. Hence the new decomposition if it exists must be a decomposition A 7 =α tt c? ...; and here, if any two corresponding indices, say α, α', are different from each other, then one of them, suppose α', is the greater, and we have N÷p a = ... = a a ~ a bß c'y ...

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', and similarly we have β = β', γ = γ',...; that is, there is only the original decomposition N=a a -bβcY ...

3. The only numbers divisible by a number A τ = a a bβcΥ.. are the numbers a a bß c'y . ., where each exponent α' is equal to or greater than the corresponding exponent α. And conversely the only numbers which divide N are those of the form α α bß c'y' .. ., where each index a is at most equal to the corresponding index α; and in particular each or any of the indices α' may be = 0. Again, the least common multiple of two numbers N=a a b^cY . . and AT =a a 'bβ'c'Y , . . . is a a ∙Wc"γ" ·.. , where each index α" is equal to the largest of the corresponding indices α, a ·— observe that any one or more of the indices a, β, γ,.., α', β', γ',.., may be = 0, so that the theorem extends to the case where either of the numbers A 7 , JV, has prime factors which are not factors of the other number. And so the greatest common measure of two numbers A r = a a bßcY .. and N ’ = a a 'bβ'cΥ'.. . is a a 'bβ"c'γ ".., where each index α" is equal to the least of the corresponding indices α and α'.

4. The divisors of A τ = a a bβcΥ. . are the several terms of the product (1 + α.. + α α )(l +b. . + 6∕ 3 )(1 +c. . + c^), where unity and the number A r itself are reckoned each of them as a divisor. Hence the number of divisors is = (α + l)(β + l)(γ + 1) ..., and the sum of the divisors is

(α α + 1 - l)(δ∕ 3 + 1 - l)(c> , + 1 - 1)..

(a-l)(δ-l)(c -l)..

5. In AT = a a bβcΥ. . the number of integers less than A r and prime to it is ≠(A τ ), = A 7 ^l - ^1 — ..

To find the numbers in question write down the series of numbers 1, 2, 3, ... A r ; strike out all the numbers divisible by a, then those divisible by b, then those divisible by c.., and so on; there will remain only the numbers prime to A r . 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 = A r . -, and the j a ’

number of terms struck out as divisible by b is = Λ τ . τ: but j b then each term divisible by ab will have been twice struck out: the number of these is = A r .- τ , and thus the number ab , of the remaining terms is A 7 fl - l-l + -lλ which is ∕ 1∖ ∕ 1∖ ∖ a b ab J = fl V - α∕ ∖ - 0/ , 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) = 1 (viz., A r =l, there is no factor 1 --Y and it is necessary to consider ≠(1) as being = 1. The explanation is that <∕>(A r ) properly denotes the number of integers not greater than A 7 and prime to it; so that in A r = 1 we have 1 an integer not greater than A 7 and prime to it; but in every other case the two definitions agree.

6. If A 7 , A r ', are numbers prime to each other then ≠(A 7 A r ') = φ(A 7 )<∕>(A 7 '), and so also for any number of numbers having no common divisor; in particular φ(a a bβc^Y. .) = φ(a a )φ(bβ)φ(c"Y) .. .; ≠(α α ) = a a (1 ~ ^), and the theorem is at once verified. We have A r = Σ<∕>(√V'), where the summation extends to all the divisors AT of A τ , unity and the number A 7 itself being included; thus 15 = ≠(15) + ≠(5) + ≠(3) + ≠(l), = 8 + 4 + 2 + l.

. 7. The prime factor of the binomial function x n -1 is (x N -lYx N l ab -V)

= } λ , -—a rational and integral function

(z 7 Wα-l)(√w-l). .

of the degree ≠(A r ); say this is called [x∙ v -l], and we have x n - 1 = ∏ pr∙ iv ' - 1], where the product extends to all the divisors A^' of A 7 , unity and the number A 7 included. For instance t≈ ra - 1 >(⅞⅛⅛≡Ty^^ ai+a,, ^ x * +i, ^ i ' +li and we have

(x 15 -1) = [α= 1 ≡ -1] [x 5 -1] [x 3 - l][x -1], = (aP-x 7 . . -X +1)(⅛ 4 + x i + x i + x + l)(a,∙ 2 + ae + l)(x - 1).

8. Congruence to a given modulus. A number x is congruent to 0, to the modulus N, x ≡ 0 (mod. A 7 ), when x is divisible by N ; two numbers a?, y are congruent to the modulus Ai 7 x≡y (mod. A 7 ), when their difference x - y divides by A 7 or, what is the same thing, if x - y ≡ 0 (mod. A r ). Observe that, if xy≡⅛ (mod. A 7 ), and x be prime to A 7 , then y ≡ 0 (mod. A r ).

9. Residues 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 A 7 congruent to one and only one of these residues. For instance, the residues may be 0, 1, 2, 3,... A r - 1 (the residue of a given number is here simply the positive remainder of the number when divided by K}; or, N being odd, the system may be

0, ± 1, ±2,.. ±⅛(W-1), and A r even,

0, ±1, ±2, .. ±⅛(A-2),+⅜Λ r .

10. Prime residues to a given modulus. Considering only the numbers which are prime to a given modulus A 7 , we have here a set of ≠(A 7 ) numbers, say φ(∆ r ) prime residues, such that every number prime to A r is, to the modulus A”, congruent to one and only one of these prime residues. For instance the prime residues may be the numbers less than A 7 and prime to it. In particular, if A 7 is a prime number p, then the residues may be the p - 1 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 seé whether this is so or not.

11. Fermat’s theorem, χv~ 1 -l ≡ 0 (mod. p). The generalized theorem is ^≠C v )-l≡0 (mod. A 7 ). The proof of the generalized theorem is as easy as that of the original theorem. Consider the series of the ≠(A 7 ) numbers a, b, c,.. . each less than A r and prime to it; let x be any number prime to A 7 then each of the numbers xa, xb, xc,.. is prime to A 7 and no two of them are congruent to the modulus A 7 that is, we cannot have x(a - 6) ≡ 0 (mod. A τ ); in fact, x is prime to A r , and the difference a - b of two positive numbers each less than A 7 will be less than A 7 Hence the numbers xa, xb, xc,.. . are in a different order congruent to the numbers a, b, c,.. .; and multiplying together the numbers of each set we have χΦV r >abc. ≡ abc..

(mod, A 7 ), or, since a, b, c,.. are each prime to AT, and therefore also the product abc.. is prime to A", we have a j0GV)= l j or say x≠6 v ) — 1 ≡ 0 (mod. A τ ).

In particular, if N be a prime number =p, then ≠(A r ) is =p-l, and the theorem is χP^ 1 -l≡0 (mod. p), x being now any number not divisible by p.

12. The general congruence ∕(z)≡0 (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 α such that ∕(α) ≡ 0 (mod. ρ, throughout), then a is said to be a root of the congruence ∕(z) ≡ 0; we may, it is clear, for a substitute any value whatever d = a + kp, or say any value d which is ≡ α, but such value d is considered not as a different root but as the same root of the congruence. We have thus ∕(α) ≡ 0; and therefore ∕(z) ≡ f(x~) -f(d), = (x — d)f 1 (x), where ∕ 1 (∙r) is a function of like form with f(x), that is, with integer coefficients, but of the next inferior order n-l. Suppose there is another root b of the congruence, that is, an integer value b such that ∕(6) ≡ 0; we have then (b - a)...