Translation:Theorematis arithmetici demonstratio nova

by Carl Friedrich Gauss

1.

Questions in higher arithmetic lead frequently to singular phenomena, much more so than in analysis, and this contributes a great deal to their allure. In analytical investigations it is evidently impossible to discover new truths, unless the way to them has been revealed by our mastery of their underlying principles. On the other hand, in arithmetic it is very often the case that, through induction and by some unexpected fortune, the most elegant new truths spring up, the demonstrations of which are so deeply hidden and shrouded in so much darkness, that they elude all efforts, and deny access to the keenest investigations. Furthermore, there are so many surprising connections between arithmetic truths, which are at first sight most heterogeneous, that we not infrequently arrive at a demonstration much desired and sought after through long meditations, by a path very different from that which had been expected, while we are looking for something quite different. Generally speaking, truths of this kind are of such a nature that they can be approached by several very different paths, and it is not always the shortest paths that present themselves at first. With such a truth, which has been demonstrated through the most abstruse detours, it is certainly valuable if one happens to discover a simpler and more genuine explanation.

2.

Among the questions mentioned in the preceding article, a prominent place is held by the theorem containing almost all the theory of quadratic residues, which in Disquisitiones Arithmeticae (Sect. IV) is distinguished by the name fundamental theorem. Legendre is undoubtedly to be regarded as the first discoverer of this most elegant theorem, although the great geometers Euler and Lagrange had long before discovered several of its special cases by induction. I will not dwell here on enumerating the efforts of these men to find a demonstration; the reader is referred to their extensive work which has just been mentioned. However it is permissible to add, in confirmation of what has been stated in the previous article, an account of my own efforts. I had fallen upon the theorem on my own in 1795, at a time when I was completely ignorant of all that had already been discovered in higher arithmetic, and was completely shut out from literary resources. For a whole year it tortured me, and eluded me despite my most strenuous efforts, until at last I received the demonstration that I have delivered in the fourth Section of the aforementioned work. Afterwards, three others presented themselves to me, based on entirely different principles, one of which I delivered in the fifth Section. But all these demonstrations, even if they seem to leave nothing to be desired with regard to rigor, are derived from very heterogeneous principles, except perhaps the first, which nevertheless proceeded by more laborious reasoning, and was burdened by more extensive operations. Therefore, I have no doubt that until now a genuine demonstration has not been given; let it now be up to the experts to judge whether that which has lately been successfully discovered, and which the following pages present, deserves to be decorated with this name.

3.

Theorem. Let ${\textstyle p}$ be a positive prime number, and let ${\textstyle k}$ any integer not divisible by ${\textstyle p;}$

${\textstyle A}$ the complex of numbers ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3\ldots {\frac {1}{2}}(p-1)}$
${\textstyle B}$ the complex of numbers ${\textstyle {\frac {1}{2}}(p+1),}$ ${\textstyle {\frac {1}{2}}(p+3),}$ ${\textstyle {\frac {1}{2}}(p+5)\ldots p-1}$

Let us consider the minimal positive residues modulo ${\textstyle p}$ of the products of ${\textstyle k}$ with each of the numbers in ${\textstyle A.}$ These will obviously all be different, with some belonging to ${\textstyle A}$ and others to ${\textstyle B.}$ Now if it is assumed that, among the resulting residues, ${\textstyle \mu }$ of them belong to ${\textstyle B,}$ then ${\textstyle k}$ will either be a quadratic residue or a quadratic non-residue modulo ${\textstyle p,}$ according as ${\textstyle \mu }$ is even or odd.

Proof. Let the residues belonging to ${\textstyle A}$ be ${\textstyle a,}$ ${\textstyle a^{\prime },}$ ${\textstyle a^{\prime \prime }\ldots ,}$ and let the remaining residues belonging to ${\textstyle B}$ be ${\textstyle b,}$ ${\textstyle b^{\prime },}$ ${\textstyle b^{\prime \prime }\ldots .}$ It is clear that the complements of the latter, ${\textstyle p-b,}$ ${\textstyle p-b^{\prime },}$ ${\textstyle p-b^{\prime \prime }\ldots ,}$ are all distinct from the numbers ${\textstyle a,}$ ${\textstyle a^{\prime },}$ ${\textstyle a^{\prime \prime }\ldots ,}$ and that, taken together, they complete the complex ${\textstyle A.}$ We therefore have

$$1.2.3\ldots {\frac {1}{2}}(p-1)=aa^{\prime }a^{\prime \prime }\ldots (p-b)(p-b^{\prime })(p-b^{\prime \prime })\ldots$$

