Page:EB1911 - Volume 19.djvu/884

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 𝑥, 𝑦, 𝑧, . . . 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 𝑥≡𝑎 (mod 𝑚), where 𝑚 is the least common multiple of the moduli. Supposing that 𝑝 is a prime, and that we have a corresponding table of indices, the solution of 𝑎𝑥≡𝑏 (mod 𝑝) can be found by observing that ind 𝑥 ≡ ind 𝑏−ind 𝑎 (mod 𝑝−1).

31. Quadratic Residues. Law of Reciprocity.—To an odd prime modulus 𝑝, the numbers 1, 4, 9, . . . (𝑝−1)² are congruent to 1/2(𝑝−1) residues only, because $(p-x)^{2}=x^{2}$. Thus for 𝑝=5, we have 1, 4, 9, 16≡1, 4, 4, 1 respectively. There are therefore 1/2(𝑝−1) quadratic residues and 1/2(𝑝−1) quadratic non-residues prime to 𝑝; and there is a corresponding division of incongruent classes of integers with respect to 𝑝. 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 𝑎R𝑝, 𝑎N𝑝 to denote that 𝑎, is a residue or non-residue of 𝑝 respectively.

Given a table of indices, the solution of 𝑥²≡a(mod 𝑝) when possible, is found from 2ind 𝑥≡ind 𝑎 (mod 𝑝−1), and the result may be written in the form $x\equiv \pm r\ ({\mbox{mod}}\ p)$. But it is important to discuss the congruence $x^{2}\equiv a$ without assuming that we have a table of indices. It is sufficient to consider the case $x^{2}\equiv q\ ({\mbox{mod}}\ p)$, where 𝑞 is a positive prime less than 𝑝; and the question arises whether the quadratic character of 𝑞 with respect to 𝑝 can be deduced from that of 𝑝 with respect to 𝑞. The answer is contained in the following theorem, which is called the law of quadratic reciprocity (for real positive odd primes): if 𝑝, 𝑞 are each or one of them of the form 4𝑛+1, then 𝑝, 𝑞 are each of them a residue, or each a non-residue of the other; but if 𝑝, 𝑞 are each of the form 4𝑛+3, then according as 𝑝 is a residue or non-residue of 𝑞 we have 𝑞 a non-residue or a residue of 𝑝.

Legendre introduced a symbol $\left({\frac {m}{q}}\right)$ which denotes + 1 or −1 according as 𝑚R𝑞 or 𝑚N𝑞 being a positive odd prime and 𝑚 any number prime to 𝑞); with its help we may express the law of reciprocity in the form

$\left({p \over q}\right)\left({q \over p}\right)=(-1)^{{\frac {1}{4}}(p-1)(q-1)}$

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

$\left({-1 \over p}\right)=(-1)^{{1 \over 2}(p-1)}$, $\left({2 \over p}\right)=(-1)^{{1 \over 8}(p^{2}-1)}$

where 𝑝 is any positive odd prime.

It follows from the definition that

$\left({p_{1}^{\alpha }p_{2}^{\beta }p_{3}^{\gamma }... \over q}\right)=\left({p_{1} \over q}\right)^{\alpha }\left({p_{2} \over q}\right)^{\beta }\left({p_{3} \over q}\right)^{\gamma }...$

