Translation:Disquisitiones Arithmeticae/First Section

by Carl Friedrich Gauss

On Congruent Numbers in General

Article 1

Congruent numbers, moduli, residues and non-residues

If a number ${\textstyle a}$ divides the difference of two numbers ${\textstyle b}$ and ${\textstyle c,}$ then ${\textstyle b}$ and ${\textstyle c}$ are said to be congruent modulo ${\textstyle a;}$ otherwise they are incongruent: the number ${\textstyle a}$ will be called the modulus of the congruence. In the former case, the numbers ${\textstyle b}$ and ${\textstyle c}$ are said to be residues of each other, and in the latter case they are said to be non-residues.

These notions apply to all integers, both positive and negative^[1], but they are not to be extended to fractions.

E.g. ${\textstyle -9}$ and ${\textstyle +16}$ are congruent with respect to the modulus ${\textstyle 5;}$ ${\textstyle -7}$ is a residue of ${\textstyle 15}$ with respect to the modulus ${\textstyle 11,}$ and a non-residue with respect to the modulus ${\textstyle 5.}$

Additionally, since ${\textstyle 0}$ is divisible by any number, it follows that every number must be considered as congruent to itself with respect to any modulus.

Article 2

All residues of a given number ${\textstyle a}$ modulo ${\textstyle m}$ are included in the formula ${\textstyle a+km,}$ where ${\textstyle k}$ is an undetermined integer. The simplest of the propositions that we are going to present can be easily demonstrated in this way; but indeed their truth can be equally easily discerned by anyone who looks at them.

From now on, we will denote congruences between two numbers using the symbol ${\textstyle \equiv ,}$ adding, when necessary, the modulus enclosed in parentheses, e.g. ${\textstyle -16\equiv 9{\pmod {5}},}$ ${\textstyle -7\equiv 15{\pmod {11}}}$ ^[2].

Article 3

Theorem. Given ${\textstyle m}$ successive integers

$$a,a+1,a+2\dots a+m-1$$

and another ${\textstyle A,}$ one and only one of them will be congruent to ${\textstyle A}$ modulo ${\textstyle m.}$

If ${\textstyle {\frac {a-A}{m}}}$ is an integer, we will have ${\textstyle a\equiv A.}$ If it is a fraction, let ${\textstyle k}$ be the next largest integer (or the next smallest, if it is negative and the sign is disregarded). Then ${\textstyle A+km}$ will necessarily fall between ${\textstyle a}$ and ${\textstyle a+m,}$ and thus it will be the number which is sought. Moreover, it is clear that the quotients ${\textstyle {\frac {a-A}{m}},}$ ${\textstyle {\frac {a+1-A}{m}},}$ ${\textstyle {\frac {a+2-A}{m}}}$ etc. are between ${\textstyle k-1}$ and ${\textstyle k+1;}$ therefore no more than one of them can be an integer.

Article 4

Minimal residues.

It follows that every number will have a residue in the sequence ${\textstyle 0,}$ ${\textstyle 1,}$ ${\textstyle 2,\dots (m-1),}$ and also in the sequence ${\textstyle 0,}$ ${\textstyle -1,}$ ${\textstyle -2,\dots -(m-1).}$ We will call these minimal residues. It is clear that, unless ${\textstyle 0}$ is a residue of the number, there will always be two minimal residues, one positive and the other negative. If their magnitudes are not equal, then one of them will be ${\textstyle <{\frac {m}{2}};}$ otherwise, both will be ${\textstyle ={\frac {m}{2}},}$ the sign being disregarded; hence it follows that any number has a residue that does not exceed half the modulus, and we will call this the absolute minimum.

E.g. ${\textstyle -13}$ modulo ${\textstyle 5,}$ has minimal positive residue ${\textstyle 2,}$ which is also absolutely minimal, and also ${\textstyle -3,}$ which is the negative minimal residue; ${\textstyle +5}$ modulo ${\textstyle 7}$ is its own minimal positive residue; ${\textstyle -2}$ is the minimal negative residue, which is also the absolute minimum.

Article 5

Elementary propositions about congruences

From the notions we have just established, we immediately draw the following conclusions:

