# Is Gauss the first who introduced congruences?

I have read Disquisitiones Arithmeticae and I have read somewhere that he introduced the concept of congruence with this book.

Wasn't this concept already used by other Mathematicians in the past?

Yes, the idea of congruences is due to Gauss. Case closed.

Earlier mathematicians had to write out divisibility relations or full equations, without the convenience of the congruence notation that make divisibility relations look like (and can be manipulated as) equations from algebra.

Why do you think it might have been introduced by someone earlier?

• I am thinking that because Euler's Theorem use congruences for instance. And it was published before Gauss was born Jan 18, 2016 at 9:54
• Euler's theorem is formulated now in terms of congruences, but that doesn't mean he expressed it that way! Quadratic reciprocity is expressed in terms of the Legendre symbol, which was introduced by Legendre near the end of the 1700s, yet Euler discovered it many decades earlier. Euler wrote his work more awkwardly than we would because he lacked the notations we are used to.
– KCd
Jan 18, 2016 at 10:54

Gauss was anticipated by Euler by about fifty years, however his notation and terminology were somewhat more rudimentary, and he did not publish his work. The ideas are contained in Euler's Tractatus de Numerorum Doctrina (Treatise on the Doctrine of Numbers) that he started writing around 1750 but never finished, it was only published posthumously in 1849, long after Disquisitiones Arithmeticae. In it Euler defined "residue" with respect to an integer $d$ as the remainder from the division by it, noted that integers are thereby divided into $d$ classes, with all numbers in a class regarded as “equivalent” (unlike Gauss Euler does not have a symbol for this equivalence). He then defined arithmetical operations on classes and showed that they are preserved by assigning the residue to its number. Other algebraic ideas also appear in the manuscript, in particular Euler shows that residues relatively prime to $d$ have multiplicative inverses, and uses what is now called coset argument in group theory to prove a generalization of the little Fermat theorem to non-prime $d$ (sometimes called the totient theorem). Euler's residue classes are of course what Gauss called congruence classes, but some modern textbooks (e.g. Rosen's Elementary Number Theory) still use the terms residue and residue class. See detailed commentary in Katz's History of Mathematics (19.1.3).

Two numbers being congruent can be expressed in terms of divisibility or remainders, so a lot of prior work could be converted into the language of congruences once Gauss introduced it. Pythagorean even-odd argument, Chinese remainder theorem, Little Fermat theorem, etc. use arguments now associated with congruences. However, to say that Pythagoreans, Sunzi or Fermat already had a "concept" of congruence would be misleading, it would be like saying that ancient Greeks already used polynomials, limits and integrals by other names. The kind of abstraction of classes, equivalence and algebraic manipulations that went into the concept of congruence as Gauss presented it in Disquisitiones Arithmeticae (and Euler somewhat anticipated) was a major new step, not contemplated and probably unnatural in earlier times.

• The Katz reference is now 19.3.2 in the 3rd edition. Your first paragraph appears to be mostly excerpted from there - including large verbatim quotes. To be fair to Katz, they should be properly quoted. May 25, 2018 at 19:38

It is worth noting that Gauss himself did not claim to be the first to invent the concept of congruence. In Disquisitiones Arithmeticae, after giving his definition of congruence and introducing his symbol $$\equiv$$, he adds the following footnote

Hoc signum propter magnam analogiam quae inter aequalitatem atque congruentiam invenitur adoptavimus. Ob eandem caussam ill. Le Gendre in comment. infra saepius laudanda ipsum aequalitatis signum pro congruentia retinuit, quod nos ne ambiguitas oriatur imitari dubitavimus.

which can be translated as

We adopted this symbol because of the great analogy that is found between equality and congruence. It is for the same reason that the illustrious Legendre, in a commentary that we will later have occasion to cite, retained the very symbol of equality for congruence. We hesitated to imitate this, lest any ambiguity arise.

To understand what Gauss is talking about here, we can simply follow his citations. This leads to the following passage in Legendre's Recherches d’Analyse indéterminée,

Pour exprimer que $$P$$ est divisible par $$A$$, ou que $$\frac{P}{A}$$ est un entier, j'ecrirai $$\frac{P}{A}=e$$. On peut omettre dans le cours du calcul tous les multiples de $$A$$: ainsi les coefficiens $$a$$, $$b$$, $$c$$, etc. et généralement tous les nombres sur lesquels on opérera, ne surpasseront jamais $$\tfrac{1}{2} A$$ en plus ou en moins. D'après cette omission on peut écrire indifféremment $$\frac{P}{A} = e$$, ou $$P=0$$, pourvu que dans le dernier cas, on ne perde pas de vue le nombre $$A$$ dont on rejette les multiples.

which can be translated as

To express that $$P$$ is divisible by $$A$$, or that $$\frac{P}{A}$$ is an integer, I will write $$\frac{P}{A}=e$$. During calculations, we can omit all multiples of $$A$$: thus the coefficients $$a$$, $$b$$, $$c$$, etc. and generally all numbers on which we operate will never exceed plus or minus $$\tfrac{1}{2} A$$. Having made this omission, we can write indifferently $$\frac{P}{A} = e$$ or $$P=0$$, provided that in the latter case, we do not lose sight of the number $$A$$ whose multiples are rejected.

While Legendre did not use or introduce terminology like "congruence", "modulus" etc. to describe what he was doing, he was certainly writing equations in which it is implicit that the two sides are not equal, but rather differ by an unspecified multiple of a given number. Further reading reveals instances where he manipulates these equations algebraically, in the same way that one manipulates ordinary equations (e.g. the first paragraph at the top of page 475).

Gauss appears to have thought that this was similar enough (or even identical) to his own concept of congruence, to the extent that he had to acknowledge it (and assert the superiority of his own notation).