NUMBERS, Theory of. The Theory of Numbers, or higher arithmetic, otherwise arithmology, is a subject which, originating with Euclid, has in modern times, in the hands of Legendre, Gauss, Lejeune-Dirichlet, Kummer, Kronecker, and others, been developed into a most extensive and interesting branch of mathematics. We distinguish between the ordinary (or say the simplex) theory and the various complex theories.
In the ordinary theory we have, in the first instance, positive integer numbers, the unit or unity 1, and the other numbers 2, 3, 4, 5, etc. We introduce the zero 0, which is a number sui generis, and the negative numbers - 1, - 2, - 3, — 4, <tc., and we have thus the more general notion of integer numbers, 0, ±1, ±2, ±3, <tc.; + 1 and - 1 are units or unities. The sum of any two or more numbers is a number; conversely, any number is a sum of two or more parts; but even when the parts are positive a number cannot be, in a determinate manner, represented as a sum of parts. The product of two or more numbers is a number; but (disregarding the unities +1, - 1, which may be introduced as factors at pleasure) it is not conversely true that every number is a product of numbers. A number such as 2, 3, 5, 7, 11, <fcc., which is not a product of numbers, is said to be a prime number; and a number which is not prime is said to be composite. A number other than zero is thus either prime or composite; and we have the theorem that every composite number is, in a determinate way, a product of prime factors.
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) f 1 (b} ≡ 0, and b - a is not ≡ 0 (for then b would be the same root as d). Hence ∕ 1 (6) ≡ 0, and ∕(x) = (x - α) {∕ 1 (ar) -∕ 1 (δ)}, = (x - a) (x - δ) ∕ 2 (<r), where ∕ 2 (^) is an integral function such as ∕(jc), but of the order n - 2; and so on, that is, if there exist n different (n on-congruent) roots of the congruence f(x) ≡ 0, then f(x) = Λ(x - d)(x -6).. .(x- 1∙), and the congruence may be written Λ(x — d)(x -V),.(x-k)≡Q. And this cannot be satisfied by any other value I; for if so we should have A(l - α)(Z - ά) ... (I - k} ≡ 0, that is, some one of the congruences (Z - a) ≡ 0, <fcc., 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 a, b, c,.. k, then the form is ∕(z) ≡ Λ(x - d)(x - δ).. .(x - Z∙), ≡ 0.
Observe that a congruence may have equal roots, viz., if the form be ∕(z) ≡Λ(x - α) α (x - d)P.. ., ≡ 0, then the roots a, b,. . are to be counted α times, β times,... respectively; but clearly the whole number of roots a + β +.. 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 will be considered further on (see No. 41).
13. The linear congruence cMJ≡≡c(mod. 6). 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 d and b' are prime to each other, or, what is the same thing, we have the congruence dx≡c ’ (mod. δ'). This can always be solved, for, if we consider the b' numbers 0, 1, 2,. ..δ'-l, one and only one of these will be≡c' (mod. 6'). Multiplying these by any number d 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'- 1; that is, in the series d, 2α',... (δ'-l) d there will be one and only one term≡c' (mod. δ'), or, calling the term in question α, we have x = a as the solution of the congruence dx ≡ c (mod. 6'); da - c is then a multiple of 6', say it is = — b'β, and the corresponding value of y is y = β. We may for α write a + 7nb', 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 = β - ma.
The value of x can be found by a process similar to that for finding the greatest common measure of the two numbers d and c' ; this is what is really done in the apparently tentative process which at once presents itself for small numbers, thus 6x≡9 (mod. 35), we have 36τ = 54, or, rejecting multiples of 35, ar≡≡19, or, if we please α> = 35w+19.
z In particular, we can always find a number ξ such that a ζ — 1 (m θd. b ); and we have then x = cξ as the solution of the congruence a x ≡ c. The value of ζ may be written ^^d^ ( m ° d ' b wllere ^⅛ stands fθr that integer value ξ which satisfies the original congruence dξ ≡ 1 (mod. δ') and the value of x may then be written x ≡ (mod. 6 , ). Another solution of the linear congruence is given in No. 21.
14. Wilson’s theorem, 1.2.3...∕>-l + l≡0 (mod. p∖ It has been seen that for any prime number p the congruence λtP- 1 -1≡0 (mod. p) of the order p-1 has the P - 1 roots 1, 2,.. .p - 1; we have therefore χP ~ 1 - 1 ≡ (χ - l)(χ - 2).. . (x -p - 1), or, comparing the terms independent of x, it appears that 1.2.3..√) - 1 ≡ - 1, that is, 1.2.3... jΓ^i + 1 ≡ 0 (mod. jo), —the required theorem. For instance, where p = 5, then 1.2.3.4 + 1 ≡ 0 (mod. 5), and where p = 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 j.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 connect the 6 heptagons which can be obtained from it by making it rotate through successive angles of A 360°. That is, ⅜.1.2.3.4.5.6- g(7 - 1) ≡ 0 (mod. 7), whence 1.2.3.4.5.6-7 + l≡0, or finally 1.2.3.4.5.6 + l≡0 (mod. 7). It is clear that the proof applies without alteration 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 χP - 1 = 0. Take, for instance, p = l. By what precedes we have a.· 8 -1=μ 6 -1] [«3 -1] [χ2 _ i] [ x _ i] j = (z 2 - a;+l)(z s +a;+l)(z+ l)(ae -1); and we have ai® -1 ≡ (x - l)(x - 2)(ae - 3)(x - 4)(x - 5)(z - 6) (mod. 7); whence also
(z 2 - x + l)(aj 2 ÷ x + l)(x + l)(z -1) ≡ (x - l)(z - 2)(x - 3)(ae - 4)(x - 5){x - 6).
These two decompositions must agree together, and we in fact have x 2 -x + 1 ≡ (ae - 3)(x- 5), ic 2 + z+1 ≡ {x - 2)(z- 3), α! + l≡x-6, a:-1 ≡ae-1.
In particular, we thus have 3, 5, as the roots of the congruence x i - x + 1 ≡ 0, that is, [∙z∙ 6 - 1] ≡ 0, and these roots 3, 5, are not the roots of any other of the congruences [ar 3 -l]≡0, [ir 2 -l]≡0, [x-l]≡0j that is, writing α = 3 or 5 in the series of numbers α, α 2 , α 3 , α 4 , α 5 , α 6 , we have α 6 as the first term which is≡l (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 v ~ γ - 1 ≡ 0 (mod. p) has the p - 1 real roots 1, 2, 3,.. .p - 1; hence the congruence [ar? -1 - 1] ≡ 0, which is of the order <∕>(∕> - 1), has this number φ(p — 1 ) of real roots: and, calling any one of these g, then in the series of powers g, g 2 , gf...gP~∖' the first term which is ≡ 1 (mod.p) is g p ~ 1 , that is, we have 5 r > 5 ,2 j · · · ff p ~ 1 = 1, 2, 3,... p - 1 in a different order.
Any such number g is said to be a prime root of p, and the number of prime roots is φ(p - 1), the number of integers less than and prime to p - 1.
The notion of a prime root was applied by Gauss to the solution of the binomial equation λ∙p - 1 = 0, or, what is the same thing, to the question of the division of the circle (Kreistheilung), see Equation, Nos. 30 and 31 (vol. viii., p. 507); and, as remarked in the introduction to the present article, the roots or periods of roots of this equation present themselves as the units of a complex theory in the Theory of Numbers.
17. Any number x less than p is≡y w , and, if ?zz is not prime to p - 1, but has with it a greatest common measure e, suppose in = ke, p - 1 = e∕, then X ≡ g pe , xf≡ ≡ g k <∙ p - 0 ≡ 1, that is, xf≡ 1; and it is easily seen that in the series of powers x, x 2 ,.. . <z∕, we have xf as the first term which is ≡ 1 (mod. p). A number ≡ g m , where m is not prime to p - 1, is thus not a prime root; and it further appears that, g being any particular prime root, the ≠(∕> - Γ) prime roots are ≡ the numbers y w , where in is any number less than p - 1 and prime to it. Thus in the foregoing example p = 7, where the prime roots were 3 and 5, the integers less than 6 and prime to it are 1,5; and we in fact have 5 ≡ 3 5 and 3 ≡ 5 5 (mod. 7).
18. Integers belonging to a given exponent; index of a number. If, as before, p - 1 = ef, that is, if f be a submultiple of p - 1, then any integer x such that xf is the lowest power of x which is ≡ 1 (mod. p') is said to belong to the exponent f. The number of residues, or terms of the series 1, 2, 3,... p - 1, which belong to the exponent f is φ(f), the number of integers less than f and prime to it; these are the roots of the congruence [a√-l]≡0 of the order ≠(∕). It is hardly necessary to remark that the prime roots belong to the exponent ∕> - 1.
A number x ≡ g m is said to have the index in ; observe the distinction between the two terms exponent and index; and further that the index is dependent on the selected prime root g.
19. Special forms of composite modulus. If instead of a prime modulus p we have a modulus p m which is the power of an odd prime, or a modulus c 2p or 2p wι which is twice an odd prime or a power of an odd prime, then there is a theory analogous to that of prime roots, viz., the numbers less than the modulus and prime to it are congruent to successive powers of a prime root g ; thus, if^ m =3 2 , we have 2, 4, 8, 16, 32, 64 ≡ 2, 4, 8, 7, 5, 1 (mod. 9), and if 2p m =2. 3 2 , we have 5, 25, 125, 625, 3125, 15625 ≡ 5, 7, 11, 13, 17, 1 (mod. 18).
As regards the even prime 2 and its powers—for the modulus 2 or 4 the theory of prime roots does not come into existence, and for the higher powers it is not applicable; thus with modulus = 8 the numbers less than 8 and prime to it are 1, 3, 5, 7; and we have 3 2 ≡ 5 2 ≡ 7 2 ≡ 1 (mod. 8).
20. Composite modulus A r =α α 0‰7 . . . — no prime roots—irregularity. In the general case of a composite modulus it has been seen that, if x is any number less than N and prime to it, then λ∙0( n ) - 1 ≡ 0 (mod. A r ). But (except in the above-mentioned cases p m , 2p m , 2 or 4) there is not any number a such that a,ΦW is the first power of a which is ≡ 1; there is always some submultiple 7 = ^≠(A 7 ) such that a i is the first power which is ≡1. For instance, say 7V^= 24, </>(#) = 8, then the numbers less than 24 and prime to itare 1,5,7,11,13,17,19,23; and we have 1 1 ≡1, 5 2 ≡7 2 ≡ 13 2 ≡ 17 2 ≡ 19 2 ≡23 2 ≡ 1 (mod. 24), that is, 1 has the exponent 1, but all the other numbers have the exponent 2. So again where A 7 ^= 48, the 16 numbers less then 48 and prime to it have, 1 the exponent 1, and 7, 13, 17, 23, 25, 31, 35, 41, 47 each the exponent 2, and the remaining numbers 5, 11, 19, 29, 37, 43 each the exponent 4. We cannot in this case by means of any single root or of any two roots express all the numbers, but we can by means of three roots, for instance, 5, 7, 13, express all the numbers less than 48 and prime to it; the numbers are in fact ≡ 5 α 7∕ 3 13 7 , where a = 0, 1, 2, or 3, and β and γ each = 0 or 1.
[Comparing with the theorem for a prime number p, where the several numbers 1, .2,3,.. .p - 1, are expressed by means of a single prime root, ≡g a , where a = 0,1, 2,.. .p - 1, we have the analogue of a case presenting itself in the theory of quadratic forms,—the “irregularity” of a determinant (post, No. 31); the difference is that here (the law being known, A r = a composite number) the case is not regarded as an irregular one, while the irregular determinants do not present themselves according to any apparent law.]
21. Maximum indicator—application to solution of a linear congruence. In the case A r = 48 it was seen that the exponents were 1, 2, 4, the largest exponent 4 being divisible by each of the others, and this property is a general one, viz., if A r = α α 6∕ 3 c'>'.. in the series of exponents i (or, as Cauchy calls them, indicators) of the numbers less than A r and prime to it, the largest exponent I is a multiple of each of the other exponents, and this largest exponent Cauchy calls the maximum indicator; the maximum indicator I is thus a submultiple of ≠(A), and it is the smallest number such that for every number x less than N and prime to it we have x 1 - 1 ≡ 0 (mod. N). The values of I have been tabulated from N= 2 to 1000.
Reverting to the linear congruence ax ≡ c (mod. 5), where a and b are prime to each other, then, if I is the maximum indicator for the modulus b, we have α i ≡l, and hence it at once appears that the solution of the congruence is x≡ca 1 ~∖
22. Residues of powers for an odd prime modulus. For the modulus p, if g be a prime root, then every number not divisible by p is ≡ one of the series of numbers g,g 2 ,... g p ~^ ; and, if k be any positive number prime to p- 1, then raising each of these to the power k we reproduce in a different order the same series of numbers g, g^ 1 ,... g p ~ 1 , which numbers are in a different order ≡ 1, 2,.... p - 1, that is, the residue of a X·th power may be any number whatever of the series 1, 2,.. .p - 1.
But, if k is not prime to p - 1, say their greatest common measure is c, and that we have p — 1 = ef, k = me, then for any number not divisible by p the Hh power is ≡ one of the series of ∕ numbers y e , g 2e ,... .gf i .; there are thus only f, = ∣(p - 1), out of the p - 1 numbers 1,2,3,... .p - 1, which are residues of a £th power.
23. Quadratic residues for an odd prime modulus. In particular, if k = 2, then e = 2, ∕= j(p - 1), and the square of every number not divisible by p is ≡ one of the ∣(∕> - 1 ) numbers g 2 , g i ,... g p ~ 1 ; that is, there are only ∣(∕> - 1) numbers out of the series 1, 2, 3,.. .p — 1 which are residues of a square number, or say quadratic residues, and the remaining J(p - 1) numbers are said to be quadratic non-residues of the modulus p,— we may say simply, residues and non-residues. But this result can be obtained more easily without the aid of the theory of prime roots. Every number not divisible by p is, to the modulus p, ≡ one of the series of numbers ±1, ±2, ±3,.. ±∣(p - 1); hence every square number is ≡ one of the series of numbers 1 2 , 2 2 , 3 2 ,.. ⅛(∕> — 1) 2 ; and thus the p-1 numbers 1, 2, 3,... .p- 1, are one-half of them residues and the other half non-residues of p. Thus in the case p = 11 every number not divisible by 11 is, to this modulus, ≡ one of the series ±1, ±2, ±3, ±4, ±5; whence the square of any such number is ≡ one of the series 1, 4, 9, 16, 25, or say the series 1, 4, 9, 5, 3; that is, we have residues 11, 3, 4, 5, . . . 9, . I non-residues ∣ . 2, . . . 6, 7, 8, . 10 ∣ .
Calling as usual the residues a and the non-residues b, we have in this case y∣∙ (∑δ - ∑α) = γγ (33 - 22), = 1, a positive integer; this is a property true for any prime number of the form 4n + 3, but for a prime number of the form 4n + 1 we have '∑b-'∑a = θ; the demonstration belongs to a higher part of the theory.
It is easily shown that the product of two residues or of two non-residues is a residue; but the product of a residue and a non-residue is a non-residue.
24. The law of reciprocity—Legendre’s symbol. The question presents itself, given that P is a residue or a non-residue of Q, can we thence infer whether Q is a residue or a non-residue of P↑ In particular, if P, Q, are the odd primes/», q, for instance, given that 13 = -ff(17), can we thence infer that 17 = 77(13), or that 17 = √V7i(13) Ί The answer is contained in the following theorem: if ∕>, q, are odd primes each or one of them of the form 4n + 1, then p, q, are each of them a residue or each of them a non-residue of the other; but, if p, q, are each of them of the form 4n + 3, then according as p is a residue or a non-residue of q we have q a non-residue or a residue of p.
The theorem is conveniently expressed by means of Legendre’s symbol, viz., p being a positive odd prime, and Q any positive or negative number not divisible by p, ∕Q∖ then j denotes +1 or - 1 according as Q is or is not a residue of p ; if, as before, q is (as/?) a positive odd prime, then the foregoing theorem is
(fxn=<- ι > itp " x, ' υ ∙
The denominator symbol may be negative, say it is -p, we then have as a definition ( —= (—— observe that ∕-O∖ ∕ Q ∖ ×~P' ×7>∕
( —- I is not = ( -— I — and we have further the theorems ∖ P J ∖-pJ
(⅞ 1 )=<->> te - 1, . (D=<- 1 ^^ υ ∙
viz., - 1 is a residue or a non-residue of p according as p ≡ 1 or ≡ 3 (mod. 4), and 2 is a residue or a non-residue of p according as p ≡ 1 or 7, or ≡ 3 or 5 (mod. 8). If, as (p ∖ ∕p∖
—Ï ) = + 1 and ( ) = ÷ L these may be written
We have also, what is in fact a theorem given at the end of No. 23,
. .(f)=(fxf>
The further definition is sometimes convenient—
Ç p ) = 0, when p divides Q.
The law of reciprocity as contained in the theorem (f)G)=(-ι>" υ is a fundamental theorem in the whole theory; it was enunciated by Legendre, but first proved by Gauss, who gave no less than six demonstrations of it.
25. Jacobi’s generalized symbol. Jacobi defined this as follows: the symbol —~ 77 — , where p, p', p",.. are positive odd primes equal or unequal, and Q is any positive or negative odd number prime to ρp'p''.. ., denotes + 1 or - 1 according to the definition
⅛÷GX>X^)∙∙∙.
the symbols on the right - hand side being Legendre’s symbols; but the definition may be regarded as extending to the case where Q is not prime to pp'p"... , then we have Q divisible by some factor p, and by the definition of Legendre’s symbol in this case we have f = 0 · hence . , . . ∖7>∕
in the case in question of Q not being prime to pp ’ p''. . the value of Jacobi’s symbol is = 0.
We may further extend the definition of the symbol to the case where the numerator and the denominator of the symbol are both or one of them even, and present the definition in the most general form, as follows: suppose that, /», />', ∕>",... being positive or negative even or odd primes, equal or unequal, and similarly ∕, r∕, q',.. . being positive or negative even or odd primes, equal or unequal, we have P=pp'p''.. . and Q = qqq'... , then the symbol ∕ Q ∖ ( -p ) will denote +1, - 1, or 0, according to the definition
(IXfX>X∣)∙(fX0(i)-.
the symbols on the right hand being Legendre’s symbols. If P and Q are not prime to each other, then for some pair of factors p and q we have p = ± q, and the corre- (q ∖
— ) is = 0, whence in this
<≡,m-o p tcloυ I ~jZ J — V.
.. i Q∖
It is important to remark that (p 1 = + 1 is not a sufficient condition in order that Q maybe a residue of P; if P = s λ a ρp'p". ., /?,/>',/>",.. being positive odd primes, then, in order that Q may be a residue of P, it must be a residue of each of the prime factors p, p', p'',. ., that is, we must have (—= + 1, ( ~,'} = + 1, ( = + 1,... as many ∖P ∕ ∖P J ∖P J equations as there are unequal factors ∕>, p, p,. . of the modulus P. Ordinary Theory, Second Part,—Theory of Forms.
26. Binary quadratic (or quadric) forms—transformation and equivalence. We consider a form
αas 2 + 2bxy + cy 2 , = (a, b, c)(ic, ι∕) 2 , or when, as usual, only the coefficients are attended to, = (α, b, c). The coefficients (a, b, c) and the variables (x, y) are taken to be positive or negative integers, not excluding zero. The discriminant ac - 6 2 taken negatively, that is, ό 2 - ac, is said to be the determinant of the form, and we thus distinguish between forms of a positive and of a negative determinant.
Considering new variables, ax + βy, yx + δy, where a, β, y, δ, are positive or negative integers, not excluding zero, we have identically (a, b, c)(ax + βy, γx + δy) 2 =(a', b', c')(x, y) 2 , where a' = (a, b, c)(a, γ) 2 , ==aa 2 + 2baγ + cγ 2 , b' = (a, b, c)(a, γ)(β, δ),=aaβ + b(aδ + βγ) + cγδ, c , = (a, b, c)(β, δ) 2 , = aβ 2 + 2bβδ + cδ 2 ; and thence b' 2 - α'c' = (αδ - βy) 2 {b 2 - ac).
The form (a', b', c') is in this case said to be contained in the form (a, b, c) ; and a condition for this is obviously that the determinant D ’ of the contained form shall be equal to the determinant D of the containing form multiplied by a square number; in particular, the determinants must be of the same sign. If the determinants are equal, then (αδ-∕3γ) 2 =l, that is, αδ-∕3γ=±l. Assuming in this case that the transformation exists, and writing αδ — βy = e, and writing also x' = ax + βy, x= — (βx'- βy ’ ~), = a ’ x'+ β'y', then conversely suppose, y' = γχ + δy y= - (-yx'+ ay ’ '),=y'x'+ δ'y', where α', β', y, δ' are integers; and we have, moreover, α'δ' - β'y' = -^-(aδ - βy∖ = ~, = e > that is, a'δ' - β'y' = + 1 or - 1 according as αδ - βy is = +1 or - 1. The two forms (a, b, c), (a', b', c) are in this case said to be equivalent, and to be, in regard to the particular transformation, equivalent properly or improperly according as αδ — βy( = a'δ' — β 'γ') is = + 1 or = — 1. We have, therefore, as a condition for the equivalence of two forms, that their determinants shall be equal; but this is not a sufficient condition. It is to be remarked also that two forms of the same determinant may be equivalent properly and also improperly; there may exist a transformation for which aδ-βγ is = +1, and also a transformation for which aδ-βy is = - 1. But this is only the case when each of the forms is improperly equivalent to itself; for instance, a form x 2 — Dy 2 , which remains unaltered by the change x, y, into x, - y (that is, α, β, y, δ = 1, 0, 0, - 1, and therefore αδ - βy = - 1 ), is a form improperly equivalent to itself. A form improperly equivalent to itself is said to be an ambiguous form. In what follows, equivalent means always properly equivalent.
27. Forms for a given determinant—classes, etc. In the case where D, = δ 2 - ac, is a square the form (a, b, c)(x, y) 2 is a product of two rational factors; this case may be excluded from consideration, and we thus assume that the determinant D is either negative, or, being positive, that it is not a square. The forms (a, b, c) of a given positive or negative determinant are each of them equivalent to some one out of a finite number of non-equivalent forms which may be considered as representing so many distinct classes. For instance, every form of the determinant - 1 is equivalent to (1, 0, 1), that is, given any form (a, δ, c) for which b 2 - ac = -1, it is possible to find integer values α, β, y, δ, such that aδ-βy = +1, and (a, b, c)(ax + βy, yx + δy) 2 = (1, 0, l)(x, y) 2 , that is, = x 2 + y 2 . Or, to take a less simple example, every form of the determinant - 35 is equivalent to one of the following forms: (1, 0, 35), (5, 0, 7), (3, ±1, 12), (4, ±1, 18),—(2, 1, 8), (6, 1, 6); for the first six forms the numbers α, 26, c have no common factor, and these are said to be properly primitive forms, or to belong to the properly primitive order; for the last two forms the numbers a, b, c have no common factor, but, a and c being each even, the numbers a, 2b, c have a common factor 2, and these are said to be improperly primitive forms, or to belong to the improperly primitive order. The properly primitive forms are thus the six forms (1, 0, 35), (5, 0, 7), (3, ±1, 12), (4, ±1, 18); or we may say that there are represented hereby six properly primitive classes. Derived forms, or forms which belong to a derived order, present themselves in the case of a determinant D having a square factor or factors, and it is not necessary to consider them here.
It is not proposed to give here the rules for the determination of the system of non-equivalent forms; it will be enough to state that this depends on the determination in the first instance of a system of reduced forms, that is, forms for which the coefficients α, δ, c, taken positively satisfy certain numerical inequalities admitting only of a finite number of solutions. In the case of a negative determinant the reduced forms are no two of them equivalent, and we thus have the required system of non-equivalent forms; in the case of a positive determinant, the reduced forms group themselves together in periods in such wise that the forms belonging to a period are equivalent to each other, and the required system of non-equivalent forms is obtained by selecting one form out of each such period. The principal difference in the theory of the two cases of a positive and a negative determinant consists in these periods; the system of non-equivalent forms once arrived at, the two theories are nearly identical.
28. Characters of a form or class—division into genera. Attending only to the properly primitive forms—for instance, those mentioned above for the determinant — 35— the form (1, 0, 35) represents only numbers f which are residues of 5, and also residues of 7; we have, in fact, f = a; 2 + 35y 2 , ≡ x 2 (mod. 5), and also ≡ x 2 (mod. 7). Using the Legendrian symbols and ^0, we say that the form (1, 0, 35) has the characters ^0, ^0 = + +. Each of the other forms has in like manner a determinate character + or — in regard to and also in regard to ^0; and it is found that for each of them the characters are + + or else (that is, they are never H— or —h ).
We, in fact, have
(4)(i)
(1, 0, 35) + +
(4, ± 1, 9) (5, 0, 7) -
(3, ± 1, 12)
and we thus arrange the six forms into genera, viz., we have three forms belonging to the genus , ^*0 = + +, and three to the genus 0 ), ^0 = , these characters + + and of genera being one-half of all the combinations + +, , + - , —H.
The like theory applies to any other negative or positive determinant; the several characters have reference in some cases not only to the odd prime factors of D but also to the numbers 4 and 8, that is, there is occasion to consider also the Legendrian symbols ( ~jτ^} > = (- 1 » an ^
∕2∖ l(j 3 -1) ' d
Çj.J, = ( - 1) , and there are various cases to be con sidered according to the form of D in regard to its simple and squared factors respectively; but in every case there are certain combinations of characters (in number one-half of all the combinations) which correspond to genera, and the properly primitive forms belong to different genera accordingly, the number of forms being the same in each genus.
The form (1, 0, - D) has the characters all +, and this is said to be the principal form, and the genus containing it the principal genus. For a given determinant, the characters of two genera may be compounded together according to the ordinary rule of signs, giving the characters of a new genus; in particular, if the characters of a genus are compounded with themselves, then we have the characters of the principal genus.
29. Composition of quadratic forms. Considering A r , Y, as given lineo-linear functions of (x, y), (x', y'∖ defined by the equations X =Pfflχd +p 1 χy ’ +p 2 yχ' +p i yy', Y = q f fcx' + q 1 xy' + q 2 yx' + q 3 yy', the coefficients p 0 , p 1 , p 2 , p 3 , q 0 , q 1 , q 2 , q 3 , may be so connected with the coefficients (A, B, C∖ (a, b, c~), (α', δ', c'), of three quadratic forms as to give rise to the identity
(A, B, C∖X, Yγ t =(a, b, c)(x, yf. {a', b', c')(a∕, y') 2 ; and, this being so, the form (A, B, (B) is said to be compounded of the two forms (a, b, c) and (a', b', c'), the order of composition being indifferent.
The necessary and sufficient condition in order that it may be possible to compound together two given forms (a, b, c), (a', b', c'), is that their determinants shall be to each other in the proportion of two square numbers; in particular, the two forms may have the same determinant D ; and when this is so the compound form (A, J5, C ’) will also have the same determinant D. The rules for this composition of two forms of the same determinant have been (as part of the general theory) investigated and established. The forms compounded of equivalent forms are equivalent to each other; we thus in effect compound classes, viz., considering any two classes, the composition of their representative forms gives a form which is the representative of a new class, and the composition of any two forms belonging to the two classes respectively gives a form belonging to the new class. But, this once understood, it is more simple to speak of the composition of forms, that is, of the forms belonging to the finite system of representative forms for a given determinant; and it will be enough to consider the properly primitive forms.
30. The principal form (1, 0, D) compounded with any other form (a, b, c) gives rise to this same form (a, b, c); the principal form is on this account denoted by 1, viz., denoting the other form by <∕>, and expressing composition in like manner with multiplication, we have 1. φ = φ. The form φ may be compounded with itself, giving a form denoted by <∕> 2 ; compounding this again with φ, we have a form denoted by φ 3 ∙, and so on. Since the whole number of forms is finite we must in this manner arrive at the principal form, say we have φ n = 1, n being the least exponent for which this equation is satisfied. In particular, if the form φ belong to the principal genus, then the forms <∕> 2 , ≠ 3 ,... φ n ~ 1 will all belong to the principal genus, or the principal genus will include the forms 1, φ, φ 2 ,... φ n ~ 1 , the powers of a form φ having the exponent n.
31. Regular and irregular determinants. The principal genus may consist of such a series of forms, and the determinant is then said to be regular ; in particular, for a negative determinant D, = — 1 to — 1000, the determinant is ahvays regular except in the thirteen cases - D = 243, 307, 339, 459, 576, 580, 675, 755, 820, 884, 891, 900, 974 (and, Perott, in Crelle, vol. xcv., 1883, except also for — 7) = 468, 931); the determinant is here said to be irregular. Thus for each of the values-J9 = 576,580,820,900, the principal genus consists of four forms, not 1, φ, φ 2 , φ 3 , where φ i = 1, but 1, φ, φ 1 , φφ 1 , where φ 2 = 1, φ 1 2 = 1, and therefore also (<∕>φ 1 ) 2 = 1.
Compounding together any two forms, we have a form with the characters compounded of the characters of the two forms; and in particular, combining a form with itself, we have a form with the characters of the principal form. Or, what is the same thing, any two genera compounded together give rise to a determinate genus, viz., the genus having the characters compounded of the characters of the two genera; and any genus compounded with itself gives rise to the principal genus.
Considering any regular determinant, suppose that there is more than one genus, and that the number of forms in each genus is = n ; then, except in the case n = 2, it can be shown that there are always forms having the exponent 2n. For instance, in the case D = — 35 we have two genera each of three forms; there will be a form g having the exponent 6,— g 6 = 1; and the forms are 1, g, g 2 , g 3 , g i , g 5 , where 1, 9 i ∙> y 4 > belong to the principal genus, and g, g 3 , g b , to the other genus. The characters refer to , (’ Q, and the forms are [table]
An instance of the case n — 1 is D= —21, there are here four genera each of a single form 1, c, c 1 , c<q, where c 2 = 1, c 1 2 = 1; an instance of the case n = 2 is D = - 88, there are here two genera each of two forms 1, c, and c 1 , cc , where c 2 = 1, c i 2 — 1, thus there is here no form having the exponent 2n. (See Cayley, Tables, <L∙c., in Crelle, vol. lx., 1862, pp. 357-372.) We may have 2 fc ÷ 1 genera each of n forms, viz., such a system may be represented by (1, ≠ 2 ,... φ 2 - 2 ·, φ,φ 3 ,... ≠ 2 *→)(1, c )(l, c 1 )... (1, cjfc . 1 ), where <∕> 2 ' l =l, c 2 = 1, c 1 2 = 1, . . . c 2 jfc-1 = 1; there is no peculiarity in the form φ, we may instead of it take any form such as cφ, cc 1 φ, &c., for each of these is like φ, a form belonging to the exponent 2n, and such that the even powers give the principal genus.
32. Ternary and higher quadratic forms—cubic forms, <fcc. The theory of the ternary quadratic forms ( α ∙ b, c, a’, V, c')(.r, y, z) 2 ,=ax 2 + by 2 + cz 2 +2a'yz + 2b ’ zx + 2c , xy, or when only the coefficients are attended to (a, , , c , ), ∖a, b, c J has been studied in a very complete manner; and those of the quaternary and higher quadratic forms have also been studied; in particular the forms x 2 + y 2 + z 2 , x 2 4- y- + z 2 + w 2 composed of three or four squares; and the like forms with five, six, seven, and eight squares. The binary cubic forms (a, b, c, d){x, y) 3 , = ax 3 + ⅛bx 2 y + 3czy 2 + dy 3 , or when only the coefficients are attended to (a, b, c, d), have also been considered, though the higher binary forms have been scarcely considered at all. The special ternary cubic forms ax 3 4- by 3 + cz i 4- ⅛lxyz have been considered. Special forms of the degree n with n variables, the products of linear factors, present themselves in the theory of the division of the circle (the Kreistheilung) and of the complex numbers connected therewith; but it can hardly be said that these have been studied as a part of the general theory of forms.
Complex Theories.
33. The complex theory which first presented itself is that of the numbers a + bi composed with the imaginaι*y i, — √ — 1; here if a and b are ordinary, or say simplex positive or negative integers, including zero, we regard a + bi as an integer number, or say simply as a number in this complex theory. We have here a zero 0 (a = 0, b = 0) and the units 1, i, - 1, - i, or as these may be written 1, i, i 2 , i 3 {i i = 1); the numbers a + bi, a - bi, are said to be conjugate numbers, and their product (α + bi)(a — bi), = a 2 + b 2 , is the norm of each of them. And so the norm of the real number a is = a 2 , and that of the pure imaginary number bi is = b 2 . Denoting the norm by the letter A τ , A r (α ± bi) ja 2 + b 2 .
Any simplex prime number, ≡ 1 (mod. 4), is the sum of two squares a 2 + b 2 , for instance 13 = 9 + 4, and it is thus a product (α = bi)(a - bi), that is, it is not a prime number in the present theory, but each of these factors (or say any number a + bi, where a 2 + b 2 is a prime number in the simplex theory) is a prime; and any simplex prime number, ≡ 3 (mod. 4), is also a prime in the present theory. The number 2, = (1 + i)(l- i), is not a prime, but the factors 1 +i, 1— i are each of them prime; these last differ only by a unit factor i — 1 + i = i(l-i) — so that 2, = - t(l + i) 2 , contains a square factor.
In the simplex theory we have numbers, for instance 5, — 5, differing from each other only by a unit factor, but we can out of these select one, say the positive number, and attend by preference to this number of the pair. It is in this way—viz., by restricting a, b, c,.. . to denote terms of the series 2, 3, 5, 7,... of positive primes other than unity— that we are enabled to make the definite statement, a positive number JV is, and that in one way only, = a a bPcΥ ...; if IF be a positive or negative number, then the theorem of course is, -N^ is, and that in one way only, = ( - l) w α α 6∕ 3 <A.. .
where m = 0, or 1, and a, b, c,.. a, β, y ,. are as before. To obtain a like definite statement in the present theory we require to distinguish between the four numbers a 4. l)i f -a-bi,-b + ai,b- ai, which differ from each other only by a unit factor - 1, + i. Consider a number a + bi where a and b are the one of them odd and the other even (α and b may be either of them = 0, the other is then odd), every prime number a + bi other than ±1 +i is necessarily of this form, for if a and b were both even the number would be divisible by 2, or say by (1 + ι) 2 , and if a and b were both odd it would be divisible by 1 + i ; then of the four associated numbers a + bi —a-bi, - b + ai, bai, there is one and only one, a + bi, such that b is even and a + b - 1 is evenly even; or say one and only one which is ≡ 1 (mod. 2(1+ i)). We distinguish such one of the four numbers from the other three and call it a primary number; the units ±1, ±t, and the numbers ±l±t are none of them primary numbers. We have then the theorem, a number N is in one way only = ¾ 7n, (l + i} n A a BP . ., where Mt = 0, 1, 2, or 3, n is =0 or a positive integer, A, B,... are primary primes, α, β,.. . positive integers. Here i is a unit of the theory, 1 + i is a special prime having reference to the number 2, but which might, by an extension of the definition, be called a primary prime, and so reckoned as one of the numbers A, B,.. .; the theorem stated broadly still is that the number W is, and that in one way only, a product of prime factors, but the foregoing complete statement shows the precise sense in which this theorem must be understood. A like explanation is required in other complex theories; we have to select out of each set of primes differing only by unit factors some one number as a primary prime, and the general theorem then is that every number A r is, and that in one way only, =P. A a B^C y ... , where P is a product of unities, and A, B,C,.. are primary primes.
34. We have in the simplex theory (ante, No. 10) the theorem that, p being an odd prime, there exists a system of p - 1 residues, that is, that any number not divisible by p is, to the modulus p, congruent to one, and only one, of the p - 1 numbers 1, 2, 3,... p - 1. The analogous theorem in the complex theory is that for any prime number p other than + l±z there exists a system of A r (∕>)-1 residues, that is, that every number not divisible by p is, to the modulus p, congruent to one of these √V(p)-l numbers.
But p may be a real prime such as 3, or a complex prime such as 3 + 2i ; and the system of residues presents itself naturally under very different forms in the two cases respectively. Thus in the case jp = 3, W(3) = 9, the residues may be taken to be [table]
being in number W(3)-l = 8. And for ∕> = 3 + 27, W(3 + 2ι) = 13, they may be taken to be the system of residues of 13 in the simplex theory, viz., the real numbers 1, 2, 3, 12. We have in fact 5 + i = (2 + 3ι)(l - i), that is, 5 + i ≡ 0 (mod. 2 + 3i), and consequently a + bi ≡ a - 56, a real number which, when a + bi is not divisible by 3 + 2i, may have any one of the foregoing values 1, 2, 3,... 12.
Taking then any number x not divisible by p, the A r (∕>)-1 residues each multiplied by x are, to the modulus p, congruent to the series of residues in a different order; and we thus have,—say this is Fermat’s theorem for the complex theory— x n (p)- 1 - 1 ≡0 (mod. p), with all its consequences, in particular the theory of prime roots.
In the case of a complex modulus such as 3 + 2i, the theory is hardly to be distinguished from its analogue in the ordinary theorem; a prime root is = 2, and the series of powers is 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1, for the modulus 3 + 2i as for the modulus 13. But for a real prime such as 3 the prime root is a complex number; taking it to be = 2 + i, we have (2 + ⅛) 8 - 1 ≡ 0 (mod. 3), and the series of powers in fact is 2 + i, i, 2 + 2i, 2, 1 + 2i, 2i, 1 + i, 1, viz., we thus have the system of residues (mod. 3).
We have in like manner a theory of quadratic residues; a Legendrian symbol ^ J (which, if p, q, are uneven primes not necessarily primary but subject to the condition that their imaginary parts are even, denotes +1 or - 1 according as ydi- v '2- 1 ) is ≡ 1 or ≡ — 1 (mod. ⅛), so that ^^J = +1 or — 1 according as p is or is not a residue of q), a law of reciprocity expressed by the very simple form of equation ] = J, and generally a system of properties such as that which exists in the simplex theory.
The theory of quadratic forms (a, b, c) has been studied in this complex theory; the results correspond to those of the simplex theory.
35. The complex theory with the imaginary cube root of unity has also been studied; the imaginary element is here γ j = 1( - 1 + √ - 3), a root of the equation γ 2 + γ + 1 = 0; the form of the complex number is thus a + by, where a and b are any positive or negative integers, including zero. The conjugate number is a + by 2 , = a-b-by, and the product (a + by)(a + 6γ 2 ), = d 2 — ab + b 2 , is the norm of each of the factors a + by, a + by 2 . The whole theory corresponds very closely to, but is somewhat more simple than, that of the complex numbers a + bi.
36. The last-mentioned theory is a particular case of the complex theory for the imaginary λth roots of unity, λ being an odd prime. Here a is determined by the equation —~γ = 0, that is, α λ - 1 + α λ - 2 + ... + α +1 = 0, and the form of the complex number is∕(a), = a + ba + ca 2 ... + ka κ ~ 2 > where a, b, c,... k, are any positive or negative integers, including zero. We have λ - 1 conjugate forms, viz., /(a),/(a 2 ),. . ..∕(a λ ~ 1 ), and the product of these is the norm of each of the factors Nf(a∖ = Ay(α 2 ),... = √V∕(a λ -1 ). Taking g any prime root of λ, y λ * 1 -l≡0 (mod. λ), the roots a, α 2 ,... a λ -1 , may be arranged in the order α, (β, a3 2 ,.. . a9 ,λ " 2 ; and we have thence a grouping of the roots in periods, viz., if λ - 1 be in any manner whatever expressed as a product of two factors, λ- 1 = ef, we may with the λ - 1 roots form e periods ι∕ 0 , η 1 ,... η e -ι, each of ∕ roots. For instance λ = 13; a prime root is g = 2, and λ-l=e∕=3.4j then the three periods each of four roots are [table]
So also if ef= 2.6 then the 2 periods each of 6 roots are η 0 = a + α 4 + α 3 + a 1 ’ 2 + a 9 + a 10 , η l = a 2 + a 8 + a 6 + a 11 + a 5 + a 7 ; and so in other cases. In particular, if f= 1 and consequently e = λ- 1, the e periods each of f roots are in fact the single roots α, aS ’,... a^ λ ^ 2 . We may in place of the original form of the complex number
∕(α) = α + δα + cα 2 . . . +⅛a^^ 2 , consider the new form f(τβ = aη + bη i ... + lη e ~ 1 , which when f = 1 is equivalent to the original form, but in any other case denotes a special form of complex number; instead of λ - 1 we have only e conjugate numbers, and the product of these e numbers may be regarded as the norm of f(rβ.
37. The theory for the roots α includes as part of itself the theory for the periods corresponding to every decomposition whatever λ-l=ς∕"of λ — 1 into two factors, but each of these may be treated apart from the others as a theory complete in itself. In particular, a simple case is that of the half-periods e = 2, ∕=∣(λ- 1); and, inasmuch as the characteristic phenomenon of ideal numbers presents itself in this theory of the half-periods (first for the value λ = 23), it will be sufficient, by way of illustration of the general theory, to consider only this more special and far easier theory; we may even assume λ = 23.
For the case in question, λ - 1 = ef= 2. ∣(λ - 1), we have the two periods 77 0 , y v each of j(λ- 1) roots; from the expressions for y 0 , y v in terms of the roots we obtain at once 77 0 -+77 1 = -1, and with a little more difficulty y 0 y 1 = - ∣(λ - 1) or ∣(λ+l) according as λ is ≡ 1 or 3 (mod. 4), that is, in the two cases respectively y 0 , y v are the roots of the equation ^ 2 + ^-∣(λl) = 0, and η 2 + 77 + ∣(λ +1) = 0. And this equation once obtained there is no longer any occasion to consider the original equation of the order λ - 1, but the theory is that of the complex numbers aη 0 + by 1 , or if we please a + by, composed with the roots of this quadric equation,—say the complex numbers a + by, where a and b are any positive or negative integer numbers, including zero. In the case λ = 23 the quadric equation is y 2 + y + 6 = 0. We have Λ’(α + by) = (a + δ¾)(α + by 1 ) — a 2 - ab + {(λ + 1)6 2 ; and for λ = 23 this is N(a + by)==d 2 - ab + ⅛b 2 . It may be remarked that there is a connexion with the theory of the quadratic forms of the determinant - 23, viz., there are here the three improperly primitive forms (2, 1, 12), (4, 1, 6), (4, - 1, 6), 23 being the smallest prime number for which there exists more than one improperly primitive form.
38. Considering then the case λ = 23, we have 77 0 , 77 1 , the roots of the equation y 2 + y + 6 = 0; and a real number P is composite when it is = (α + by 0 )(a + by 1 ), =a 2 -ab + 6δ 2 , viz., if 4P=(2α-δ) 2 + 23δ 2 . Hence no number, and in particular no positive real prime P, can be composite unless it is a (quadratic) residue of 23; the residues of 23 are 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18; and we have thus, for instance, 5, 7, 11, as numbers which are not composite, while 2, 3, 13, are numbers which are not by the condition precluded from being composite: they are not, according to the foregoing signification of the word, composite (for 8, 12, 52, are none of them of the form x 2 + 23y 2 ), but some such numbers, residues that is of 23, are composite, for instance 59, = (5 - 2r∕ 0 )(5 - 2τ∕ 1 ). And we have an indication, so to speak, of the composite nature of all such numbers; take for instance 13, we have (77 - 4)(77 + 5) = -2.13, where 13 does not divide either y - 4 or y + 5, and we are led to conceive it as the product of two ideal factors, one of them dividing y - 4, the other dividing y + 5. It appears, moreover, that a power 13 3 is in fact composite, viz., we have 13 3 =(31 - 12τ∕ 0 )(31 - 12η 1 )> (2197 = 961 + 372 + 864); and writing 13= ∖∕31 — 12τy 0 . V31 - 12τ∕ 1 we have 13 as the product of two ideal numbers each represented as a cube root; it is to be observed that, 13 being in the simplex theory a prime number, these are regarded as prime ideal numbers. We have in like manner
2= ξ∕Γ^V 1 , 3= ^∕l-^2⅜∙ χ∕T τ ^⅛ &c.; every positive real prime which is a residue of 23 is thus a product of two factors ideal or actual. And, reverting to the equation (77 — 4)(77 + 5) = —2.13, or as this may be written
⅛ι-‰ + 5)= - √l-77 0 4 z31 - 12⅞ √31-12τ h , we have (77 1 - 4) 3 and (1 - τ 7o )(31 - 12τ 7o ) each = 14 + 55τ 21 , or say
¾-<= V iτ ⅞ £/31 - 12 % , and similarly
τjι + 5=- Vl-77 1 V31-12¾, so that we verify that y i - 4, y l + 5, do thus in fact each of them contain an ideal factor of 13.
39. We have 2 = Vl -17 0 Vl - τ∕ 1 , viz., the ideal multiplier V l-77 0 renders actual one of the ideal factors Vl — 7 ∕ι of 2, and it is found that this same ideal multiplier £/l - y 0 renders actual one of the two ideal factors of any other decomposable number 3, 13, <tc.,
Vl - 2⅞ Vl~% = l+‰ v z 31-12τy 0 χ∕l - η,,= - 5 - η 0 , k,c. Similarly the conjugate multiplier Vl - y 1 renders actual the other ideal factor of any number 2, 3, 13, &c. We have thus two classes, or, reckoning also actual numbers, three classes of prime numbers, viz., (1) ideal primes rendered actual by the multiplier Vl-τ7 0 , (2) ideal primes rendered actual by the multiplier £/1 - Vυ (3) actual primes. This is a general property in the several complex theories; there is always a finite number of classes of ideal numbers, distinguished according to the multipliers by which they are rendered actual; the actual numbers form a “principal” class.
40. General theory of congruences—irreducible functions. In the complex theory relating to the roots of the equation 77 2 + 77 + 6 = 0 there has just been occasion to consider the equation (77 - 4)(77 + 5) = -2.13, or say the congruence (77 - 4)(77 + 5) ≡ 0 (mod. 13); in this form the relation 77 2 + 77 -+ 6 = 0 is presupposed, but if, dropping this equation, y be regarded as arbitrary, then there is the congruence 77 2 +17 + 6 ≡ (77 - 4)(77 + 5) (mod. 13). For a different modulus, for instance 11, there is not any such congruence exhibiting a decomposition of y 2 + 77 + 6 into factors. The function y 2 + y + 6 is irreducible, that is, it is not a product of factors with integer coefficients; in respect of the modulus 13 it becomes reducible, that is, it breaks up into factors having integer coefficients, while for the modulus 11 it continues irreducible. And there is a like general theory in regard to any rational and integral function F(x) with integer coefficients; sυ,^h function, assumed to be irreducible, may for a given prime modulus p continue irreducible, that is, it may not admit of any decomposition into factors with integer coefficients; or it may become reducible, that is, admit of a decomposition F(x) ≡ φ(x)ψ(fc)χ(x) . . (mod. p). And, when this is so, it is thus a product, in one way only, of factors <∕>(a∙), ≠(x), χ(x),. ., which are each of them irreducible in regard to the same modulus 79; any such factor may be a linear function of x, and as such irreducible; or it may be an irreducible function of the second or any higher degree. It is hardly necessary to remark that in this theory functions which are congruent to the modulus p are regarded as identical, and that in the expression of F(x) an irreducible function φ(x) may present itself either as a simple factor, or as a multiple factor, with any exponent. The decomposition is analogous to that of a number into its prime factors; and the whole theory of the rational and integral function F(x) in regard to the modulus p is in many respects analogous to that of a prime number regarded as a modulus. The theory has also been studied where the modulus is a power p v .
41. The congruence - imaginaries of Galois. If F(x) be an irreducible function to a given prime modulus p, this implies that there is no integer value of x satisfying the congruence F(x) ≡ 0 (mod. y>); we assume such a value and call it i, that is, we assume F(i~) ≡ 0 (mod. p); the step is exactly analogous to that by which, starting from the notion of a real root, we introduce into algebra the ordinary imaginary i = λ∕ - 1. For instance, x 2 — x + 3 is an irreducible function to the modulus 7, there is no integer solution of the congruence aj 2 -^ + 3≡0 (mod. 7). Assuming a solution i such that ⅛ 2 -i + 3≡0 (mod. 7), we have, always to this modulus, i 2 = i - 3, and thence r' i , i 4 , <fcc., each of them equal to a linear function of i. We consider the numbers of the form a + bi, where a and b are ordinary integers which may be regarded as having each of them the values 0, 1, 2, 3, 4, 5, or 6; there are thus 7 2 , = 49, such numbers, or, excluding zero, 48 numbers; and it is easy to verify that these are in fact the numbers i, i 2 , .... ⅛ 47 , t 48 , = 1, that is, we have i a prime root of the congruence x 48 —1=0 (mod. 7 ). The irreducible function may be of the third or any higher degree; thus for the same modulus 7 there is the cubic function x 3 - x + 2, giving rise to a theory of the numbers of the form a + bi + ci 2 , where i is a congruence-imaginary such that i 3 -⅛+2≡0 (mod. 7); and instead of 7 the modulus may be any other odd prime p. Ordinary Theory, Third Part.
42. In what precedes no mention has been made of the so-called Pellian equation x 2 - Dy 2 = 1 (where D is a given positive number), and of the allied equations x 2 — Dy 2 = - 1, or = ± 4. The equations with the sign + have always a series of solutions, those with the sign - only for certain values of D; in every case where the solutions exist a least solution is obtainable by a process depending on the expression of ∖'D as a continued fraction, and from this least solution the whole series of solutions can be obtained without difficulty. The equations are very interesting, as well for their own sakes as in connexion with the theory of the binary quadratic forms of a positive non-square determinant.
43. The theory of the expression of a number as a sum of squares or polygonal numbers has been developed apart from the general theory of the binary, ternary, and other quadratic forms to which it might be considered as belonging. The theorem for two squares, that every prime number of the form 4n + 1 is, and that in one way only, a sum of two squares, is a fundamental theorem in relation to the complex numbers a + bi. A sum of two squares multiplied by a sum of two squares is always a sum of two squares, and hence it appears that every number of the form 2 α (4n+ 1) is (in general in a variety of ways) a sum of two squares.
Every number of the form 4» + 2 or 8τι + 3 is a sum of three squares; even in the case of a prime number 8n + 3 there is in general more than one decomposition, thus 59 = 25 + 25 + 9 and = 49 + 9 + 1. Since a sum of three squares into a sum of three squares is not a sum of three squares, it is not enough to prove the theorem in regard to the primes of the form 8n + 3.
Every prime number is (in general in more than one way) a sum of four squares; and therefore every number is (in general in more than one way) a sum of four squares, for a sum of four squares into a sum of four squares is always a sum of four squares.
Every number is (in general in several ways) a sum of m + 2 (m + 2)gonal numbers, that is, of numbers of the form ⅛m(x 2 - x~)+x ; and of these m-2 may be at pleasure equal to 0 or 1; in particular, every number is a sum of three triangular numbers (a theorem of Fermat’s).
The theorems in regard to three triangular numbers and to four square numbers are exhibited by certain remarkable identities in the Theory of Elliptic Functions; and generally there is in this subject a great mass of formulae connected with the theory of the representation of numbers by quadratic forms. The various theorems in regard to the number of representations of a number as the sum of a definite number of squares cannot be here referred to.
44. The equation x λ + y λ = z λ , where λ is any positive integer greater than 2, is not resoluble in whole numbers (a theorem of Fermat’s). The general proof depends on the theory of the complex numbers composed of the λth roots of unity, and presents very great difficulty; in particular, distinctions arise according as the number λ does or does not divide certain of Bernoulli’s numbers.
45. Lejeune-Dirichlet employs for the determination of the number of quadratic forms of a given positive or negative determinant a remarkable method depending on the summation of a series Σ∕ -s , where the index s is greater than but indefinitely near to unity.
46. Very remarkable formulae have been given by Legendre, Tchebycheff, and Riemann for the approximate determination of the number of prime numbers less than a given large number x. Factor tables have been formed for the first nine million numbers, and the number of primes counted for successive intervals of 50,000; and these are found to agree very closely with the numbers calculated from the approximate formulae. Legendre’s expression
*Z7
is of the form .- 7 , where A is a constant not very log x - A different from unity; Tchebycheff’s depends on the logarithm-integral li(jc); and Riemann’s, which is the most accurate, but is of a much more complicated form, contains a series of terms depending on the same integral.
The classical works on the Theory of Numbers are Legendre, Théorie des Nombres, 1st ed. 1798, 3d ed. 1830; Gauss, Disquisitiones Arithmeticae, Brunswick, 1801 (reprinted in the collected works, vol. i., Göttingen, 1863; French trans., under the title Recherches Arithmétiques, by Poullet-Delisle, Paris, 1807); and Lejeune-Dirichlet, Vorlesungen über Zahlenthcorie, 3d ed., with extensive and valuable additions by Dedekind, Brunswick, 1879-81. We have by the late Prof. H. J. S. Smith the extremely valuable series of “Reports on the Theory of Numbers,” Parts I. to VI., British Association Reports, 1859-62, 1864-65, which, with his own original researches, will be printed in the collected works now in course of publication by the Clarendon Press. See also Cayley, “Report of the Mathematical Tables Committee,” Brit. Assoc. Report, 1875, pp. 305-306, for list of tables relating to the Theory of Numbers, and Mr. J. W. L. Glaisher’s introduction to the Factor Table for the Sixth Million, London, 1883, in regard to the approximate formulae for the number of prime numbers.