Numbers that are congruent with respect to a composite modulus are also congruent modulo any of its divisors.

If several numbers are congruent with respect to the same modulus, then they will also be congruent to each other (with respect to that modulus).

The same modulus is assumed throughout the following.

Congruent numbers have the same minimal residues; incongruent numbers have different ones.

Article 6

Given numbers ${\textstyle A,}$ ${\textstyle B,}$ ${\textstyle C}$ etc., and as many others ${\textstyle a,}$ ${\textstyle b,}$ ${\textstyle c}$ etc., and any modulus whatsoever,

If ${\textstyle A\equiv a,}$ ${\textstyle B\equiv b}$ etc., then ${\textstyle A+B+C+}$ etc. ${\textstyle \equiv a+b+c+}$ etc.

If ${\textstyle A\equiv a,}$ ${\textstyle B\equiv b,}$ then ${\textstyle A-B\equiv a-b.}$

Article 7

If ${\textstyle A\equiv a,}$ then also ${\textstyle kA\equiv ka.}$

If ${\textstyle k}$ is a positive number, then this is just a particular case of the previous article, with ${\textstyle A=B=C}$ etc., ${\textstyle a=b=c}$ etc. If ${\textstyle k}$ is negative, then ${\textstyle -k}$ will be positive; so ${\textstyle -kA\equiv -ka,}$ and therefore ${\textstyle kA\equiv ka.}$

If ${\textstyle A\equiv a,}$ ${\textstyle B\equiv b,}$ then ${\textstyle AB\equiv ab.}$ For indeed, ${\textstyle AB\equiv Ab\equiv ba.}$

Article 8

If numbers ${\textstyle A,}$ ${\textstyle B,}$ ${\textstyle C}$ etc. and ${\textstyle a,}$ ${\textstyle b,}$ ${\textstyle c}$ etc. are pairwise congruent, then the products ${\textstyle ABC}$ etc. and ${\textstyle abc}$ etc. will also be congruent.

By the previous article, ${\textstyle AB\equiv ab;}$ for the same reason ${\textstyle ABC=abc,}$ and so on.

If the numbers ${\textstyle A,}$ ${\textstyle B,}$ ${\textstyle C}$ etc. are assumed to be equal, and so are the numbers ${\textstyle a,}$ ${\textstyle b,}$ ${\textstyle c}$ etc., then we obtain the following theorem: If ${\textstyle A\equiv a}$ and ${\textstyle k}$ is a positive integer, then ${\textstyle A^{k}\equiv a^{k}.}$

Article 9

Let ${\textstyle X}$ be an algebraic function of the variable ${\textstyle x,}$ of the form

$$Ax^{a}+Bx^{b}+Cx^{c}+{\text{etc.}}$$

where ${\textstyle A,}$ ${\textstyle B,}$ ${\textstyle C}$ etc. are arbitrary integers, and ${\textstyle a,}$ ${\textstyle b,}$ ${\textstyle c\dots ,}$ are non-negative integers. If one gives congruent values to ${\textstyle x,}$ then the resulting values for ${\textstyle X}$ will also be congruent.

Let ${\textstyle f}$ and ${\textstyle g}$ be congruent values of ${\textstyle x;}$ by the previous article ${\textstyle f^{a}\equiv g^{a}}$ and ${\textstyle Af^{a}\equiv Ag^{a};}$, and similarly ${\textstyle Bf^{b}\equiv Bg^{b}}$ etc. Therefore,

$$Af^{a}+Bf^{b}+Cf^{c}+{\text{etc.}}\equiv Ag^{a}+Bg^{b}+Cg^{c}+{\text{etc.}}$$

Moreover, it is easy to understand how this theorem can be extended to functions of several variables.

Article 10