Now the latter product clearly becomes

$${\begin{aligned}&\equiv (-1)^{\mu }aa^{\prime }a^{\prime \prime }\ldots bb^{\prime }b^{\prime \prime }\ldots \equiv (-1)^{\mu }k.2k.3k\ldots {\frac {1}{2}}(p-1)k\\&\equiv (-1)^{\mu }k^{{\frac {1}{2}}(p-1)}1.2.3\ldots {\frac {1}{2}}(p-1)\quad {\pmod {p}}\end{aligned}}$$

Hence we have

$$1\equiv (-1)^{\mu }k^{{\frac {1}{2}}(p-1)}$$

or ${\textstyle k^{{\frac {1}{2}}(p-1)}\equiv \pm 1,}$ according as ${\textstyle \mu }$ is even or odd, from which our theorem immediately follows.

4.

The following considerations will be greatly shortened by the introduction of certain notation. We therefore let the symbol ${\textstyle (k,p)}$ denote the multitude of residues of the products

$$k,2k,3k,\ldots ,{\frac {1}{2}}(p-1)k,$$

whose minimal positive residues exceed ${\textstyle {\frac {1}{2}}p.}$ Moreover, for any non-integral quantity ${\textstyle x,}$ we denote by ${\textstyle [x]}$ the greatest integer less than or equal to ${\textstyle x,}$ so that ${\textstyle x-[x]}$ is always a positive quantity between ${\textstyle 0}$ and ${\textstyle 1.}$ We can then easily derive the following relations:

I. ${\textstyle [x]+[-x]=-1.}$

II. ${\textstyle [x]+h=[x+h],}$ whenever ${\textstyle h}$ is an integer.

III. ${\textstyle [x]+[h-x]=h-1.}$

IV. If ${\textstyle x-[x]}$ is a fraction smaller than ${\textstyle {\frac {1}{2}},}$ then ${\textstyle [2x]-2[x]=0;}$ if it is greater than ${\textstyle {\frac {1}{2}},}$ then ${\textstyle [2x]-2[x]=1.}$

V. If the minimal positive residue of an integer ${\textstyle h}$ exceeds ${\textstyle {\frac {1}{2}}p}$ modulo ${\textstyle p,}$ then ${\textstyle \left[{\frac {2h}{p}}\right]-2\left[{\frac {h}{p}}\right]=0;}$ if it is less than or equal to ${\textstyle {\frac {1}{2}}p}$ modulo ${\textstyle p,}$ then ${\textstyle \left[{\frac {2h}{p}}\right]-2\left[{\frac {h}{p}}\right]=1.}$

VI. From this it immediately follows that ${\textstyle (k,p)=}$

$${\begin{aligned}{\left[{\frac {2k}{p}}\right]+\left[{\frac {4k}{p}}\right]+\left[{\frac {6k}{p}}\right]\ldots +\left[{\frac {(p-1)k}{p}}\right]}\\-2\left[{\frac {k}{p}}\right]-2\left[{\frac {2k}{p}}\right]-2\left[{\frac {3k}{p}}\right]\ldots -2\left[{\frac {{\frac {1}{2}}(p-1)k}{p}}\right].\end{aligned}}$$

VII. From VI and I, we can easily deduce

$$(k,p)+(-k,p)={\frac {1}{2}}(p-1)$$

Hence, it follows that ${\textstyle -k}$ has the same or opposite relation to ${\textstyle p}$ (insofar as it is a quadratic residue or non-residue) as does ${\textstyle +k,}$ depending on whether ${\textstyle p}$ is of the form ${\textstyle 4n+1}$ or ${\textstyle 4n+3.}$ It is clear that in the former case, ${\textstyle -1}$ will be a quadratic residue modulo ${\textstyle p,}$ whereas in the latter case, it will be a quadratic non-residue.

VIII. We will transform the formula given in VI as follows. From III, we have

$$\left[{\frac {(p-1)k}{p}}\right]\equiv k-1-\left[{\frac {k}{p}}\right],\left[{\frac {(p-3)k}{p}}\right]=k-1-\left[{\frac {3k}{p}}\right],\left[{\frac {(p-5)k}{p}}\right]=k-1-\left[{\frac {5k}{p}}\right]\ldots$$

Applying these substitutions to ${\textstyle {\frac {p\mp 1}{4}}}$ terms in the series above, we have

first, if ${\textstyle p}$ is of the form ${\textstyle 4n+1,}$ then

