Translation:Theorematis fundamentalis in doctrina de residuis quadraticis demonstrationes et ampliationes novae

by Carl Friedrich Gauss

The fundamental theorem of quadratic residues, which is said to be among the most beautiful truths of higher arithmetic, was easily discovered by induction, but it is much more difficult to demonstrate. It often happens in this subject that the simplest truths, which offer themselves spontaneously to the inquirer by induction, have demonstrations which are hidden in the deepest depths, which can only be brought to light after many fruitless attempts, and quite possibly by a different path than that by which they were sought. Then, when at first one path has been discovered, it happens not infrequently that several more appear from time to time, with some being shorter and more direct, and others arising obliquely and from very different principles, which one would have thought to be nearly unrelated to the proposed question. Strange connections of this kind between abstruse truths not only give a certain charm to these contemplations, but also deserve to be diligently investigated and analyzed, because they frequently lead to new resources or advances in science.

Therefore, although the arithmetic theorem which is to be discussed here may seem to be fully completed by previous efforts, which provided four entirely different demonstrations^[1], I nonetheless return again to the same theme, and add two more demonstrations, which will certainly shed new light on this matter. The first is in a certain way related to the third, as it proceeds from the same lemma; afterwards, however, it follows a different course, so that it can well be considered a new proof, whose elegance will be seen to be, if not superior, then at least not inferior to that of the third. On the other hand, the sixth demonstration is based on a completely different and more subtle principle and provides a new example of an astonishing connection between arithmetic truths that, at first glance, appear to be very far removed from each other. To these two demonstrations, a very simple new algorithm is added to determine whether a given integer is a quadratic residue modulo a given prime or not.

There was yet another reason, which prompted me to publish the new demonstrations at this particular moment, although they had been promised nine years ago. In 1805, when I began to investigate the theory of cubic and biquadratic residues, which is a much more difficult subject, I experienced almost the same fate as I once had in the theory of quadratic residues. Indeed, those theorems, which entirely exhaust these questions, and in which a remarkable analogy with the theorems pertaining to quadratic residues shines forth, were immediately discovered by induction as soon as a suitable approach had been found. However, all efforts to obtain them, with their demonstrations perfected in every aspect, remained fruitless for a long time. This was the incentive for me to add more and more demonstrations concerning quadratic residues to those already known, supported by the hope that among the many diverse methods, one or another might do something to reveal an analogous line of reasoning. This hope was by no means in vain, and tireless labor was finally followed by prosperous success. It will soon be possible to bring the fruits of this vigilance to public light; but before embarking on this arduous task, I decided to return once more to the theory of quadratic residues, to complete all that still remained of that agenda, and thus to bid farewell to this sublime part of arithmetic.

FUNDAMENTAL THEOREM OF THE THEORY OF QUADRATIC RESIDUES, FIFTH PROOF

1.

In the introduction, we have already stated that the fifth and third proof proceed from the same lemma. As a matter of convenience, it seems appropriate to repeat it in this place, with notation adapted to the present discussion.

Lemma. Let ${\textstyle m}$ be a prime number (positive odd), and let ${\textstyle M}$ be an integer not divisible by ${\textstyle m.}$ Consider the minimal positive residues of the numbers

$$M,2M,3M,4M,\ldots {\frac {1}{2}}(m-1)M$$

modulo ${\textstyle m.}$ Some of these will be less than ${\textstyle {\frac {1}{2}}m}$ and some will be greater; let the multitude of the latter ${\textstyle =n.}$ Then ${\textstyle M}$ will be a quadratic residue or non-residue modulo ${\textstyle m,}$ depending on whether ${\textstyle n}$ is even or odd.

Proof. Let those residues which are less than ${\textstyle {\frac {1}{2}}m}$ be denoted by ${\textstyle a,}$ ${\textstyle b,}$ ${\textstyle c,}$ ${\textstyle d}$ etc., and let the rest, which are greater than ${\textstyle {\frac {1}{2}}m,}$ be denoted by ${\textstyle a^{\prime },}$ ${\textstyle b^{\prime },}$ ${\textstyle c^{\prime },}$ ${\textstyle d^{\prime }}$ etc. The complements modulo ${\textstyle m}$ of the latter, ${\textstyle m-a^{\prime },}$ ${\textstyle m-b^{\prime },}$ ${\textstyle m-c^{\prime },}$ ${\textstyle m-d^{\prime }}$ etc., will evidently all be less than ${\textstyle {\frac {1}{2}}m,}$ and they will be distinct both among themselves and from the residues ${\textstyle a,}$ ${\textstyle b,}$ ${\textstyle c,}$ ${\textstyle d,}$ etc. Thus they will be identical, albeit in a different order, to the numbers ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3,}$ ${\textstyle 4\dots {\frac {1}{2}}(m-1).}$ So, if we set

$$1\times 2\times 3\times 4\ldots {\frac {1}{2}}(m-1)=P$$

then

$$P=abcd\ldots \times (m-a^{\prime })(m-b^{\prime })(m-c^{\prime })(m-d^{\prime })\ldots$$

and thus

$$(-1)^{n}P=abcd\ldots \times (a^{\prime }-m)(b^{\prime }-m)(c^{\prime }-m)(d^{\prime }-m)\ldots$$

Furthermore, we have

$$PM^{{\frac {1}{2}}(m-1)}\equiv abcd\ldots \times a^{\prime }b^{\prime }c^{\prime }d^{\prime }\ldots \equiv abcd\ldots \times (a^{\prime }-m)(b^{\prime }-m)(c^{\prime }-m)(d^{\prime }-m)\ldots$$

modulo ${\textstyle m,}$ so

$$PM^{{\frac {1}{2}}(m-1)}\equiv P(-1)^{n}$$

Hence ${\textstyle M^{{\frac {1}{2}}(m-1)}\equiv \pm 1,}$ where the sign is positive if ${\textstyle n}$ is even and negative if ${\textstyle n}$ is odd. Therefore, with the help of the theorem proved in Disquisitiones Arithmeticae art. 106, the truth of the lemma is immediately apparent.

2.

Theorem. Let ${\textstyle m,}$ ${\textstyle M}$ be positive odd relatively prime integers, and let ${\textstyle n}$ be the multitude of numbers in the sequence