Thus if one substitutes consecutive integers in place of ${\textstyle x,}$ and the values of ${\textstyle X}$ are reduced to their minimal residues, they will form a sequence in which, after an interval of ${\textstyle m}$ terms (${\textstyle m}$ being the modulus), the same terms will reappear; that is, this sequence will be formed from a period of ${\textstyle m}$ terms, repeated ad infinitum. For example, let ${\textstyle X=x^{3}-8x+6}$ and ${\textstyle m=5.}$ Then for ${\textstyle x=0,}$ ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3}$ etc., the values of ${\textstyle X}$ yield minimal positive residues ${\textstyle 1,}$ ${\textstyle 4,}$ ${\textstyle 3,}$ ${\textstyle 4,}$ ${\textstyle 3,}$ ${\textstyle 1,}$ ${\textstyle 4}$ etc., where the first five terms ${\textstyle 1,}$ ${\textstyle 4,}$ ${\textstyle 3,}$ ${\textstyle 4,}$ ${\textstyle 3}$ are repeated ad infinitum; and if the series is continued in the opposite direction, that is, if negative values are assigned to ${\textstyle x,}$ the same period reappears with the order of the terms inverted. From this it is clear that the series does not contain any terms other than those that make up the period.

Article 11

In this example, therefore, ${\textstyle X}$ cannot become ${\textstyle \equiv 0,}$ nor ${\textstyle \equiv 2{\pmod {5}},}$ and even less ${\textstyle =0}$ or ${\textstyle =2.}$ From this it follows that the equations ${\textstyle x^{3}-8x+6=0}$ and ${\textstyle x^{3}-8x+4=0}$ can have no integer solutions, and consequently no rational solutions. It can be seen in general that when ${\textstyle X}$ is of the form

$$x^{n}+Ax^{n-1}+Bx^{n-2}+\dots +N;$$

with ${\textstyle A,}$ ${\textstyle B,}$ ${\textstyle C}$ etc. being integers, and ${\textstyle n}$ being a positive integer, that the equation ${\textstyle X=0}$ (to which form it is clear that any algebraic equation can be reduced) will have no rational roots, if it happens that for a certain modulus the congruence ${\textstyle X=0}$ cannot be satisfied; but this criterion, which arises here by itself, will be further developed in section VIII. At least from this example one can form some idea of the utility of these investigations.

Article 12

Some applications

Several of the theorems that are usually presented in arithmetic treatises rely on those we have presented; for example, the rule to recognize if a number is divisible by ${\textstyle 9,}$ ${\textstyle 11,}$ or any other number. Modulo ${\textstyle 9,}$ all powers of ${\textstyle 10}$ are congruent to unity; therefore if the proposed number is of the form ${\textstyle a+10b+100c+}$etc., then its minimal residue modulo ${\textstyle 9}$ will be the same as that of ${\textstyle a+b+c+}$etc. From this it is clear that if we add the digits of the number, disregarding the place that they occupy, the sum we obtain will have the same minimal residue as the original number, so that if the latter is divisible by ${\textstyle 9,}$ the sum of the digits will be as well, and conversely. The same applies to the divisor ${\textstyle 3.}$ Since ${\textstyle 100\equiv +1}$ modulo ${\textstyle 11,}$ we will generally have ${\textstyle 10^{2k}\equiv +1,10^{2k+1}\equiv -1,}$ and thus a number of the form ${\textstyle a+10b+100c+}$etc. will have the same minimal residue as ${\textstyle a-b+c-}$etc.; hence the well-known rule is derived immediately. All similar rules can be easily deduced from the same principle.

The above also explains the reason for the rules that are usually prescribed for verifying arithmetic operations. If some given numbers must be deduced from others by addition, subtraction, multiplication, or raising to powers, we simply substitute in the operations, in place of the given numbers, their minimal residues with respect to an arbitrary modulus (by arbitrary, I really mean ${\textstyle 9}$ or ${\textstyle 11,}$ because in the decimal system, as we have just seen, we can easily find the residues relative to these moduli). The resulting numbers must be congruent to those obtained from the given numbers, otherwise it is concluded that a defect has crept into the calculation.

But since these and the like are abundantly well known, it would be superfluous to dwell on them for too long.

1. It is clear that the modulus must be taken absolutely, i.e. without regard to sign.
2. We adopted this symbol because of the great analogy that exists between equality and congruence. It is for the same reason that Legendre, in papers that we will often have occasion to cite, used the very symbol of equality to denote congruence; we preferred another one to prevent any ambiguity.