and that $\left({m \over q}\right)=\left({m' \over q}\right)$ if $m=m'\ ({\mbox{mod}}\ q)$. As a simple application of the law of reciprocity, let it be required to find the quadratic character of 11 with respect to 1907. We have

$\left({11 \over 1907}\right)=-\left({1907 \over 11}\right)=-\left({6 \over 11}\right)=1$

because 6N11. Hence 11R1907.

Legendre’s symbol was extended by Jacobi in the following manner. Let P be any positive odd number, and let 𝑝, 𝑝′, 𝑝″, &c. be its (equal or unequal) prime factors, so that P=𝑝𝑝′𝑝″.... Then if Q is any number prime to P, we have a generalized symbol defined by

$\left({{\mbox{Q}} \over {\mbox{P}}}\right)=\left({{\mbox{Q}} \over p}\right)\left({{\mbox{Q}} \over p'}\right)\left({{\mbox{Q}} \over p''}\right)...$

This symbol obeys the law that, if Q is odd and positive,

$\left({{\mbox{P}} \over {\mbox{Q}}}\right)\left({{\mbox{Q}} \over {\mbox{P}}}\right)=(-1)^{{1 \over 4}\left({\mbox{P}}-1\right)\left({\mbox{Q}}-1\right)}$

with the supplementary laws

$\left({-1 \over {\mbox{P}}}\right)=(-1)^{{1 \over 2}\left({\mbox{P}}-1\right)}$, $\left({2 \over {\mbox{P}}}\right)=(-1)^{{1 \over 8}\left({\mbox{P}}^{2}-1\right)}$

It is found convenient to add the conventions that

$\left({{\mbox{Q}} \over -{\mbox{P}}}\right)=\left({{\mbox{Q}} \over {\mbox{P}}}\right)$

when Q and P are both odd; and that the value of the symbol is 0 when P, Q are not co-primes.

In order that the congruence $x^{2}\equiv a\ ({\mbox{mod}}\ m)$ may have a solution it is necessary and sufficient that 𝑎 be a residue of each distinct prime factor of 𝑚    If these conditions are all satisfied, and $m=2^{\kappa }p^{\lambda }q^{\mu }$, where 𝑝, 𝑞, &c., are the distinct odd prime factors of 𝑚, being t in all, the number of incongruent solutions of the given congruence is $2^{t}$, $2^{t+1}$ or $2^{t+2}$, according as $\kappa <2$, $\kappa =2$, or $\kappa >2$ respectively. The actual solutions are best found by a process of exhaustion. It should be observed that $\left({a \over m}\right)=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\equiv b\ ({\mbox{mod}}\ m)$ leads to all the representations of 𝑏 in the form $ax+my$, where 𝑥, 𝑦 are integers. Many of the earliest researches in the theory of numbers deal with particular cases of the problem: given four numbers 𝑚, 𝑎, 𝑏, 𝑐, it is required to find all the integers 𝑥, 𝑦 (if there be any) which satisfy the equation $ax^{2}+bxy+cy^{2}=m$. Fermat, for instance, discovered that every positive prime of the form 4𝑛+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^{2}+bxy+cy^{2}$ will be denoted by $(a,\ b,\ c\ )(x,\ y)^{2}$ or more simply by $(a,\ b,\ c\ )$ when there is no need of specifying the variables. If k is the greatest common factor of 𝑎, 𝑏, 𝑐,    we may write $(a,\ b,\ c)=k(a',\ b',\ c')$ where $(a',\ b',\ c')$ is a primitive form, that is, one for which ${\mbox{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 ${\mbox{D}}=b^{2}-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 = 0 or a positive square is rejected, because in that case the form breaks up into the product of two linear factors. It will be observed that ${\mbox{D}}\equiv 0,1\ ({\mbox{mod}}\ 4)$ according as 𝑏 is even or odd; and that if $k^{2}$ is any odd square factor of D there will be forms of determinant D and divisor k.

If we write $x'=\alpha x+\beta y$, $y'=\gamma x+\delta y$, we have identically

$(a,b,c)(x',y')^{2}=(a',b',c')(x,y)^{2}$

where

$a'=a\alpha ^{2}+b\alpha \gamma +o\gamma ^{2}$ $b'=2a\alpha \beta +b(\alpha \delta +\beta \gamma )+2c\gamma \delta$ $c'=a\beta ^{2}+b\beta \delta +\delta ^{2}$

Hence also

${\mbox{D}}'=b'^{2}-4a'c'=(\alpha \delta -\beta \gamma )^{2}(b^{2}-4ac)=(\alpha \delta -\beta \gamma )^{2}{\mbox{D}}$.

Supposing that $\alpha ,\ \beta ,\ \gamma ,\ \delta$ are integers such that $\alpha \delta -\beta \gamma =n$, a number different from zero, $(a,\ b,\ c)$ is said to be transformed into $(a',\ b',\ c')$ by the substitution ${\begin{pmatrix}\alpha ,&\beta \\\gamma ,&\delta \end{pmatrix}}$ of the 𝑛th order. If $n^{2}=1$, the two forms are said to be equivalent, and the equivalence is said to be proper or improper according as $n=1$ or $n=-1$. In the case of equivalence, not only are 𝑥′, 𝑦′ integers wherever 𝑥, 𝑦 are so, but conversely; hence every number representable by (𝑎, 𝑏, 𝑐) is representable by (𝑎′, 𝑏′, 𝑐′) and conversely. For the present we shall deal with proper equivalence only and write 𝑓~𝑓′ to indicate that the forms 𝑓,𝑓′ 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 definite 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 𝑧＝𝑥+𝑦𝑖 is represented in the usual way by a point (𝑥, 𝑦) referred to rectangular axes. Then by plotting off all the points corresponding to $(\alpha z+\beta )/(\gamma z+\delta )$, we obtain a complete set of properly equivalent points. These all lie on the same side of the axis of 𝑥, 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=\pm 1$; (ii.) that it is not inside the circle $x^{2}+y^{2}=1$; (iii.) that it is not on the line $2x=1$, or on the arcs of the circle $x^{2}+y^{2}=1$ intercepted by 2𝑥＝1 and 𝑥＝0. This point will be called the reduced point equivalent to 𝑧. In the positive half-plane (𝑦>0) 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 finite, are all triangles bounded by circular arcs, and having angles 1/3π, 1/3π, 0 and the fundamental triangle 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 𝑥<0) by ∇; 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.