$$M,2M,3M\ldots {\frac {1}{2}}(m-1)M$$

whose minimal positive residues modulo ${\textstyle m}$ are greater than ${\textstyle {\frac {1}{2}}m.}$ Similarly, let ${\textstyle N}$ be the multitude of numbers in the sequence

$$m,2m,3m\ldots {\frac {1}{2}}(M-1)m$$

whose minimal positive residues modulo ${\textstyle M}$ are greater than ${\textstyle {\frac {1}{2}}M.}$ Then the three numbers ${\textstyle n,}$ ${\textstyle N,}$ ${\textstyle {\frac {1}{4}}(m-1)(M-1)}$ will either be all even, or one will be even and the other two will be odd.

Proof. Let us denote

by ${\textstyle f}$ the complex of numbers ${\textstyle 1,2,3\ldots {\frac {1}{2}}(m-1)}$

by ${\textstyle f^{\prime }}$ the complex of numbers ${\textstyle m-1,m-2,m-3\ldots {\frac {1}{2}}(m+1)}$

by ${\textstyle F}$ the complex of numbers ${\textstyle 1,2,3\ldots {\frac {1}{2}}({M}-1)}$

by ${\textstyle F^{\prime }}$ the complex of numbers ${\textstyle M-1,M-2,M-3\ldots {\frac {1}{2}}(M+1)}$

Thus ${\textstyle n}$ will indicate how many numbers ${\textstyle Mf}$ have their least positive residues modulo ${\textstyle m}$ in the complex ${\textstyle f^{\prime },}$ and similarly ${\textstyle N}$ will indicate how many numbers ${\textstyle mF}$ have their least positive residues modulo ${\textstyle M}$ in the complex ${\textstyle F^{\prime }.}$ Finally, let us denote

by ${\textstyle \varphi }$ the of numbers ${\textstyle 1,2,3\ldots {\frac {1}{2}}(mM-1)}$

by ${\textstyle \varphi ^{\prime }}$ the complex of numbers ${\textstyle mM-1,mM-2,mM-3\ldots {\frac {1}{2}}(mM+1)}$

Since every integer not divisible by ${\textstyle m}$ must be congruent, modulo ${\textstyle m,}$ to a residue from the complex ${\textstyle f}$ or from the complex ${\textstyle f^{\prime },}$ and similarly every integer not divisible by ${\textstyle M}$ must be congruent to a residue from the complex ${\textstyle F}$ or from the complex ${\textstyle F^{\prime },}$ it follows that all the numbers ${\textstyle \varphi ,}$ among which obviously no one is divisible by both ${\textstyle m}$ and ${\textstyle M,}$ can be distributed into eight classes in the following way.

I. In the first class there will be those numbers which are congruent to some number from ${\textstyle f}$ modulo ${\textstyle m,}$ and congruent to some number from ${\textstyle F}$ modulo ${\textstyle M.}$ We will denote the multitude of these numbers by ${\textstyle \alpha .}$

II. Numbers congruent to numbers from ${\textstyle f,}$ ${\textstyle F^{\prime }}$ modulo ${\textstyle m,}$ ${\textstyle M,}$ respectively, the multitude of which we set ${\textstyle =\beta .}$

III. Numbers congruent to numbers from ${\textstyle f^{\prime },}$ ${\textstyle F}$ modulo ${\textstyle m,}$ ${\textstyle M,}$ respectively, the multitude of which we set ${\textstyle =\gamma .}$

IV. Numbers congruent to numbers from ${\textstyle f^{\prime },}$ ${\textstyle F^{\prime }}$ modulo ${\textstyle m,}$ ${\textstyle M,}$ respectively, the multitude of which shall be ${\textstyle =\delta .}$

V. Numbers divisible by ${\textstyle m,}$ and congruent to one of the residues from ${\textstyle F}$ modulo ${\textstyle M.}$

VI. Numbers divisible by ${\textstyle m,}$ and congruent to one of the residues from ${\textstyle F^{\prime }}$ modulo ${\textstyle M.}$

VII. Numbers divisible by ${\textstyle M,}$ congruent to one of the residues from ${\textstyle f}$ modulo ${\textstyle m.}$

VIII. Numbers divisible by ${\textstyle M,}$ congruent to one of the residues from ${\textstyle f^{\prime }}$ modulo ${\textstyle m.}$

Clearly, classes V and VI taken together will include all of the numbers ${\textstyle mF.}$ The multitude of numbers contained in VI will be ${\textstyle =N,}$ and hence the multitude of numbers contained in V will be ${\textstyle {\frac {1}{2}}(M-1)-N.}$ Similarly, classes VII and VIII taken together will contain all numbers ${\textstyle Mf,}$ in class VIII there will be ${\textstyle n}$ numbers, and in class VII there will be ${\textstyle {\frac {1}{2}}(m-1)-n.}$

Similarly, all the numbers ${\textstyle \varphi ^{\prime }}$ will be distributed into eight classes IX - XVI. If we maintain the same order, then it is easy to see that the numbers in the classes

IX, X, XI, XII, XIII, XIV, XV, XVI

are the complements modulo ${\textstyle mM}$ of the numbers in the classes

IV, III, II, I, VI, V, VIII, VII

respectively, so that in class IX there will be ${\textstyle \delta }$ numbers; in class X, there will be ${\textstyle \gamma ,}$ and so on. Now, it is clear that if all the numbers of the first class are joined with all the numbers of the ninth class, one will have all the numbers below ${\textstyle mM}$ which are congruent to some number from ${\textstyle f}$ modulo ${\textstyle m}$ , and to some number from ${\textstyle F}$ modulo ${\textstyle M.}$ It is easily seen that the multitude of these is equal to the multitude of all combinations of one individual from ${\textstyle f}$ and one individual from ${\textstyle F.}$ Therefore,

$$\alpha +\delta ={\frac {1}{4}}(m-1)(M-1)$$

and by a similar argument

$$\beta +\gamma ={\frac {1}{4}}(m-1)(M-1)$$

By joining all numbers of classes II, IV, VI, we will clearly have all numbers below ${\textstyle {\frac {1}{2}}mM,}$ which are congruent to some residue from ${\textstyle F^{\prime }}$ modulo ${\textstyle M.}$ Moreover, these same numbers can also be presented as follows:

