852
NUMBER
linear congruences in any number of variables, first developed with precision by Smith. In any particular case, it is best to replace as many as possible of the given congruences by an equivalent set obtained by successively eliminating the variables x, y, z, . in order. An important problem is to find a number which has given residues with respect to a given set of moduli. When possible, the solution is of the form x≡a (mod m), where in is the least common multiple of the moduli. Supposing that p is a prime, and that we have a corresponding table of indices, the solution of ax§ ;1li mod p) can be found by observing that ind x≡ind b−ind a (mod p−1).
31. Quadratic Residues. Law of Reciprocity.-To an odd prime modulus p, the numbers 1, 4, 9, . . . (p−1)2 are congruent to Hp-1) residues only, because (p-x)2=x'2. Thus for p=5, we have 1, 4, 9, 1621, 4, 4, 1 respectively. There are therefore é(p-1) quadratic residues and %(p-1) quadratic non-residues prime to p; and there is a corresponding division of in congruent classes of integers with respect to p. The product of two residues or of two non residues is a residue; that of a residue and a non-residue is a non residue; and taking any primitive root as base the index of any number is even or odd according as the number is a residue or a non residue. Gauss writes aRp, aNp to denote that a, is a residue or non residue of p respectively.
Given a table of indices, the solution of x2Ea(mod p) when possible, is found from zind xEind a (mod pe1), and the result may be written in the form xi =|=r (mod p). But it is important to discuss the congruence xiao without assuming that we have a table of indices. It is sufficient to consider the case x'sq (mod p), where q is a positive prime less than p; and the question arises whether the quadratic character of q with respect to p can be deduced from that of p with respect to q. The answer is contained in the following theorem, which is called the law of quadratic reciprocity (for real positive odd primes): if p, q are each or one of them of the form 4n+1, then p, q are each of them a residue, or each a non-residue of the other; but if p, q are each of the form 4n+3, then according as p is a residue or non-residue of q we have g a non-residue or a residue of p.
Legendre introduced a symbol which denotes + 1 or −1 according as mRq or mNq being a positive odd prime and m any number prime to q); with its help we may express the law of reciprocity in the form
=(,): <»-1><q-n
This theorem was first stated by Legendre, who only partly proved it; the first complete proof, by induction, was published by Gauss, who also discovered five (or six) other more or 'less independent proofs of it. Many others have since been invented.
There are two supplementary theorems relating to −1 and 2 respectively, which, may be expressed in the form 1 = gp-n (2 = l(P2'I)
(z> l l U ' P) l ')
where p is any positive odd prime.
It follows from the definition that
<ssL-° e <@>“ere>~—fl
9 9 fl
and that = if m =m' (mod q). As a simple application of the law of reciprocity, let it be required to find the quadratic character of II with respect to 1907. We have
(ss)=~¢¥3=*(§)n
because 6N11. Hence 11R1907.
Legendre's symbol was extended by Jacobi in the following manner. Let P be any positive odd number, and let p, p', p", &c. be its (equal or unequal) prime factors, so that P=pp'p” .... Then g Q is any number prime to P, we have a generalized symbol defined
(P) - (P) (if) (fr)
This symbol obeys the law that, if Q is odd and positive, B Q HP-)(Q-)
(Q) (P)-< 1>.
with the supplementary laws
IJ. . § <P-> 3 P=(P)'(')
I~ (P) °(UA( -It
is found convenient to add the conventions that (915) = (%)
when Q and P are both odd; and that the value of the symbol is o when P, Q are not co-primes.
In order that the congruence x”-Ea (mod rn) may have a solution it is necessary and sufficient that a be a residue of each distinct prime factor of m If these conditions are all satisfied, and m=2'<p/of1. ., where p, q, &c., are the distinct odd prime factors of rn, being t in all, the number of in congruent solutions of the given congruence is 2', 2'*1 or 2'+2, according as:<<2, r=2, or l¢>2 respectively. The actual solutions are best found by a process of exhaustion. It should be observed that = 1 is a necessary but not a sufficient condition for the possibility of the congruence.
32. Quadratic forms.—It will be observed that the solution of the linear congruence ax≡b (mod m) leads to all the representations of b in the form ax-}~my, where x, y are integers. Many of the earliest researches in the theory of numbers deal with particular cases of the problem: given four numbers m, a, b, c, it is required to find all the integers x, y (if there be any) which satisfy the equation ax2+bxy+ cy” =m. F ermat, for instance, discovered that every positive prime of the form 4n+1 is uniquely expressible as the sum of two squares. There is a corresponding arithmetical theory for forms of any degree and any number of variables; only those of linear forms and binary quadratics are in any sense complete, as the difficulty of the problem increases very rapidly with the increase of the degree of the form considered or of the number of variables contained in it.
The form ax*-}»bxy+cy2 will be denoted by (ri, b, c) (x, y)' or more simply by (a, b, c) when there is no need of specifying the variables. If k is the greatest common factor of a, b, c, we may write (cz, b, c) = k(a', I/, c') where (a', b', c') is a primitive form, that is, one for which dv (a', b', c') =1. The other form is than said to be derived from (a', b', c') and to have a divisor k. For the present we shall concern ourselves only with primitive forms. Writing D =b2-4ac, the invariant D is called the determinant of (a, b, c), and there is a first classification of forms into definite forms for which D is negative, and indefinite forms for which D is positive. The case D =o or a positive square is rejected, because in that case the form breaks u p into the product of two linear factors. It will be observed that DEG, I (mod 4) according as b is even or odd; and that if ki' is, any odd square factor of D there will be forms of determinant D and divisor k.
If we write x′=ax+By, y' =-yx-l»5y, we have identically (a, b, c) (x′. y')2=(@', b'. v') (x.;v)"
where
zz' =aa2-1-ba-y+ 072
b' = 2aa/3 +b(a.5 +By) -I-2675
c' = 1182 -I-b;36 +52
Hence also
D' = b'2-4a'c' = (ao -5~/)2(b'=-4ac) = (416 ~B»y)2 D. Supposing that a, /3, fy, 6 are integers such that a6-/3'y=n, a number different from zero, (il, b, c) is said to be transformed into (a', b', c') by the substitution (3 of the nth order. If n2=I, the two forms are said to be equivalent, and the equivalence is said to be proper or improper according as ri= I or n = - I. In the case of equivalence, not only are x', y' integers wherever x, y are so, but conversely; hence every number representable by (a, b, c) is representable by (a', b', c') and conversely. For the present We shall deal with proper equivalence only and write f-f' to indicate that the forms f, f' are properly equivalent. Equivalent forms have the same divisor. A complete set of equivalent forms is said to form a class; classes of the same divisor are said to form an order, and of these the most important is the principal order, which consists of the primitive classes. It is a fundamental theorem that for a given determinant the number of classes is finite; this is proved by showing that every class must contain one at least of a certain finite number of so-called reduced forms, which can be found by dehnite rules of calculation.
33. Method of Reduction.—This differs according as D is positive or negative, and will require some preliminary lemmas. Suppose that any complex quantity z=x+yi is represented in the usual way by a point (x, y) referred to rectangular axes. Then by plotting off all the points corresponding to (az~{-5) / (yz-f-6), we obtain a complete set of properly equivalent points. These all lie on the same side of the axis of x, and there is precisely one of them and no more which satisfies the conditions: (i.) that it is not outside the area which is bounded by the lines 2x= ='=1; (ii.) that it is not inside the circle x2+y2=1; (iii.) that it is not on the line 2x=I, or on the arcs of the circle x2~i-y2 ='I intercepted by 2x= I and x=o. This point will be called the reduced point equivalent to z. In the positive half-plane (y>o) the aggregate of all reduced points occupies the interior and half the boundary of an area which will be called the fundamental triangle, because the areas equivalent to it and hnite, are all triangles bounded by circular arcs, and having angles -érr, évr, o and the fundamental trian le may be considered as a special case when one vertex goes to infinity. The aggregate of equivalent triangles forms a kind of mosaic which fills up the whole of the positive half-(plane. It will be convenient to denote the fundamental triangle (with its half-boundary, for which x<o) by V; for a reason which will appear later, the set of equivalent triangles will be said to make up the modular dissection of the positive half-plane.