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?

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.
• 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 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