$$F^{\prime },M+F^{\prime },2M+F^{\prime },3M+F^{\prime }\ldots {\frac {1}{2}}(m-3)M+F^{\prime }$$

from which the total number of them will be ${\textstyle ={\frac {1}{4}}(m-1)(M-1),}$ or in other words we will have

$$\beta +\delta +N={\frac {1}{4}}(m-1)(M-1)$$

Similarly, by joining the classes III, IV, VIII, it follows that

$$\gamma +\delta +n={\frac {1}{4}}(m-1)(M-1)$$

From this the following four equations arise:

$${\begin{aligned}&2\alpha ={\frac {1}{4}}(m-1)(M-1)+n+N\\&2\beta ={\frac {1}{4}}(m-1)(M-1)+n-N\\&2\gamma ={\frac {1}{4}}(m-1)(M-1)-n+N\\&2\delta ={\frac {1}{4}}(m-1)(M-1)-n-N\end{aligned}}$$

each of which demonstrates the truth of the theorem.

3.

If we now assume that ${\textstyle m}$ and ${\textstyle M}$ are prime numbers, the combination of the previous theorem with the lemma of article 1 immediately yields the fundamental theorem. For it is clear that,

I. Whenever one or both of ${\textstyle m,}$ ${\textstyle M}$ is of the form ${\textstyle 4k+1,}$ the number ${\textstyle {\frac {1}{4}}(m-1)(M-1)}$ will be even, and therefore ${\textstyle n}$ and ${\textstyle N}$ will either be both even or both odd, and thus either ${\textstyle m}$ and ${\textstyle M}$ are both quadratic residues modulo each other, or both are quadratic non-residues modulo each other.

II. Whenever ${\textstyle m,}$ ${\textstyle M}$ are both of the form ${\textstyle 4k+3,}$ the number ${\textstyle {\frac {1}{4}}(m-1)(M-1)}$ will be odd, hence one of the numbers ${\textstyle n,}$ ${\textstyle N}$ will be even and the other odd, and therefore one of the numbers ${\textstyle m,}$ ${\textstyle M}$ will be a quadratic residue modulo the other, and the other will be a quadratic non-residue modulo the one. Q. E. D.

FUNDAMENTAL THEOREM OF THE THEORY OF QUADRATIC RESIDUES, SIXTH PROOF.

1.

Theorem. Let ${\textstyle p}$ be a prime number (odd positive), let ${\textstyle n}$ be a positive integer not divisible by ${\textstyle p,}$ and let ${\textstyle x}$ be an indeterminate quantity. Then the function

$$1+x^{n}+x^{2n}+x^{3n}+{\text{etc.}}+x^{np-n}$$

will be divisible by

$$1+x+xx+x^{3}+{\text{etc.}}+x^{p-1}$$

Proof. Let ${\textstyle g}$ be a positive integer such that ${\textstyle gn\equiv 1{\pmod {p}},}$ and let ${\textstyle gn=1+hp.}$ Then we have

$${\begin{aligned}{\frac {1+x^{n}+x^{2n}+x^{3n}+{\text{etc.}}+x^{np-n}}{1+x+xx+x^{3}+{\text{etc.}}+x^{p-1}}}={\frac {(1-x^{np})(1-x)}{(1-x^{n})(1-x^{p})}}&={\frac {(1-x^{np})(1-x^{gn}-x+x^{hp+1})}{(1-x^{n})(1-x^{p})}}\\&={\frac {1-x^{np}}{1-x^{p}}}\cdot {\frac {1-x^{gn}}{1-x^{n}}}-{\frac {x(1-x^{np})}{1-x^{n}}}\cdot {\frac {1-x^{hp}}{1-x^{p}}}\end{aligned}}$$

and therefore the function is clearly integral. Q. E. D.

It follows that any integral function of ${\textstyle x}$ which is divisible by ${\textstyle {\frac {1-x^{np}}{1-x^{n}}},}$ will also be divisible by ${\textstyle {\frac {1-x^{p}}{1-x}}.}$

2.

Let ${\textstyle \alpha }$ denote a positive primitive root modulo ${\textstyle p,}$ i.e., let ${\textstyle \alpha }$ be a positive integer such that the minimal positive residues of the powers ${\textstyle 1,}$ ${\textstyle \alpha ,}$ ${\textstyle \alpha \alpha ,}$ ${\textstyle \alpha ^{3},}$ ${\textstyle \ldots ,}$ ${\textstyle \alpha ^{p-2}}$ modulo ${\textstyle p}$ are identical (without regard to order) to the numbers ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3,}$ ${\textstyle 4,}$ ${\textstyle \ldots ,}$ ${\textstyle p-1.}$ Furthermore, denoting the function

$$x+x^{\alpha }+x^{\alpha \alpha }+x^{\alpha ^{3}}+\ldots +x^{\alpha ^{p-2}}+1$$

by ${\textstyle f(x),}$ it is clear that ${\textstyle f(x)-1-x-xx-x^{3}-\ldots -x^{p-1}}$ will be divisible by ${\textstyle 1-x^{p},}$ and therefore a fortiori by ${\textstyle {\frac {1-x^{p}}{1-x}}=1+x+xx+x^{3}+\ldots +x^{p-1}.}$ From this it follows, since ${\textstyle x}$ is an indeterminate quantity, that ${\textstyle f(x^{n})}$ will also be divisible by ${\textstyle {\frac {1-x^{np}}{1-x^{n}}}}$ and consequently (by the previous article) also by ${\textstyle {\frac {1-x^{p}}{1-x}},}$ as long as ${\textstyle n}$ is an integer not divisible by ${\textstyle p.}$ Conversely, whenever ${\textstyle n}$ is an integer divisible by ${\textstyle p,}$ each part of the function ${\textstyle f(x^{n}),}$ reduced by unity, will be divisible by ${\textstyle 1-x^{p}.}$ Therefore in this case, ${\textstyle f(x^{n})-p}$ will also be divisible by ${\textstyle 1-x^{p},}$ and consequently also by ${\textstyle {\frac {1-x^{p}}{1-x}}.}$

3.

Theorem. If we set