$${\begin{aligned}(k,p)=&{\frac {1}{4}}(k-1)(p-1)\\&-2\left\{\left[{\frac {k}{p}}\right]+\left[{\frac {3k}{p}}\right]+\left[{\frac {5k}{p}}\right]\ldots +\left[{\frac {{\frac {1}{2}}(p-3)k}{p}}\right]\right\}\\&-\left\{\left[{\frac {k}{p}}\right]+\left[{\frac {2k}{p}}\right]+\left[{\frac {3k}{p}}\right]\ldots +\left[{\frac {{\frac {1}{2}}(p-1)k}{p}}\right]\right\}\end{aligned}}$$

second, if ${\textstyle p}$ is of the form ${\textstyle 4n+3,}$ then

$${\begin{aligned}(k,p)=&{\frac {1}{4}}(k-1)(p+1)\\&-2\left\{\left[{\frac {k}{p}}\right]+\left[{\frac {3k}{p}}\right]+\left[{\frac {5k}{p}}\right]\ldots +\left[{\frac {{\frac {1}{2}}(p-1)k}{p}}\right]\right\}\\&-\left\{\left[{\frac {k}{p}}\right]+\left[{\frac {2k}{p}}\right]+\left[{\frac {3k}{p}}\right]\ldots +\left[{\frac {{\frac {1}{2}}(p-1)k}{p}}\right]\right\}\end{aligned}}$$

IX. For the special case ${\textstyle k=+2,}$ it follows from the formulas given above that ${\textstyle (2,p)={\frac {1}{4}}(p\mp 1),}$ with the sign being taken as ${\textstyle +}$ or ${\textstyle -}$ depending on whether ${\textstyle p}$ is of the form ${\textstyle 4n+1}$ or ${\textstyle 4n+3.}$ Thus, ${\textstyle (2,p)}$ is even and ${\textstyle 2Rp,}$ whenever ${\textstyle p}$ is of the form ${\textstyle 8n+1}$ or ${\textstyle 8n+7;}$ on the contrary, ${\textstyle (2,p)}$ is odd and ${\textstyle 2Np,}$ whenever ${\textstyle p}$ is of the form ${\textstyle 8n+3}$ or ${\textstyle 8n+5.}$

5.

Theorem. Let ${\textstyle x}$ be a positive non-integer quantity such that no integer can be found among its multiples ${\textstyle x,}$ ${\textstyle 2x,}$ ${\textstyle 3x\ldots }$ up to ${\textstyle nx}$ . Letting ${\textstyle [nx]=h,}$ it is easily concluded that no integer can be found among the multiples of the reciprocal quantities ${\textstyle {\frac {1}{x}},}$ ${\textstyle {\frac {2}{x}},}$ ${\textstyle {\frac {3}{x}}\ldots }$ up to ${\textstyle {\frac {h}{x}}.}$ Then I say that

$$\left.{\begin{array}{l}{\phantom {+}}[x]+[2x]+[3x]\dots +[nx]\\+\left[{\frac {1}{x}}\right]+\left[{\frac {2}{x}}\right]+\left[{\frac {3}{x}}\right]\ldots +\left[{\frac {h}{x}}\right]\end{array}}\right\}=nh$$

Proof. Let ${\textstyle \Omega }$ represent the series ${\textstyle [x]+[2x]+[3x]\ldots +[nx].}$ Then the terms up to the ${\textstyle \left[{\frac {1}{x}}\right]^{\text{th}}}$ term inclusively are clearly all ${\textstyle =0;}$ the terms up to the ${\textstyle \left[{\frac {2}{x}}\right]^{\text{th}}}$ term inclusively are all ${\textstyle =1;}$ the terms up to the ${\textstyle \left[{\frac {3}{x}}\right]^{\text{th}}}$ term inclusively are all ${\textstyle =2}$ and so on. Hence we have

$$\left.{\begin{array}{rl}\Omega &=0\times \left[{\frac {1}{x}}\right]\\&+1\times \left\{\left[{\frac {2}{x}}\right]-\left[{\frac {1}{x}}\right]\right\}\\&+2\times \left\{\left[{\frac {3}{x}}\right]-\left[{\frac {2}{x}}\right]\right\}\\&+3\times \left\{\left[{\frac {4}{x}}\right]-\left[{\frac {3}{x}}\right]\right\}\\&\qquad {\text{etc.}}\\&+(h-1)\left\{\left[{\frac {h}{x}}\right]-\left[{\frac {h-1}{x}}\right]\right\}\\&+h\left\{n-\left[{\frac {h}{x}}\right]\right\}\end{array}}\right\}=hn-\left[{\frac {1}{x}}\right]-\left[{\frac {2}{x}}\right]-\left[{\frac {3}{x}}\right]\ldots -\left[{\frac {h}{x}}\right]$$

