# How and where was the notion of a primitive root formulated before Gauss?

Gauss credits Euler (and I think some others) with having known of the existence of primitive roots. How did these predecessors of Gauss formulate the notion of a primitive root without a concept of congruence? In what works, and in what context? In particular, since the notion of a primitive root seems quite unnatural to me if you don't have a notion of congruence (I mean, the shortest definition I can think of is "A number $a$ such that for every possible remainder $r$ there is an integer $n$ such that $a^n$ is $r$ more than a multiple of $p$"), what led Euler and other pre-Gaussian mathematicians to consider such a concept?

## 1 Answer

According to Dickson's history book Lambert in 1769 was the first to grasp the concept by claiming that for any prime $p$ there was a number $g$ such that $g^{p-1}-1$ was divisible by $p$, but $g^e-1$ was not for any $0<e<p-1$. Euler coined the term "primitive root" in 1773 when he attempted to prove Lambert's claim in 1773, but his proof had a flaw. He also listed primitive roots for primes up to 41, but noted that he had no general way of finding them. Lagrange gave a result about polynomials in 1777 that fills the gap, and Lagrange in 1785 connected primitive roots to roots of unity, where the concept arises very naturally.

Gauss himself was partly motivated by roots of unity since he wanted to prove that certain polygons were constructible when a primitive root of unity could be expressed using only square roots. Gauss only defined congruences in their modern form in Disquisitiones Arithmeticae (completed in 1798 but published only in 1801), where he gave two proofs of their existence for primes.

• His work on regular polygons is not why he cared about primitive roots mod primes. It's his work on decimals that shows the importance of primitive roots: for any prime $p$ other than $2$ or $5$, the period length of the decimal expansion for $1/p$ is the order of $10 \bmod p$, so this period length is at most $p-1$ (in fact, it divides $p-1$) and it can be $p-1$ if and only if $10$ is a primitive root mod $p$. This is why Lambert, before Gauss, wanted to know whether there is always some primitive root mod $p$. See hal.archives-ouvertes.fr/halshs-00663295/document. – KCd Feb 10 '15 at 22:30
• @KCd Nice, I didn't know about decimals. But one does not exclude the other. He was working on inscribable polygons around the same time (1796), and that involved in his words "intensive consideration of the relation of all the roots to one another on arithmetical ground", i.e. in terms of congruences. Constructions of polygons are directly related to finding primitive roots "on arithmetical ground". jstor.org/stable/2972265?seq=1#page_scan_tab_contents – Conifold Feb 11 '15 at 1:27
• Sure, constructing regular polygons using unmarked straightedge and compass is related to complex roots of unity, but I don't see why the phenomena of primitive roots in modular arithmetic (particularly modulo primes) is linked to that. In any case, the question was why the notion of a primitive root mod primes came up before Gauss and the study of periods in decimal expansions of rational numbers was one motivation. – KCd Feb 11 '15 at 2:35
• @KCd Primitive root modulo a prime are needed to form quadratic equations (from so-called Gauss periods) that express cyclotomic roots via nested square roots when the prime is of the form $2^m+1$, see a sketch of Gauss's proof in $\S$5 of journals.cambridge.org/… Gauss gives the construction in section VII of Disquisitiones Arithmeticae after proving existence of primitive roots modulo primes in section III. – Conifold Feb 11 '15 at 19:14
• @KCd please consider writing an answer of your own: It seems like you have some interesting things to say about this issue! :) – Danu Feb 14 '15 at 8:28