$$x-x^{\alpha }+x^{\alpha \alpha }-x^{\alpha ^{3}}+x^{\alpha ^{4}}-{\text{etc.}}-x^{\alpha ^{p-2}}=\xi$$

then ${\textstyle \xi \xi \mp p}$ will be divisible by ${\textstyle {\frac {1-x^{p}}{1-x}},}$ if we take the upper sign whenever ${\textstyle p}$ is of the form ${\textstyle 4k+1}$ and the lower sign whenever ${\textstyle p}$ is of the form ${\textstyle 4k+3.}$

Proof. It can easily be seen that, of the ${\textstyle p-1}$ functions

$${\begin{aligned}&+x\xi -xx+x^{\alpha +1}-x^{\alpha \alpha +1}+{\text{etc.}}+x^{\alpha ^{p-2}+1}\\&-x^{\alpha }\xi -x^{2\alpha }+x^{\alpha \alpha +\alpha }-x^{\alpha ^{3}+\alpha }+{\text{etc.}}+x^{\alpha ^{p-1}+\alpha }\\&+x^{\alpha \alpha }\xi -x^{2\alpha \alpha }+x^{\alpha ^{3}+\alpha \alpha }-x^{\alpha ^{4}+\alpha \alpha }+{\text{etc.}}+x^{\alpha ^{p}+\alpha \alpha }\\&-x^{\alpha ^{3}}\xi -x^{2\alpha ^{3}}+x^{\alpha ^{4}+\alpha ^{3}}-x^{\alpha ^{5}+\alpha ^{3}}+{\text{etc.}}+x^{\alpha ^{p+1}+\alpha ^{3}}\end{aligned}}$$

etc. up to

$$-x^{\alpha ^{p-2}}\xi -x^{2\alpha ^{p-2}}+x^{\alpha ^{p-1}+\alpha ^{p-2}}-x^{\alpha ^{p}+\alpha ^{p-2}}+{\text{etc.}}+x^{\alpha ^{2p-4}+\alpha ^{p-2}}$$

the first will be ${\textstyle =0,}$ and each of the others will be divisible by ${\textstyle 1-x^{p}.}$ Therefore, the sum of all these will also be divisible by ${\textstyle 1-x^{p}.}$ This sum is

$${\begin{aligned}&=\xi \xi -(f(xx)-1)+(f(x^{\alpha +1})-1)-(f(x^{\alpha \alpha +1})-1)+(f(x^{\alpha ^{3}+1})-1)-{\text{etc.}}+(f(x^{\alpha ^{p-2}+1})-1)\\&=\xi \xi -f(xx)+f(x^{\alpha +1})-f(x^{\alpha \alpha +1})+f(x^{\alpha ^{3}+1})-{\text{etc.}}+f(x^{\alpha ^{p-2}+1})=\Omega \end{aligned}}$$

Therefore, this expression ${\textstyle \Omega }$ will also be divisible by ${\textstyle {\frac {1-x^{p}}{1-x}}.}$ Now among the exponents ${\textstyle 2,}$ ${\textstyle \alpha +1,}$ ${\textstyle \alpha \alpha +1,}$ ${\textstyle \alpha ^{3}+1\ldots \alpha ^{p-2}+1,}$ the only one divisible by ${\textstyle p}$ will be ${\textstyle \alpha ^{{\frac {1}{2}}(p-1)}+1,}$ and so by the previous article, the individual parts of the expression ${\textstyle \Omega ,}$

$$f(xx),f(x^{\alpha +1}),f(x^{\alpha \alpha +1}),f(x^{\alpha ^{3}+1}){\text{ etc.}}$$

except for the term ${\textstyle f(x^{\alpha ^{{\frac {1}{2}}(p-1)}+1}),}$ will be divisible by ${\textstyle {\frac {1-x^{p}}{1-x}}.}$ It is therefore permissible to delete those parts, and the remaining function

$$\xi \xi \mp f(x^{\alpha ^{{\frac {1}{2}}(p-1)}+1})$$

will still be divisible by ${\textstyle {\frac {1-x^{p}}{1-x}}.}$ Above the sign will be positive or negative, depending on whether ${\textstyle p}$ is of the form ${\textstyle 4k+1}$ or ${\textstyle 4k+3.}$ And since ${\textstyle f(x^{\alpha ^{{\frac {1}{2}}(p-1)}+1})-p}$ is divisible by ${\textstyle {\frac {1-x^{p}}{1-x}},}$ it follows that ${\textstyle \xi \xi \mp p}$ will also be divisible by ${\textstyle {\frac {1-x^{p}}{1-x}}.}$ Q.E.D.

To avoid any ambiguity from the double sign, we will denote by ${\textstyle \varepsilon }$ the number ${\textstyle +1}$ or ${\textstyle -1,}$ according to whether ${\textstyle p}$ is of the form ${\textstyle 4k+1}$ or ${\textstyle 4k+3.}$ Therefore,

$${\frac {(1-x)(\xi \xi -\varepsilon p)}{1-x^{p}}}$$

will be an integral function of ${\textstyle x,}$ which we will denote by ${\textstyle Z.}$

4.

Let ${\textstyle q}$ be a positive odd number, so that ${\textstyle {\frac {1}{2}}(q-1)}$ an integer. Then ${\textstyle (\xi \xi )^{{\frac {1}{2}}(q-1)}-(\varepsilon p)^{{\frac {1}{2}}(q-1)}}$ will be divisible by ${\textstyle \xi \xi -\varepsilon p,}$ and therefore also by ${\textstyle {\frac {1-x^{p}}{1-x}}.}$ If we set ${\textstyle \varepsilon ^{{\frac {1}{2}}(q-1)}=\delta ,}$ and

$$\xi ^{q-1}-\delta p^{{\frac {1}{2}}(q-1)}={\frac {1-x^{p}}{1-x}}\cdot Y$$

then ${\textstyle Y}$ will be an integral function of ${\textstyle x,}$ and we will have ${\textstyle \delta =+1}$ whenever one of the numbers ${\textstyle p,}$ ${\textstyle q,}$ or both, is of the form ${\textstyle 4k+1;}$ on the other hand, we will have ${\textstyle \delta =-1}$ whenever both ${\textstyle p,}$ ${\textstyle q}$ are of the form ${\textstyle 4k+3.}$

5.