Q. E. D.

6.

Theorem. Let ${\textstyle k,}$ ${\textstyle p}$ be any odd positive integers that are prime to each other. Then

$$\left.{\begin{array}{l}{\phantom {+}}{\left[{\frac {k}{p}}\right]+\left[{\frac {2k}{p}}\right]+\left[{\frac {3k}{p}}\right]\ldots +\left[{\frac {{\frac {1}{2}}(p-1)k}{p}}\right]}\\+{\left[{\frac {p}{k}}\right]+\left[{\frac {2p}{k}}\right]+\left[{\frac {3p}{k}}\right]\ldots +\left[{\frac {{\frac {1}{2}}(k-1)p}{k}}\right]}\end{array}}\right\}={\frac {1}{4}}(k-1)(p-1).$$

Proof. Suppose, which is allowed, that ${\textstyle k<p.}$ Then ${\textstyle {\frac {{\frac {1}{2}}(p-1)k}{p}}}$ is smaller than ${\textstyle {\frac {1}{2}}k,}$ but larger than ${\textstyle {\frac {1}{2}}(k-1),}$ so ${\textstyle \left[{\frac {{\frac {1}{2}}(p-1)k}{p}}\right]={\frac {1}{2}}(k-1).}$ Hence, it is clear that the current theorem follows immediately from the previous theorem by taking ${\textstyle {\frac {k}{p}}=x,}$ ${\textstyle {\frac {1}{2}}(p-1)=n,}$ and therefore ${\textstyle {\frac {1}{2}}(k-1)=h.}$

It can be demonstrated in a similar manner that if ${\textstyle k}$ is an even number, relatively prime to ${\textstyle p,}$ then

$$\left.{\begin{array}{l}{\phantom {+}}\left[{\frac {k}{p}}\right]+\left[{\frac {2k}{p}}\right]+\left[{\frac {3k}{p}}\right]\ldots +\left[{\frac {{\frac {1}{2}}(p-1)k}{p}}\right]\\+\left[{\frac {p}{k}}\right]+\left[{\frac {2p}{k}}\right]+\left[{\frac {3p}{k}}\right]\ldots +\left[{\frac {{\frac {1}{2}}kp}{k}}\right]\end{array}}\right\}={\frac {1}{4}}k(p-1)$$

But we do not dwell on this proposition, which is not necessary for our purposes.

7.

Now, by combining the theorem mentioned above with proposition VIII of article 4, the fundamental theorem immediately follows. Indeed, let ${\textstyle k}$ and ${\textstyle p}$ be any two distinct positive prime numbers, and let

$${\begin{aligned}(k,p)+\left[{\frac {k}{p}}\right]+\left[{\frac {2k}{p}}\right]+\left[{\frac {3k}{p}}\right]\ldots +\left[{\frac {{\frac {1}{2}}(p-1)k}{p}}\right]&=L\\(p,k)+\left[{\frac {p}{k}}\right]+\left[{\frac {2p}{k}}\right]+\left[{\frac {3p}{k}}\right]\ldots +\left[{\frac {{\frac {1}{2}}(k-1)p}{k}}\right]&=M\end{aligned}}$$

Then by proposition VIII of article 4, it is clear that ${\textstyle L}$ and ${\textstyle M}$ are always even. But by the theorem of Article 6, we have

$$L+M=(k,p)+(p,k)+{\frac {1}{4}}(k-1)(p-1)$$

Therefore, when ${\textstyle {\frac {1}{4}}(k-1)(p-1)}$ turns out to be even, which occurs if either both ${\textstyle k}$ and ${\textstyle p}$ are of the form ${\textstyle 4n+1}$ or if one of them is of the form ${\textstyle 4n+1,}$ it is necessary that either both ${\textstyle (k,p)}$ and ${\textstyle (p,k)}$ are even or both are odd. On the other hand, when ${\textstyle {\frac {1}{4}}(k-1)(p-1)}$ is odd, which happens if both ${\textstyle k}$ and ${\textstyle p}$ are of the form ${\textstyle 4n+3,}$ it is necessary that one of the numbers ${\textstyle (k,p)}$ and ${\textstyle (p,k)}$ is even and the other is odd. In the former case, then, the relation of ${\textstyle k}$ to ${\textstyle p}$ and the relation of ${\textstyle p}$ to ${\textstyle k}$ (insofar as one is a quadratic residue or non-residue modulo the other) will be identical, and in the latter case they will be opposite.

Q. E. D.