Now, let us assume that ${\textstyle q}$ is also a prime number (different from ${\textstyle p}$). Then it is clear from the theorem proven in Disquisitiones Arithmeticae, art. 51, that

$$\xi ^{q}-(x^{q}-x^{q\alpha }+x^{q\alpha \alpha }-x^{q\alpha ^{3}}+{\text{etc.}}-x^{q\alpha ^{p-2}})$$

is divisible by ${\textstyle q,}$ or of the form ${\textstyle qX,}$ where ${\textstyle X}$ is an integral function of ${\textstyle x,}$ even with respect to its numerical coefficients (which also applies to the other integral functions occurring here, ${\textstyle Z,}$ ${\textstyle Y,}$ ${\textstyle W}$). Let us denote by ${\textstyle \mu }$ the index of the number ${\textstyle q}$ with respect to the primitive root ${\textstyle \alpha }$ modulo ${\textstyle p,}$ i.e. let ${\textstyle q\equiv \alpha ^{\mu }{\pmod {p}}.}$ Then the numbers ${\textstyle q,}$ ${\textstyle q\alpha ,}$ ${\textstyle q\alpha \alpha ,}$ ${\textstyle q\alpha ^{3}\ldots q\alpha ^{p-2}}$ will be congruent to ${\textstyle \alpha ^{\mu },}$ ${\textstyle \alpha ^{\mu +1},}$ ${\textstyle \alpha ^{\mu +2}\ldots \alpha ^{p-2},}$ ${\textstyle 1,}$ ${\textstyle \alpha ,}$ ${\textstyle \alpha \alpha \ldots \alpha ^{\mu -1}}$ modulo ${\textstyle p,}$ and thus

$${\begin{aligned}&x^{q}-x^{\alpha ^{\mu }}\\&x^{q\alpha }-x^{\alpha ^{\mu +1}}\\&x^{q\alpha \alpha }-x^{\alpha ^{\mu +2}}\\&x^{q\alpha ^{3}}-x^{\alpha ^{\mu +3}}\\&\quad \vdots \\&x^{q\alpha ^{p-\mu -2}}-x^{\alpha ^{p-2}}\\&x^{q\alpha ^{p-\mu -1}}-x\\&x^{q\alpha ^{p-\mu }}-x^{\alpha }\\&x^{q\alpha ^{p-\mu +1}}-x^{\alpha \alpha }\\&\quad \vdots \\&x^{q\alpha ^{p-2}}-x^{\alpha ^{\mu -1}}\end{aligned}}$$

will all be divisible by ${\textstyle 1-x^{p}.}$ Taking these quantities alternately positively and negatively, and adding them all up, it is clear that the function

$$x^{q}-x^{q\alpha }+x^{q\alpha \alpha }-x^{q\alpha \alpha ^{3}}+{\text{etc.}}-x^{q\alpha ^{p-2}}\mp \xi$$

will be divisible by ${\textstyle 1-x^{p},}$ provided that the sign is taken to be positive or negative depending on whether ${\textstyle \mu }$ is even or odd, i.e. depending on whether ${\textstyle q}$ is a quadratic residue or non-residue modulo ${\textstyle p.}$ Therefore, let us set

$$x^{q}-x^{q\alpha }+x^{q\alpha }-x^{q\alpha ^{3}}+{\text{etc.}}-x^{q\alpha ^{p-2}}-\gamma \xi =(1-x^{p})W$$

where ${\textstyle \gamma =+1}$ or ${\textstyle \gamma =-1}$ depending on whether ${\textstyle q}$ is a quadratic residue or non-residue modulo ${\textstyle p.}$ Then it is clear that ${\textstyle W}$ will be an integral function.

6.

Having made these preparations, we deduce by combining the preceding equations that

$$q\xi {X}=\varepsilon p(\delta p^{{\frac {1}{2}}(q-1)}-\gamma )+{\frac {1-x^{p}}{1-x}}\cdot (Z(\delta p^{{\frac {1}{2}}(q-1)}-\gamma )+Y\xi \xi -W\xi (1-x))$$

Suppose that upon dividing the function ${\textstyle \xi X}$ by

$$x^{p-1}+x^{p-2}+x^{p-3}+{\text{etc.}}+x+1$$

we obtain a quotient ${\textstyle U}$ and remainder ${\textstyle T,}$ or in other words we have

$$\xi X={\frac {1-x^{p}}{1-x}}\cdot U+T$$

where ${\textstyle U}$ and ${\textstyle T}$ are integral functions, even with respect to their numerical coefficients, and the degree of ${\textstyle T}$ is lower than the divisor. Then we will have

$$qT-\varepsilon p(\delta p^{{\frac {1}{2}}(q-1)}-\gamma )={\frac {1-x^{p}}{1-x}}\cdot (Z(\delta p^{{\frac {1}{2}}(q-1)}-\gamma )+Y\xi \xi -W\xi (1-x)-qU)$$

which is obviously false unless the left member and the right member both vanish individually. Thus ${\textstyle \varepsilon p(\delta p^{{\frac {1}{2}}(q-1)}-\gamma )}$ will be divisible by ${\textstyle q,}$ and also ${\textstyle \delta p^{{\frac {1}{2}}(q-1)}-\gamma ,}$ and therefore, because ${\textstyle \delta \delta =1,}$ the number ${\textstyle p^{{\frac {1}{2}}(q-1)}-\gamma \delta }$ will be divisible by ${\textstyle q.}$

Now if ${\textstyle \beta }$ denotes a positive or negative unit, depending on whether ${\textstyle p}$ is a quadratic residue or non-residue modulo ${\textstyle q,}$ then ${\textstyle p^{{\frac {1}{2}}(q-1)}-\beta }$ will be divisible by ${\textstyle q,}$ and therefore so will be ${\textstyle \beta -\gamma \delta ,}$ which cannot happen unless ${\textstyle \beta =\gamma \delta .}$ Hence, the fundamental theorem follows automatically. Namely,

I. Whenever both ${\textstyle p,}$ ${\textstyle q,}$ or one of them alone, is of the form ${\textstyle 4k+1,}$ and consequently ${\textstyle \delta =+1,}$ we will have ${\textstyle \beta =\gamma ,}$ and thererfore either ${\textstyle q}$ is a quadratic residue mduloo ${\textstyle p,}$ and ${\textstyle p}$ is simultaneously a quadratic residue modulo ${\textstyle q,}$ or ${\textstyle q}$ is a quadratic non-residue modulo ${\textstyle p,}$ and simultaneously ${\textstyle p}$ is a quadratic non-residue modulo ${\textstyle q.}$

II. Whenever both ${\textstyle p,}$ ${\textstyle q}$ are of the form ${\textstyle 4k+3,}$ and consequently ${\textstyle \delta =-1,}$ we will have ${\textstyle \beta =-\gamma ,}$ and therefore either ${\textstyle q}$ is a quadratic residue modulo ${\textstyle p,}$ and simultaneously ${\textstyle p}$ is a quadratic non-residue modulo ${\textstyle q,}$ or ${\textstyle q}$ is a non-residue modulo ${\textstyle p,}$ and simultaneously ${\textstyle p}$ is a residue modulo ${\textstyle q.}$ Q. E. D.

A new algorithm for determining whether a given positive integer is a quadratic residue or non-residue modulo a given prime.

1.

Before we present a new solution to this problem, we will briefly repeat the solution given in Disquisitiones Arithmeticae, which was accomplished quite expediently with the help of the fundamental theorem and the following well-known theorems:

I. The relation of a number ${\textstyle a}$ to a number ${\textstyle b}$ (insofar as the former is a quadratic residue or non-residue modulo the latter) is the same as the relation of a number ${\textstyle c}$ to ${\textstyle b,}$ if ${\textstyle a\equiv c{\pmod {b}}.}$

II. If ${\textstyle a}$ is a product of factors ${\textstyle \alpha ,}$ ${\textstyle \beta ,}$ ${\textstyle \gamma ,}$ ${\textstyle \delta ,}$ etc., and ${\textstyle b}$ is a prime number, then the relation of ${\textstyle a}$ to ${\textstyle b}$ will depend on the relation of these factors to ${\textstyle b,}$ so that ${\textstyle a}$ will be a quadratic residue or non-residue depending on whether there is an even or odd number of such factors which are quadratic non-residues modulo ${\textstyle b.}$ Thus, whenever any factor is a square, it will not be considered at all in this examination; and if any factor is a power of an integer with an odd exponent, it can be replaced with that integer instead.

III. The number 2 is a quadratic residue modulo any prime number of the form ${\textstyle 8m+1}$ or ${\textstyle 8m+7,}$ and a non-residue modulo any prime number of the form ${\textstyle 8m+3}$ or ${\textstyle 8m+5.}$

Therefore, given a number ${\textstyle a}$ whose relation to the prime number ${\textstyle b}$ is sought, we first substitute the minimal positive residue of ${\textstyle a}$ modulo ${\textstyle b}$ in place of ${\textstyle a.}$ Then, after resolving this residue into its prime factors, the problem is reduced by theorem II to the determination of the relations of each of these factors to ${\textstyle b.}$ The relation of the factor 2 (if it is present an odd number of times) to ${\textstyle b}$ is known by theorem III. The relations of the remaining factors to ${\textstyle b}$ known by the fundamental theorem. Thus instead of the relation of the given number to the prime number ${\textstyle b,}$ we must now investigate the relations of ${\textstyle b}$ to certain other odd primes smaller than ${\textstyle b}$, and these problems will be reduced in the same way to smaller moduli, and it is clear that these successive reductions will eventually be exhausted.

2.

To illustrate this solution by an example, let us seek the relation of the number ${\textstyle 103}$ to ${\textstyle 379.}$ Since ${\textstyle 103}$ is already less than ${\textstyle 379,}$ and is itself a prime number, the fundamental theorem must be applied immediately, which tells us that the relation we seek is the opposite of the relation of the number ${\textstyle 379}$ to ${\textstyle 103.}$ This in turn is equal to the relation of the number ${\textstyle 70}$ to ${\textstyle 103,}$ which depends on the relations of the numbers ${\textstyle 2,}$ ${\textstyle 5,}$ ${\textstyle 7}$ to ${\textstyle 103.}$ The first of these relations is revealed by theorem III. The second, by the fundamental theorem, depends on the relation of the number ${\textstyle 103}$ to ${\textstyle 5,}$ which by theorem I is equal to the relation of the number ${\textstyle 3}$ to ${\textstyle 5;}$ this, in turn, by the fundamental theorem, depends on the relation of the number ${\textstyle 5}$ to ${\textstyle 3,}$ which by theorem I is equal the relation of the number ${\textstyle 2}$ to ${\textstyle 3,}$ which is known by theorem III. Likewise, the relation of the number ${\textstyle 7}$ to ${\textstyle 103}$ depends, by the fundamental theorem, on the relation of the number ${\textstyle 103}$ to ${\textstyle 7,}$ which by theorem I is equal to the relation of the number ${\textstyle 5}$ to ${\textstyle 7;}$ this, in turn, by the fundamental theorem, depends on the relation of the number ${\textstyle 7}$ to ${\textstyle 5,}$ which is equal, by theorem I, to the relation of the number ${\textstyle 2}$ to ${\textstyle 5,}$ which is known by theorem III. If one prefers to transform this analysis into a synthesis, the decision of the question will be referred to the fourteen points, which we present here in full, so that the greater concision of the new solution may be the more clearly understood.

1. The number ${\textstyle 2}$ is a quadratic residue modulo ${\textstyle 103}$ (theorem III).
2. The number ${\textstyle 2}$ is a quadratic non-residue modulo ${\textstyle 3}$ (theorem III).
3. The number ${\textstyle 5}$ is a quadratic non-residue modulo ${\textstyle 3}$ (by 1 and 2).
4. The number ${\textstyle 3}$ is a quadratic non-residue modulo ${\textstyle 5}$ (fund. theorem and 3).
5. The number ${\textstyle 103}$ is a quadratic non-residue modulo ${\textstyle 5}$ (1 and 4).
6. The number ${\textstyle 5}$ is a quadratic non-residue modulo ${\textstyle 103}$ (fund. theorem and 5).
7. The number ${\textstyle 2}$ is a quadratic non-residue modulo ${\textstyle 5}$ (theorem III).
8. The number ${\textstyle 7}$ is a quadratic non-residue modulo ${\textstyle 5}$ (1 and 7).
9. The number ${\textstyle 5}$ is a quadratic non-residue modulo ${\textstyle 7}$ (fund. theorem and 8).
10. The number ${\textstyle 103}$ is a quadratic non-residue modulo ${\textstyle 7}$ (1 and 9).
11. The number ${\textstyle 7}$ is a quadratic residue modulo ${\textstyle 103}$ (fund. theorem and 10).
12. The number ${\textstyle 70}$ is a quadratic non-residue modulo ${\textstyle 103}$ (II, 1, 6, 11).
13. The number ${\textstyle 379}$ is a quadratic non-residue modulo ${\textstyle 103}$ (1 and 12).
14. The number ${\textstyle 103}$ is a quadratic residue modulo ${\textstyle 379}$ (fund. theorem and 13).

In the following, for the sake of brevity, we will use the notation introduced in Comment. Gotting. Vol. XVI. Namely, by ${\textstyle [x]}$ we will denote the quantity ${\textstyle x}$ itself, if ${\textstyle x}$ is an integer, or the greatest integer smaller than ${\textstyle x,}$ if ${\textstyle x}$ is a fractional quantity, so that ${\textstyle x-[x]}$ is always a non-negative quantity less than unity.

3.

Problem. If ${\textstyle a}$ and ${\textstyle b}$ are positive integers which are relatively prime to each other, and ${\textstyle \left[{\frac {1}{2}}a\right]=a^{\prime },}$ evaluate the sum

$$\left[{\frac {b}{a}}\right]+\left[{\frac {2b}{a}}\right]+\left[{\frac {3b}{a}}\right]+\left[{\frac {4b}{a}}\right]+{\text{etc.}}+\left[{\frac {a^{\prime }b}{a}}\right]$$

Solution. For the sake of brevity, let us denote the sum in question by ${\textstyle \varphi (a,b),}$ so that

$$\varphi (b,a)=\left[{\frac {a}{b}}\right]+\left[{\frac {2a}{b}}\right]+\left[{\frac {3a}{b}}\right]+{\text{etc.}}+\left[{\frac {b^{\prime }a}{b}}\right]$$

if we set ${\textstyle \left[{\frac {1}{2}}b\right]=b^{\prime }.}$ It was shown in the demonstration of the third fundamental theorem that in the case where ${\textstyle a}$ and ${\textstyle b}$ are both odd, we have

$$\varphi (a,b)+\varphi (b,a)=a^{\prime }b^{\prime }$$

As we already mentioned there, the truth of this proposition can also be extended to the case where only one of the numbers ${\textstyle a,}$ ${\textstyle b}$ is odd, by following the same method. Let ${\textstyle a}$ be divided by ${\textstyle b}$ in a manner analogous to the method by which the greatest common divisor of two integers is investigated, let ${\textstyle \beta }$ be the quotient, and let ${\textstyle c}$ be the remainder; then divide ${\textstyle b}$ by ${\textstyle c}$ and so on in a similar manner, so as to obtain equations

$${\begin{aligned}&a=\beta b+c\\&b=\gamma c+d\\&c=\delta d+e\\&d=\varepsilon e+f{\text{ etc.}}\end{aligned}}$$

In this way, through a series of continually decreasing numbers ${\textstyle b,}$ ${\textstyle c,}$ ${\textstyle d,}$ ${\textstyle e,}$ ${\textstyle f}$ etc., we shall eventually arive at unity, since by hypothesis ${\textstyle a}$ and ${\textstyle b}$ are coprime. Then the final equation will be

$$k=\lambda l+1$$

We clearly have

$${\begin{aligned}&{\left[{\frac {a}{b}}\right]=\left[\beta +{\frac {c}{b}}\right]=\beta +\left[{\frac {c}{b}}\right]}\\&{\left[{\frac {2a}{b}}\right]=\left[2\beta +{\frac {2c}{b}}\right]=2\beta +\left[{\frac {2c}{b}}\right]}\\&{\left[{\frac {3a}{b}}\right]=\left[3\beta +{\frac {3c}{b}}\right]=3\beta +\left[{\frac {3c}{b}}\right]}\end{aligned}}$$

etc., so

$$\varphi (b,a)=\varphi (b,c)+{\frac {1}{2}}\beta (b^{\prime }b^{\prime }+b^{\prime })$$

and therefore

$$\varphi (a,b)=a^{\prime }b^{\prime }-{\frac {1}{2}}\beta (b^{\prime }b^{\prime }+b^{\prime })-\varphi (b,c)$$

By similar reasoning, if we set ${\textstyle \left[{\frac {1}{2}}c\right]=c^{\prime },}$ ${\textstyle \left[{\frac {1}{2}}d\right]=d^{\prime },}$ ${\textstyle \left[{\frac {1}{2}}e\right]=e^{\prime }}$ etc., then

$${\begin{aligned}&\varphi (b,c)=b^{\prime }c^{\prime }-{\frac {1}{2}}\gamma (c^{\prime }c^{\prime }+c^{\prime })-\varphi (a,d)\\&\varphi (c,d)=c^{\prime }d^{\prime }-{\frac {1}{2}}\delta (d^{\prime }d^{\prime }+d^{\prime })-\varphi (d,e)\\&\varphi (d,e)=d^{\prime }e^{\prime }-{\frac {1}{2}}\varepsilon (e^{\prime }e^{\prime }+e^{\prime })-\varphi (e,f)\end{aligned}}$$

etc. up to

$$\varphi (k,l)=k^{\prime }l^{\prime }-{\frac {1}{2}}\lambda (l^{\prime }l^{\prime }+l^{\prime })-\varphi (l,1)$$

Therefore, since it is obvious that ${\textstyle \varphi (l,1)=0,}$ we obtain the formula

$${\begin{aligned}\varphi (a,b)=&a^{\prime }b^{\prime }-b^{\prime }c^{\prime }+c^{\prime }d^{\prime }-d^{\prime }e^{\prime }+{\text{etc.}}\pm k^{\prime }l^{\prime }\\&-{\frac {1}{2}}\beta (b^{\prime }b^{\prime }+b^{\prime })+{\frac {1}{2}}\gamma (c^{\prime }c^{\prime }+c^{\prime })-{\frac {1}{2}}\delta (d^{\prime }d^{\prime }+d^{\prime })+{\frac {1}{2}}\varepsilon (e^{\prime }e^{\prime }+e^{\prime })-{\text{etc.}}\mp {\frac {1}{2}}\lambda (l^{\prime }l^{\prime }+l^{\prime })\end{aligned}}$$

4.

It is easily concluded from what was set forth in the third proof, that the relation of the number ${\textstyle b}$ to ${\textstyle a,}$ whenever ${\textstyle a}$ is a prime number, is automatically known from the value of the sum ${\textstyle \varphi (a,2b).}$ Namely, ${\textstyle b}$ will be a quadratic residue or non-residue modulo ${\textstyle a}$ according to whether this sum is an even or odd number. The sum ${\textstyle \varphi (a,b)}$ itself can be used for the same purpose, but with the restriction that the case where ${\textstyle b}$ is odd must be distinguished from the case where it is even. Specifically,

I. Whenever ${\textstyle b}$ is odd, ${\textstyle b}$ will be a quadratic residue or non-residue modulo ${\textstyle a,}$ depending on whether ${\textstyle \varphi (a,b)}$ is even or odd.

II. Whenever ${\textstyle b}$ is even, the same rule will hold, if in addition ${\textstyle a}$ is of the form ${\textstyle 8n+1}$ or of the form ${\textstyle 8n+7.}$ If however, for an even value of ${\textstyle b}$ the modulus ${\textstyle a}$ is of the form ${\textstyle 8n+3}$ or ${\textstyle 8n+5,}$ the opposite rule must be applied, namely that ${\textstyle b}$ will be a quadratic residue modulo ${\textstyle a}$ if ${\textstyle \varphi (a,b)}$ is odd, but it will be a non-residue if ${\textstyle \varphi (a,b)}$ is even.

All of this is very easily derived from article 4 of the third proof.

5.

Example. If the ratio of the number 103 to the prime number 379 is sought, then to find the sum ${\textstyle \varphi (379,103),}$ we first compute

$${\begin{array}{r|r|r}a=379&a^{\prime }=189&\\b=103&b^{\prime }={\phantom {0}}51&\beta =3\\c={\phantom {0}}70&c^{\prime }={\phantom {0}}35&\gamma =1\\d={\phantom {0}}33&d^{\prime }={\phantom {0}}16&\delta =2\\e={\phantom {00}}4&e^{\prime }={\phantom {00}}2&\varepsilon =8\end{array}}$$

hence

$$\varphi (379,103)=9639-1785+560-32-3978+630-272+24=4786$$

and thus ${\textstyle 103}$ is a quadratic residue modulo ${\textstyle 379.}$ If we want to use the sum ${\textstyle \varphi (379,206)}$ for the same purpose, we have the following pattern,

$${\begin{array}{r|r|r}379&189&\\206&103&1\\173&86&1\\33&16&5\\8&4&4\end{array}}$$

from which we deduce

$$\varphi (379,206)=19467-8858+1376-64-5356+3741-680+40=9666$$

and thus 103 is a quadratic residue modulo 379.

6.

Since in order to determine the relation of ${\textstyle b}$ to ${\textstyle a,}$ it is not necessary to compute each part of the aggregate ${\textstyle \varphi (a,b),}$ but rather it is sufficient to know how many of them are odd, our rule can also be expressed as follows:

Let ${\textstyle a=\beta b+c,}$ ${\textstyle b=\gamma c+d,}$ ${\textstyle c=\delta d+e}$ etc., until the series of numbers ${\textstyle a,}$ ${\textstyle b,}$ ${\textstyle c,}$ ${\textstyle d,}$ ${\textstyle e}$ etc. reaches unity. Set ${\textstyle \left[{\frac {1}{2}}a\right]=a^{\prime },}$ ${\textstyle \left[{\frac {1}{2}}b\right]=b^{\prime },}$ ${\textstyle \left[{\frac {1}{2}}c\right]=c^{\prime }}$ etc., and let ${\textstyle \mu }$ be the multitude of odd numbers in the series ${\textstyle a^{\prime },}$ ${\textstyle b^{\prime },}$ ${\textstyle c^{\prime }}$ etc. which are immediately followed by an odd number; further, let ${\textstyle \nu }$ be the multitude of odd numbers in the series ${\textstyle \beta ,}$ ${\textstyle \gamma ,}$ ${\textstyle \delta }$ etc., such that the corresponding number in the series ${\textstyle b^{\prime },}$ ${\textstyle c^{\prime },}$ ${\textstyle d^{\prime }}$ etc. is of the form ${\textstyle 4n+1}$ or ${\textstyle 4n+2.}$ With this being done, ${\textstyle b}$ will be a quadratic residue or non-residue modulo ${\textstyle a,}$ depending on whether ${\textstyle \mu +\nu }$ is even or odd, except in the case where ${\textstyle b}$ is even and ${\textstyle a}$ is of the form ${\textstyle 8n+3}$ or ${\textstyle 8n+5,}$ in which case the opposite rule holds.

In our example, the sequence ${\textstyle a^{\prime },}$ ${\textstyle b^{\prime },}$ ${\textstyle c^{\prime },}$ ${\textstyle d^{\prime },}$ ${\textstyle e^{\prime }}$ has two consecutive pairs of odd numbers, hence ${\textstyle \mu =2,}$ and in the series ${\textstyle b^{\prime },}$ ${\textstyle c^{\prime },}$ ${\textstyle d^{\prime },}$ ${\textstyle e^{\prime },}$ there are two odd numbers, but the corresponding numbers in ${\textstyle b^{\prime },}$ ${\textstyle c^{\prime },}$ ${\textstyle d^{\prime },}$ ${\textstyle e^{\prime }}$ are of the form ${\textstyle 4n+3,}$ hence ${\textstyle \nu =0.}$ Therefore, ${\textstyle \mu +\nu }$ is even, and it follows that 103 is a quadratic residue modulo 379.

1. Two have been set forth in the Disquisitiones Arithmeticae, Sections four and five; the third in a separate treatise (Commentt. Soc. Gotting. Vol. XVI), the fourth is included in the treatise: Summation of certain singular series (Commentt. Recentiores, Vol. I).