Translation:Disquisitiones Arithmeticae/Third Section

by Carl Friedrich Gauss

On Residues of Powers

Article 45

The residues of the terms of a geometric progression starting from unity constitute a periodic series.

Theorem. Let ${\textstyle a}$ be relatively prime to ${\textstyle p.}$ Then the geometric progression ${\textstyle 1,}$ ${\textstyle a,}$ ${\textstyle aa,}$ ${\textstyle a^{3}}$ etc. has at least one term ${\textstyle a^{t},}$ aside than the first term ${\textstyle 1,}$ which is congruent to unity modulo ${\textstyle p,}$ and whose exponent ${\textstyle t}$ is ${\textstyle <p.}$

Proof. Since the modulus ${\textstyle p}$ is relatively prime to ${\textstyle a,}$ and consequently is also relatively prime to any power of ${\textstyle a,}$ no term of the progression will be ${\textstyle \equiv 0{\pmod {p}}}$ but each of them will be congruent to one of the numbers ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3\dots p-1.}$ Since the multitude of this series of numbers is ${\textstyle p-1,}$ it is clear that if more than ${\textstyle p-1}$ terms of the progression are considered, they cannot all have different minimal residues. So among the numbers ${\textstyle 1,}$ ${\textstyle a,}$ ${\textstyle a^{2},}$ ${\textstyle a^{3}\dots a^{p-1},}$ at least two will be congruent. Therefore, letting ${\textstyle a^{m}\equiv a^{n}}$ with ${\textstyle m>n,}$ and dividing by ${\textstyle a^{n}}$ (Art. 22), we obtain ${\textstyle a^{m-n}\equiv 1,}$ where ${\textstyle m-n<p}$ and ${\textstyle >0.}$ Q.E.D.

Ex. In the progression ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 4,}$ ${\textstyle 8}$ etc., the first term congruent to unity modulo ${\textstyle 13}$ is ${\textstyle 2^{12}=4096,}$ but in the same progression modulo ${\textstyle 23,}$ we have ${\textstyle 2^{11}=2048\equiv 1;}$ similarly, ${\textstyle 5^{6}=15625\equiv 1{\pmod {7}}}$ and ${\textstyle 5^{5}=3125\equiv 1{\pmod {11}}.}$ Thus in some cases, the exponent of the power congruent to unity is smaller than ${\textstyle p-1,}$ and in other cases, one must go all the way to the ${\textstyle {p-1}^{st}}$ power.

Article 46

When the progression is continued beyond the term congruent to unity, one will find the same residues as those obtained from the beginning. Thus, if ${\textstyle a^{t}\equiv 1,}$ we will have ${\textstyle a^{t+1}\equiv a,}$ ${\textstyle a^{t+2}\equiv a^{2}}$etc., until we reach the term ${\textstyle a^{2t}}$ whose minimal residue will again be ${\textstyle \equiv 1,}$ and the period of residues will begin again. We will thus have a period of ${\textstyle t}$ residues, which always repeats itself from the beginning as soon as it is finished; and no residues other than those in this period can occur in the entire progression. In general, we will have ${\textstyle a^{mt}\equiv 1}$ and ${\textstyle a^{mt+n}\equiv a^{n};}$ which can be represented in our notation as follows:

If ${\textstyle r\equiv \rho {\pmod {t}},}$ then ${\textstyle a^{r}\equiv a^{\rho }{\pmod {p}}.}$

Article 47

This theorem provides an expeditious method of finding residues of powers, regardless of the magnitude of the exponent they are raised to, as soon as the power congruent to unity is known. If e.g. one asks for the remainder which arises upon dividing ${\textstyle 3^{1000}}$ by ${\textstyle 13,}$ then since ${\textstyle 3^{3}\equiv 1{\pmod {13}},}$ we have ${\textstyle t\equiv 3,}$ and therefore, since ${\textstyle 1000\equiv 1{\pmod {3}},}$ we obtain ${\textstyle 3^{1000}\equiv 3{\pmod {13}}.}$

Article 48

If ${\textstyle a^{t}}$ is the smallest power congruent to unity, (excluding ${\textstyle a^{0}=1,}$ a case which we do not consider), then the ${\textstyle t}$ residues that make up the period will all be distinct, as can be easily seen from the demonstration in Art. 45. Then the proposition from Art. 46 can be reversed; namely, if ${\textstyle a^{m}\equiv a^{n}{\pmod {p}},}$ we will have ${\textstyle m\equiv n{\pmod {t}}.}$ For if ${\textstyle m}$ and ${\textstyle n}$ were incongruent modulo ${\textstyle t,}$ their minimal residues ${\textstyle \mu }$ and ${\textstyle \nu }$ would be different. But ${\textstyle a^{\mu }\equiv a^{m}}$ and ${\textstyle a^{\nu }\equiv a^{n},}$ hence ${\textstyle a^{\mu }\equiv a^{\nu },}$ meaning that all powers below ${\textstyle a^{t}}$ would not be incongruent, contrary to the hypothesis.

So if ${\textstyle a^{k}\equiv 1{\pmod {p}},}$ we will have ${\textstyle k\equiv 0{\pmod {t}},}$ meaning that ${\textstyle k}$ will be divisible by ${\textstyle t.}$

So far we have only discussed moduli that are relatively prime to ${\textstyle a.}$ We will now separately consider absolutely prime moduli, and establish a more general investigation on this foundation.

Article 49

On moduli which are prime numbers.

Theorem. If ${\textstyle p}$ is a prime number that does not divide ${\textstyle a,}$ and ${\textstyle a^{t}}$ is the smallest power of ${\textstyle a}$ congruent to unity, the exponent ${\textstyle t}$ will be ${\textstyle =p-1,}$ or an aliquot part of ${\textstyle p-1.}$

See Art. 45 for examples.

Since we have already proved that ${\textstyle t}$ is ${\textstyle =p-1}$ or ${\textstyle <p-1,}$ it remains to show that in the latter case it is always an aliquot part of ${\textstyle p-1.}$

I. Let us gather the minimal positive residues of all the terms ${\textstyle 1,}$ ${\textstyle a,}$ ${\textstyle aa\dots a^{t-1},}$ and denote them by ${\textstyle \alpha ,}$ ${\textstyle \alpha ',}$ ${\textstyle \alpha ''}$etc., so that we have ${\textstyle \alpha \equiv 1,}$ ${\textstyle \alpha '\equiv a,}$ ${\textstyle \alpha ''\equiv a^{2}}$etc. It is clear that these will all be distinct; for if two terms ${\textstyle a^{m}}$ and ${\textstyle a^{n}}$ gave the same residue, then (assuming ${\textstyle m>n}$) we would have ${\textstyle a^{m-n}\equiv 1,}$ and ${\textstyle m-n<t,}$ which is absurd, since ${\textstyle a^{t}}$ is the smallest power of ${\textstyle a}$ congruent to unity (by hypothesis). Moreover, all numbers ${\textstyle \alpha ,}$ ${\textstyle \alpha ',}$ ${\textstyle \alpha ''}$etc. are included in the series ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3,}$ ${\textstyle 4\dots p-1,}$ a series they do not exhaust when ${\textstyle t<p-1.}$ We will denote by ${\textstyle (A)}$ the complex of all these residues, which includes a total of ${\textstyle t}$ terms.

II. Let ${\textstyle \beta }$ be an arbitrary number from the series ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3\dots p-1}$ which is missing from ${\textstyle (A).}$ Compute the products of ${\textstyle \beta }$ with ${\textstyle \alpha ,}$ ${\textstyle \alpha ',}$ ${\textstyle \alpha ''}$ etc., and let their minimal residues be ${\textstyle \beta ,}$ ${\textstyle \beta ',}$ ${\textstyle \beta ''}$ etc., the number of which will also be ${\textstyle t.}$ These residues will be distinct, both from each other and also from the numbers ${\textstyle \alpha ,}$ ${\textstyle \alpha ',}$ ${\textstyle \alpha ''}$etc. Indeed, if the former assertion were false, we would have ${\textstyle \beta a^{m}\equiv \beta a^{n},}$ and dividing by ${\textstyle \beta }$ would give us ${\textstyle a^{m}\equiv a^{n},}$ contrary to what we have just demonstrated. If the latter were false, then we would have ${\textstyle \beta a^{m}\equiv a^{n}.}$ When ${\textstyle m<n,}$ this yields ${\textstyle \beta \equiv a^{n-m},}$ i.e. ${\textstyle \beta }$ would be congruent to one of the numbers ${\textstyle \alpha ,}$ ${\textstyle \alpha ',}$ ${\textstyle \alpha ''}$etc., contrary to the hypothesis; and when ${\textstyle n<m,}$ we will have, upon multiplying by ${\textstyle a^{t-m},}$ ${\textstyle \beta a'\equiv a^{t+n-m}}$ or, since ${\textstyle a^{t}\equiv 1,}$ ${\textstyle \beta \equiv a^{t-(m-n)},}$ which is the same absurdity. Letting ${\textstyle (B)}$ denote the complex of the numbers ${\textstyle \beta ,}$ ${\textstyle \beta ',}$ ${\textstyle \beta ''}$ etc., whose multitude is ${\textstyle t,}$ we now have ${\textstyle 2t}$ numbers from the series ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3,}$ ${\textstyle }$etc. ${\textstyle p-1.}$ So, if ${\textstyle (A)}$ and ${\textstyle (B)}$ exhaust this series, then we have ${\textstyle t={\frac {p-1}{2}}.}$

III. If some are missing, let ${\textstyle \gamma }$ be one of those. Multiply ${\textstyle \alpha ,}$ ${\textstyle \alpha ',}$ ${\textstyle \alpha ''}$etc., by ${\textstyle \gamma ,}$ let ${\textstyle \gamma ,}$ ${\textstyle \gamma ',}$ ${\textstyle \gamma ''}$etc., be the minimal residues of these products, and let ${\textstyle (C)}$ denote the complex of all such residues. Then ${\textstyle (C)}$ will include ${\textstyle t}$ numbers taken from the series ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3\dots p-1,}$ which are distinct from both each other and the numbers in ${\textstyle (A)}$ and ${\textstyle (B).}$ The first two assertions are proven as in II. For the third, if we had ${\textstyle \gamma a^{m}\equiv \beta a^{n},}$ we would obtain either ${\textstyle \gamma \equiv \beta a^{n-m},}$ or ${\textstyle \gamma \equiv \beta a^{t+n-m},}$ depending on whether ${\textstyle m<n}$ or ${\textstyle >n.}$ In either case, ${\textstyle \gamma }$ would be congruent to one of the numbers in ${\textstyle (B),}$ contrary to the hypothesis. We will therefore have ${\textstyle 3t}$ numbers from the series ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3\dots p-1,}$ and if none are left over, then we will have ${\textstyle t={\frac {p-1}{3}},}$ and the theorem has been demonstrated.

IV. But if there are still some left over, we will arrive in the same way at a fourth complex of numbers ${\textstyle (D),}$ and so on. Since the series ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3\dots p-1}$ is finite, it will eventually be exhausted, and therefore ${\textstyle p-1}$ will be a multiple of ${\textstyle t:}$ thus ${\textstyle t}$ will be an aliquot part of ${\textstyle p-1.}$ Q.E.D.

Article 50

Fermat's Theorem.

Since ${\textstyle {\frac {p-1}{t}}}$ is an integer, raising each member of the congruence ${\textstyle a^{t}\equiv 1{\pmod {p}}}$ to the power ${\textstyle {\frac {p-1}{t}}}$shows that ${\textstyle a^{p-1}\equiv 1{\pmod {p}};}$ that is, ${\textstyle a^{p-1}-1}$ will always be divisible by ${\textstyle p,}$ when ${\textstyle p}$ is prime and does not divide ${\textstyle a.}$

This theorem, which is remarkable both for its elegance and its great utility, is usually called Fermat’s theorem, after the name of the inventor. See Fermatii Opera Mathem. Tolosae 1679 fol. p. 163. Fermat did not provide a proof, although he claimed to have found one. Euler was the first to publish it in his dissertation entitled Theorematum quorundam ad numeros primos spectantium demonstratio, Comm. Ac. Pétrop. T. VIII.^[1] It is derived from the expansion of ${\textstyle (a+1)^{p}.}$ From the form of the coefficients in this expansion, it is easy to deduce that ${\textstyle (a+1)^{p}-a^{p}-1}$ is always divisible by ${\textstyle p,}$ and consequently ${\textstyle (a+1)^{p}-(a+1)}$ will be divisible by ${\textstyle p}$ whenever ${\textstyle a^{p}-a}$ is. Now since ${\textstyle 1^{p}-1}$ is always divisible by ${\textstyle p,}$ ${\textstyle 2^{p}-2}$ will be as well; hence so will be ${\textstyle 3^{p}-3,}$ and generally ${\textstyle a^{p}-a.}$ Therefore, if ${\textstyle p}$ does not divide ${\textstyle a,}$ ${\textstyle a^{p-1}-1}$ will be divisible by ${\textstyle p.}$ What we have just said is sufficient to understand the nature of the method. Lambert gave a similar proof in Actis Erudit. 1769, p. 109. But since the binomial expansion of a power seems alien to number theory, Euler provided another proof Comment. nov. Petr. T. VIII, p. 70. that exactly agrees with the one we have just presented. In the future, other proofs will be presented: here we will be content to give another one derived from the same principle as Euler’s. The following proposition, of which the theorem in question is only a particular case, will be useful for other investigations below.

Article 51

If ${\textstyle p}$ is a prime number, then the ${\textstyle p^{th}}$ power of ${\textstyle a+b+c+}$etc. is

$$\equiv a^{p}+b^{p}+c^{p}+$$

etc. modulo ${\textstyle p.}$

It is known that ${\textstyle (a+b+c+{\text{ etc.}})^{p}}$ is composed of terms of the form ${\textstyle Pa^{\alpha }b^{\beta }c^{\gamma }}$etc. where we have ${\textstyle \alpha +\beta +\gamma +{\text{ etc.}}=p,}$ ${\textstyle P}$ being the number of permutations of ${\textstyle p}$ objects, of which ${\textstyle \alpha ,}$ ${\textstyle \beta ,}$ ${\textstyle \gamma }$ etc. are respectively equal to ${\textstyle a,}$ ${\textstyle b,}$ ${\textstyle c}$ etc. But in Art. 41 above we have shown that this number is always divisible by ${\textstyle p,}$ unless all the letters are equal to each other; i.e. unless one of the numbers ${\textstyle \alpha ,}$ ${\textstyle \beta ,}$ ${\textstyle \gamma }$ etc., is ${\textstyle =p}$ and the others are ${\textstyle =0.}$ From this it follows that all the terms of the expansion, except ${\textstyle a^{p},}$ ${\textstyle b^{p}}$ etc. are divisible by ${\textstyle p,}$ and therefore ${\textstyle (a+b+c+{\text{ etc.}})^{p}\equiv a^{p}+b^{p}+c^{p}+{\text{ etc.}}{\pmod {p}}.}$ If all the quantities ${\textstyle a,}$ ${\textstyle b,}$ ${\textstyle c}$ etc. are assumed to be ${\textstyle =1,}$ and their number is ${\textstyle k,}$ then we will have ${\textstyle k^{p}\equiv k,}$ as in the previous article.

Article 52

How many numbers generate a period whose multitude is a given divisor of ${\textstyle \,p-1.}$

Since the divisors of ${\textstyle p-1}$ are the only numbers that can serve as exponents for the smallest powers congruent to unity, one is led to ask whether all divisors of ${\textstyle p-1}$ enjoy this property; and, when classifying all numbers not divisible by ${\textstyle p}$ according to the exponent of their smallest power congruent to unity, how many there are for each exponent. We immediately observe that it suffices to consider positive numbers from ${\textstyle 1}$ to ${\textstyle p-1{:}}$ for it is clear that congruent numbers must be raised to the same power to become congruent to unity, and therefore any number must be raised to the same exponent as its minimum positive residue. We must therefore investigate how the numbers ${\textstyle 1,2,3\dots p-1}$ are distributed among the factors of ${\textstyle p-1,}$ in this respect.

For the sake of brevity, if ${\textstyle d}$ is one of the divisors of ${\textstyle p-1,}$ (among which which ${\textstyle 1}$ and ${\textstyle p-1}$ are to be included), we will denote by ${\textstyle \psi d}$ the multitude of positive numbers less than ${\textstyle p,}$ whose ${\textstyle d^{th}}$ power is the smallest power congruent to unity.

Article 53

In order to make ourselves more easily understood, we will first present an example. For ${\textstyle p=19,}$ the numbers ${\textstyle 1,2,3\dots 18}$ are distributed among the divisors of ${\textstyle 18}$ as follows:

$${\begin{array}{r|rrrrrr}1&1.&&&&&\\2&18.&&&&&\\3&7,&11.&&&&\\6&8,&12.&&&&\\9&4,&5,&6,&9,&16,&17.\\18&2,&3,&10,&13,&14,&15.\end{array}}$$

So in this case ${\textstyle \psi 1=1,}$ ${\textstyle \psi 2=1,}$ ${\textstyle \psi 3=2,}$ ${\textstyle \psi 6=2,}$ ${\textstyle \psi 9=6,}$ ${\textstyle \psi 18=6.}$ With a little attention, one can see that the multitude of numbers belonging to each exponent is equal to the multitude of numbers relatively prime to and not greater than that exponent. Equivalently, retaining the notation of Art. 39, we have ${\textstyle \psi d=\phi d.}$ This observation can be proved in general, as follows.

I. If there is a number ${\textstyle a}$ belonging to the exponent ${\textstyle d,}$ i.e. one whose ${\textstyle d^{th}}$ power is congruent to unity, and whose lower powers are incongruent, then its powers ${\textstyle aa,}$ ${\textstyle a^{3},}$ ${\textstyle a^{4}\dots a^{d},}$ or equivalently their minimal residues, will also have the property that their ${\textstyle d^{th}}$ powers are congruent to unity. In other words, the minimal residues of the numbers ${\textstyle a,}$ ${\textstyle aa,}$ ${\textstyle a^{3}\dots a^{d},}$ which are all distinct, will be roots of the congruence ${\textstyle x^{d}\equiv 1.}$ Since this congruence can have no more than ${\textstyle d}$ distinct roots, it is clear that the minimal residues of ${\textstyle a,}$ ${\textstyle a^{2},}$ ${\textstyle a^{3}\dots a^{d},}$ are the only numbers between ${\textstyle 1}$ and ${\textstyle p-1}$ whose ${\textstyle d^{th}}$ powers are congruent to unity. Hence it follows that the numbers belonging to the exponent ${\textstyle d}$ can be found among the minimal residues of the numbers ${\textstyle a,}$ ${\textstyle a^{2},}$ ${\textstyle a^{3}\dots a^{d}.}$ Which these are, and what their multitude is, will now be determined. If ${\textstyle k}$ is a number relatively prime to ${\textstyle d,}$ then none of the powers of ${\textstyle a^{k},}$ with exponent ${\textstyle <d,}$ will be congruent to unity. Indeed, suppose that ${\textstyle {\frac {1}{k}}{\pmod {d}}\equiv m}$ (see Art. 31). Then we will have ${\textstyle a^{km}\equiv a,}$ and thus if the ${\textstyle e^{th}}$ power of ${\textstyle a^{k}}$ were congruent to unity, with ${\textstyle e<d,}$ then we would also have ${\textstyle a^{kme}\equiv 1,}$ and consequently ${\textstyle a^{e}\equiv 1,}$ contrary to the hypothesis. Hence it is clear that the minimal residue of ${\textstyle a^{k}}$ belongs to the exponent ${\textstyle d.}$ On the other hand, if ${\textstyle k}$ had a common divisor ${\textstyle \delta }$ with ${\textstyle d,}$ then the minimal residue of ${\textstyle a^{k}}$ would not belong to the exponent ${\textstyle d,}$ since the ${\textstyle {\frac {d}{\delta }}^{th}}$ power of ${\textstyle a^{k}}$ is congruent to unity (for ${\textstyle {\frac {kd}{\delta }}}$ is divisible by ${\textstyle d,}$ or equivalently ${\textstyle \equiv 0{\pmod {d}},}$ and therefore ${\textstyle a^{\frac {kd}{\delta }}\equiv 1}$). From this we conclude that there are as many numbers belonging to the exponent ${\textstyle d}$ as there are numbers relatively prime to ${\textstyle d}$ in the series ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3,\dots ,d.}$ But it must be remembered that this conclusion is based on the supposition that there is already a number ${\textstyle a}$ belonging to the exponent ${\textstyle d.}$ Therefore, it remains doubtful whether every exponent has a number belonging to it, and the only conclusion we can draw is that ${\textstyle \psi d}$ is either ${\textstyle =0}$ or ${\textstyle =\phi d.}$

Article 54

II. Let ${\textstyle d,}$ ${\textstyle d',}$ ${\textstyle d''}$ etc. be the divisors of ${\textstyle p-1.}$ Since the numbers ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3\dots p-1}$ must be distributed among these divisors, we will have

$$\psi d+\psi d'+\psi d''+\dots =p-1.$$

But (Art. 40) we have shown that

$$\phi d+\phi d'+\phi d''+\dots =p-1,$$

and in the previous article we saw that ${\textstyle \psi d}$ is less than or equal to ${\textstyle =\phi d.}$ The same goes for ${\textstyle \psi d'}$ and ${\textstyle \phi d',}$ etc. Therefore, if one or more of the terms in the sequence ${\textstyle \psi d,}$ ${\textstyle \psi d'',}$ ${\textstyle }$etc., were less than the corresponding term in the sequence ${\textstyle \phi d,}$ ${\textstyle \phi d',}$ ${\textstyle }$etc., then the sum of the former could not be equal to the sum of the latter. Hence, we conclude that ${\textstyle \psi d}$ and ${\textstyle \phi d}$ are always equal to each other, regardless of the magnitude of ${\textstyle p-1.}$

Article 55

The particular case of the previous proposition which most deserves our attention is the following: there always exist numbers such that none of their powers below the ${\textstyle {p-1}^{st}}$ is congruent to unity, and indeed, there are as many between the ${\textstyle 1^{st}}$ and ${\textstyle {p-1}^{st}}$ as there are numbers less than and relatively prime to ${\textstyle p-1.}$ Since the demonstration of this theorem is by no means as obvious as it may appear to be at first sight, it is worth giving another demonstration which is slightly different from the previous one, especially because a diversity of methods often contributes a great deal to the elucidation of obscure matters.

First decompose ${\textstyle p-1}$ into prime factors, so that ${\textstyle p-1=a^{\alpha }b^{\beta }c^{\gamma }}$etc., where ${\textstyle a,}$ ${\textstyle b,}$ ${\textstyle c}$etc. are distinct prime numbers. The proof of the theorem then proceeds according to the following steps:

I. We can always find a number ${\textstyle A}$ (or several) belonging to the exponent ${\textstyle a^{\alpha },}$ and similarly numbers ${\textstyle B,}$ ${\textstyle C}$ etc. belonging to the exponents ${\textstyle b^{\beta },}$ ${\textstyle c^{\gamma }}$ etc.,

II. The product of the numbers ${\textstyle A,}$ ${\textstyle B,}$ ${\textstyle C}$ etc., or the minimal residue of this product, belongs to the exponent ${\textstyle p-1.}$ This can be proved as follows.

I. Since the congruence ${\textstyle x^{\frac {p-1}{a}}\equiv 1{\pmod {p}}}$ has degree ${\textstyle <p-1,}$ it cannot be satisfied by all numbers in the series ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3\dots p-1.}$ Therefore, we can find such a number ${\textstyle g}$ which does not satisfy the congruence. If we then set ${\textstyle h=g^{\frac {p-1}{a}}}$, I claim that the minimal residue of ${\textstyle h}$ belongs to the exponent ${\textstyle a^{\alpha }.}$

Indeed, it is clear that ${\textstyle h^{a^{\alpha }}}$ is congruent to ${\textstyle g^{p-1},}$ i.e. to unity, but ${\textstyle h^{a^{\alpha -1}}}$ is congruent to ${\textstyle g^{\frac {p-1}{a}},}$ which is not congruent to unity. No less will the powers ${\textstyle h^{a^{\alpha -2}},}$ ${\textstyle h^{a^{\alpha -3}}}$ be congruent to unity. But the exponent of the smallest power of ${\textstyle h}$ which is congruent to unity, that is the exponent to which ${\textstyle h}$ belongs, must be a divisor of ${\textstyle a^{\alpha }}$ (Art. 48); and since ${\textstyle a^{\alpha }}$ is only divisible by itself and by lower powers of ${\textstyle a,}$ it necessarily follows that ${\textstyle a^{\alpha }}$ will be the exponent to which ${\textstyle b}$ belongs. It can be shown by a similar method that one can find numbers belonging to the exponents ${\textstyle b^{\beta },}$ ${\textstyle c^{\gamma }}$etc.

II. If we assume that the product of all numbers ${\textstyle A,}$ ${\textstyle B,}$ ${\textstyle C}$ etc. does not belong to the exponent ${\textstyle p-1}$ etc., but rather to a smaller exponent ${\textstyle t,}$ then ${\textstyle t}$ must be one of the divisors of ${\textstyle p-1}$ (Art. 48), or in other words ${\textstyle {\frac {p-1}{t}}}$ will be an integer greater than unity. It follows that this quotient will be one of the prime numbers ${\textstyle a,}$ ${\textstyle b,}$ ${\textstyle c}$ etc., or at least divisible by one of them (Art. 17), e.g. by ${\textstyle a,}$ as the reasoning would be the same for the others. Thus ${\textstyle t}$ will divide ${\textstyle {\frac {p-1}{a}},}$ and so the product ${\textstyle ABC}$ etc., raised to the power ${\textstyle {\frac {p-1}{a}},}$ would still be congruent to unity (Art. 46). But it is clear that all numbers ${\textstyle B,}$ ${\textstyle C,}$ ${\textstyle D}$ etc. (except ${\textstyle A}$) become congruent to unity when raised to the power ${\textstyle {\frac {p-1}{a}},}$ since the exponents ${\textstyle b^{\beta },}$ ${\textstyle c^{\gamma },}$etc. to which they belong, divide ${\textstyle {\frac {p-1}{a}}.}$ Therefore

$$A^{\frac {p-1}{a}}B^{\frac {p-1}{a}}C^{\frac {p-1}{a}}{\text{etc.}}\equiv A^{\frac {p-1}{a}}\equiv 1,$$

so ${\textstyle a^{\alpha }}$ must divide ${\textstyle {\frac {p-1}{a}}}$ (Art. 48), i.e. ${\textstyle {\frac {p-1}{a^{\alpha +1}}}}$ is an integer; but ${\textstyle {\frac {p-1}{a^{\alpha +1}}}\equiv {\frac {b^{\beta }c^{\gamma }{\text{etc.}}}{a}}}$ is not an integer (Art. 15). Therefore our assumption cannot hold, i.e. the product ${\textstyle ABC}$ etc. actually belongs to the exponent ${\textstyle p-1.}$

This proof seems a bit longer than the first one, but it is more direct.

Article 56

This theorem provides us with a remarkable example of the circumspection needed in number theory, so as not to consider as proven things that are not. Lambert, refers to this proposition in the dissertation we have praised above, Acta Erudit. 1769 p. 127, but he says nothing about the necessity of proving it. No one has even attempted to do so, except the great Euler, Comment. nov. Ac. Petrop. T. XVIII, 1774, p. 85, Demonstrationes circa residua ex divisione potestatum per numeros primos resultantia. See especially article 37, in which he extensively discussed the need to prove this proposition. However, the demonstration of this penetrating man has two defects; one is that he tacitly assumes, starting in article 31, that the congruence ${\textstyle x^{n}\equiv 1}$ (translating his arguments into our notation) actually has ${\textstyle n}$ different roots, while it was only demonstrated that this congruence cannot have more; the other is that he only deduces the formula of Art. 34 by induction.

Article 57

Primitive roots, bases, indices.

Following Euler, we will call the numbers that belong to the exponent ${\textstyle p-1}$ primitive roots. So if ${\textstyle a}$ is a primitive root, then all the minimal residues of the powers ${\textstyle a,}$ ${\textstyle a^{2},}$ ${\textstyle a^{3}\dots a^{p-1}}$ will be distinct, from which one easily deduces that they all lie among the numbers ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3\dots p-1,}$ which are in the same number as them, i.e. that every number not divisible by ${\textstyle p}$ is congruent to some power of ${\textstyle a.}$ This remarkable property is of great utility, and can considerably shorten the arithmetic operations related to congruences, in much the same way that the introduction of logarithms shortens the operations of ordinary arithmetic. We will take an arbitrarily chosen primitive root ${\textstyle a}$ as the base, to which we will refer all numbers not divisible by ${\textstyle p,}$ and if ${\textstyle a^{e}\equiv b{\pmod {p}},}$ we will call ${\textstyle e}$ the index of ${\textstyle b.}$ E.g. for the modulus ${\textstyle 19,}$ if we take the primitive root ${\textstyle 2}$ as the base, then $${\begin{matrix}&{\text{the numbers}}&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18\\&{\text{have indices}}&0&1&13&2&16&14&6&3&8&17&12&15&5&7&11&4&10&9\end{matrix}}$$

Moreover, it is clear that for a given base each number has several indices, but these are all congruent modulo ${\textstyle p-1;}$ thus indices which are congruent modulo ${\textstyle p-1}$ will be considered equivalent, just as numbers are considered equivalent when they are congruent modulo ${\textstyle p.}$

Article 58

Algorithm for computing indices.

The theorems concerning indices are precisely analogous to those concerning logarithms.

The index of a product of any number of factors is congruent to the sum of the indices of the different factors, modulo ${\textstyle p-1.}$

The index of a power of a number is congruent, modulo ${\textstyle p-1,}$ to the product of the exponent by the index of the given number.

We omit the proofs because of their simplicity.

Thus if we wanted to construct a table that gives the indices of all numbers for various moduli, then all numbers larger than the modulus and all composite numbers could be omitted. An attempt at such a table can be found at the end of this work (Tab. I). The prime numbers and powers of prime numbers from ${\textstyle 3}$ to ${\textstyle 97,}$ which are to be regarded as moduli, can be found in the first column. The numbers taken as bases are in the nexdt column; then follow the indices of successive prime numbers, which are written in groups of five each; at the top are the prime numbers arranged in the same order, so that one can easily find the index that corresponds to a given prime number, for a given modulus.

E.g. if ${\textstyle p=67,}$ then the index of the number ${\textstyle 60,}$ with ${\textstyle 12}$ taken as the base, will be

$$\equiv 2\operatorname {Ind.} 2+\operatorname {Ind.} 3+\operatorname {Ind.} 5\equiv {58}+9+39\equiv 40{\pmod {66}}$$

Article 59

The index of the value of any expression ${\textstyle {\frac {a}{b}}{\pmod {p}},}$ (Art. 31) is congruent modulo ${\textstyle p-1}$ to the difference of the indices of the numerator ${\textstyle a}$ and the denominator ${\textstyle b,}$ provided that the numbers ${\textstyle a}$ and ${\textstyle b}$ are not divisible by ${\textstyle p.}$

Let ${\textstyle c}$ be any value of this expression; we will have ${\textstyle bc\equiv a{\pmod {p}};}$ hence

$$\operatorname {Ind.} b+\operatorname {Ind.} c\equiv \operatorname {Ind.} a{\pmod {p-1}},$$

and therefore

$$\operatorname {Ind.} c\equiv \operatorname {Ind.} a-\operatorname {Ind.} b.$$

Therefore, if we have two tables, one giving the indices corresponding to each number for some modulus, and the other giving the numbers corresponding to given indices, then we can easily solve all linear congruences, since they can always be reduced to others with prime moduli (Art. 30). E.g. for the congruence

$$29x+7\equiv 0{\pmod {47}}$$

we have

$$x\equiv {\tfrac {-7}{29}}{\pmod {47}}$$

Thus,

$$\operatorname {Ind.} x\equiv \operatorname {Ind.} -7-\operatorname {Ind.} {29}\equiv \operatorname {Ind.} 40-\operatorname {Ind.} 29\equiv 15-43\equiv 18{\pmod {46}};$$

Now ${\textstyle 3}$ is the number with index ${\textstyle 18;}$ therefore ${\textstyle x\equiv 3{\pmod {47}}.}$ We have not added the second table; but another can be used in its place, as we will show in Sect. VI.

Article 60

On the roots of the congruence $x^{n}\equiv A.$

Just as we introduced notation for the roots of first degree congruencesin Art. 31, in what follows we will introduce another sign for the roots of pure congruences of higher degrees. Just as the symbol ${\textstyle {\sqrt[{n}]{A}}}$ represents nothing other than a root of the equation ${\textstyle x^{n}\equiv A,}$ so will the symbol ${\textstyle {\sqrt[{n}]{A}}{\pmod {p}}}$ represent an arbitrary root of the congruence ${\textstyle x^{n}\equiv A{\pmod {p}}.}$ Thus we will say that the expression ${\textstyle {\sqrt[{n}]{A}}{\pmod {p}}}$ has as many values as it has incongruent ones modulo ${\textstyle p,}$ because all those congruent modulo ${\textstyle p}$ must be considered equivalent (Art. 26). Furthermore, it is clear that if ${\textstyle A}$ and ${\textstyle B}$ are congruent modulo ${\textstyle p,}$ then the expressions ${\textstyle {\sqrt[{n}]{A}}{\pmod {p}}}$ and ${\textstyle {\sqrt[{n}]{B}}{\pmod {p}}}$ will be equivalent.

Now if we take ${\textstyle {\sqrt[{n}]{A}}\equiv x{\pmod {p}},}$ we will have ${\textstyle n\operatorname {Ind.} x\equiv \operatorname {Ind.} A{\pmod {p-1}}.}$ From this congruence, and the rules of the previous section, we can deduce the values of ${\textstyle \operatorname {Ind.} x,}$ and hence the corresponding values of ${\textstyle x.}$ However, it is easy to see that ${\textstyle x}$ has as many values as there are roots of the congruence ${\textstyle n\operatorname {Ind.} x\equiv \operatorname {Ind.} A{\pmod {p-1}}.}$ Therefore, ${\textstyle {\sqrt[{n}]{A}}}$ will have only one value when ${\textstyle n}$ is coprime to ${\textstyle p-1,}$ but when the greatest common divisor of ${\textstyle n}$ and ${\textstyle p-1}$ is ${\textstyle \delta ,}$ there will be ${\textstyle \delta }$ incongruent values of ${\textstyle \operatorname {Ind.} x}$ modulo ${\textstyle p-1,}$ and consequently ${\textstyle {\sqrt[{n}]{A}}}$ will have equally many incongruent values modulo ${\textstyle p,}$ provided that ${\textstyle \operatorname {Ind.} A}$ is divisible by ${\textstyle \delta .}$ Without this condition, ${\textstyle {\sqrt[{n}]{A}}}$ will have no real values.

For instance, if one seeks the values of the expression ${\textstyle {\sqrt[{15}]{11}}{\pmod {19}},}$ one must solve the congruence ${\textstyle 15\operatorname {Ind.} x\equiv \operatorname {Ind.} 11\equiv 6{\pmod {18}},}$ from which one obtains three values ${\textstyle \operatorname {Ind.} x\equiv 4,}$ ${\textstyle 10,}$ ${\textstyle 16{\pmod {18}}.}$ The values of ${\textstyle x}$ corresponding to these are ${\textstyle 6,}$ ${\textstyle 9,}$ ${\textstyle 4.}$

Article 61

Although this method is very expedient when the necessary tables are available, we should not forget that it is indirect. So, it will be worthwhile to investigate how fruitful direct methods can be. We will now present some observations that can be deduced from the previous notions; others, which require more subtle considerations, will be reserved until Section VIII.

Let us begin with the simplest case, in which ${\textstyle A=1,}$ or equivalently, in which one seeks the roots of the congruence ${\textstyle x^{n}\equiv 1{\pmod {p}}.}$ Taking an arbitrary primitive root as the base, we have ${\textstyle \operatorname {Ind.} x\equiv 0{\pmod {p-1}}.}$ When ${\textstyle n}$ is relatively prime to ${\textstyle p-1,}$ this congruence will have only one root, namely ${\textstyle \operatorname {Ind.} x\equiv 0{\pmod {p-1}}{:}}$ so in this case ${\textstyle {\sqrt[{n}]{1}}{\pmod {p}}}$ will have only one value, namely ${\textstyle \equiv 1.}$ However, when ${\textstyle n}$ and ${\textstyle p-1}$ have ${\textstyle \delta }$ as their greatest common divisor, the complete solution of the congruence ${\textstyle n\operatorname {Ind.} x\equiv 0{\pmod {p-1}}}$ will be ${\textstyle x\equiv 0{\pmod {\frac {p-1}{\delta }}}}$ (see Art. 29), i.e. ${\textstyle \operatorname {Ind.} x}$ must be congruent to one of the numbers

$$0,{\frac {p-1}{\delta }},{\frac {2(p-1)}{\delta }},{\frac {3(p-1)}{\delta }},\dots {\frac {(\delta -1)(p-1)}{\delta }}$$

modulo ${\textstyle p-1,}$ and so will have ${\textstyle \delta }$ incongruent values modulo ${\textstyle p-1;}$ thus ${\textstyle x}$ will also have ${\textstyle \delta }$ distinct values (incongruent modulo ${\textstyle p.}$). From this one can see that the expression ${\textstyle {\sqrt[{\delta }]{1}}{\pmod {p}}}$ has ${\textstyle \delta }$ distinct values, whose indices are the numbers listed above; therefore the expression ${\textstyle {\sqrt[{\delta }]{1}}{\pmod {p}}}$ is entirely equivalent to the expression ${\textstyle {\sqrt[{n}]{1}}{\pmod {p}},}$ i.e. the congruence ${\textstyle x^{\delta }\equiv 1{\pmod {p}}}$ and the congruence ${\textstyle x^{n}\equiv 1{\pmod {p}}}$ have the same roots; but the former will be of a lower degree unless ${\textstyle \delta =n.}$

Ex. ${\textstyle {\sqrt[{15}]{1}}{\pmod {19}}}$ has three values, because ${\textstyle 3}$ is the greatest common divisor of ${\textstyle 15}$ and ${\textstyle 18;}$ these will also be the values of the expression ${\textstyle {\sqrt[{3}]{1}}{\pmod {19}}.}$ The three values are ${\textstyle 1,}$ ${\textstyle 7,}$ ${\textstyle 11.}$

Article 62

This reduction offers us a great advantage, since we no longer need to solve congruences of the form ${\textstyle x^{n}\equiv 1{\pmod {p}}}$ other than those where ${\textstyle n}$ is a divisor of the reduced module by unity. Later we will show that congruences of this form can be reduced even further, although the method above is insufficient to do so. However, there is one case that we can fully address here, namely the case ${\textstyle n=2.}$ Indeed, it is clear that the values of the expression ${\textstyle {\sqrt[{2}]{1}}{\pmod {p}}}$ will always be ${\textstyle +1}$ and ${\textstyle -1,}$ since it cannot have more than two values, and ${\textstyle +1}$ and ${\textstyle -1}$ are incongruent, unless the modulus is ${\textstyle =2,}$ in which case it is clear that ${\textstyle {\sqrt[{2}]{1}}}$ will only have one value. It follows that ${\textstyle +1}$ and ${\textstyle -1}$ are also the values of the expression ${\textstyle {\sqrt[{2m}]{1}}{\pmod {p}},}$ whenever ${\textstyle m}$ is relatively prime with ${\textstyle {\frac {p-1}{2}}.}$ This will happen for any modulus such that ${\textstyle {\frac {p-1}{2}}}$ is an absolutely prime number (unless ${\textstyle p-1=2m,}$ in which case all numbers ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3\dots p-1}$ are roots) e.g. when ${\textstyle p=3,}$ ${\textstyle 5,}$ ${\textstyle 7,}$ ${\textstyle 11,}$ ${\textstyle 23,}$ ${\textstyle 47,}$ ${\textstyle 59,}$ ${\textstyle 83,}$ ${\textstyle 107}$ etc. As a corollary, we observe that the index of ${\textstyle -1}$ is always ${\textstyle \equiv {\frac {p-1}{2}}{\pmod {p-1}},}$ regardless of the primitive root chosen as the base. Indeed, ${\textstyle 2\operatorname {Ind.} (-1)\equiv 0{\pmod {p-1}}.}$ Thus ${\textstyle \operatorname {Ind.} (-1)}$ will either be ${\textstyle \equiv 0}$ or ${\textstyle \equiv {\frac {p-1}{2}}:}$ but ${\textstyle 0}$ is always the index of ${\textstyle +1,}$ and ${\textstyle +1}$ and ${\textstyle -1}$ always have different indices (except in the case where ${\textstyle p=2,}$ which is not worth considering here).

Article 63

We have shown (Art. 60) that the expression ${\textstyle {\sqrt[{n}]{A}}{\pmod {p}}}$ either has ${\textstyle \delta }$ different values or none at all, if ${\textstyle \delta }$ is the greatest common divisor of ${\textstyle n}$ and ${\textstyle p-1.}$ Just as we found that ${\textstyle {\sqrt[{n}]{A}}}$ and ${\textstyle {\sqrt[{\delta }]{A}}}$ were equivalent when ${\textstyle A\equiv 1,}$ we will prove more generally that the expression ${\textstyle {\sqrt[{n}]{A}}}$ can always be reduced to another equivalent expression ${\textstyle {\sqrt[{\delta }]{B}}}$. Let ${\textstyle x}$ denote any value such that ${\textstyle x^{n}\equiv A,}$ and let ${\textstyle t}$ denote any value of the expression ${\textstyle {\frac {\delta }{n}}{\pmod {p-1}},}$ which will always have real values, as we saw in Art. 31. Then we will have ${\textstyle x^{tn}\equiv A^{t};}$ but because ${\textstyle tn\equiv \delta {\pmod {p-1}},}$ we will have ${\textstyle x^{tn}\equiv x^{\delta }.}$ Thus ${\textstyle x^{\delta }\equiv A^{t},}$ and therefore any value of ${\textstyle {\sqrt[{n}]{A}}}$ will also be a value of ${\textstyle {\sqrt[{\delta }]{A^{t}}}.}$ So, whenever ${\textstyle {\sqrt[{n}]{A}}}$ has real values, it will be precisely equivalent to the expression ${\textstyle {\sqrt[{\delta }]{A^{t}}},}$ since it can neither have different nor fewer values, although it is true that ${\textstyle {\sqrt[{\delta }]{A^{t}}}}$ can have real values without necessarily ${\textstyle {\sqrt[{n}]{A}}}$ having them.

Ex. To find the values of the expression ${\textstyle {\sqrt[{21}]{2}}{\pmod {31}},}$ we observe that the greatest common divisor of the numbers ${\textstyle 21}$ and ${\textstyle 30}$ is ${\textstyle 3,}$ and ${\textstyle 3}$ is a value of ${\textstyle {\frac {3}{21}}{\pmod {30}},}$ so if ${\textstyle {\sqrt[{21}]{2}}}$ has real values, it will be equivalent to the expression ${\textstyle {\sqrt[{3}]{2^{3}}}}$ or ${\textstyle {\sqrt[{3}]{8}},}$ and indeed we find that the values of the latter are ${\textstyle 2,}$ ${\textstyle 10,}$ and ${\textstyle 19,}$ which also satisfy the former.

Article 64

In order to not undertake this operation unnecessarily, we must look for rules by which we can immediately deduce whether ${\textstyle {\sqrt[{n}]{A}}}$ admits real values or not. If we have a table of indices, the matter is easy, because it is clear from Art. 60 that ${\textstyle {\sqrt[{n}]{A}}}$ will have real values whenever the index of ${\textstyle A}$ is divisible by ${\textstyle \delta ,}$ no matter which primitive root is taken as the base, and otherwise it will not have real values. However, we can also discover this without the help of this table. If ${\textstyle k}$ is the index of ${\textstyle A,}$ and ${\textstyle k}$ is divisible by ${\textstyle \delta ,}$ then ${\textstyle {\frac {k(p-1)}{\delta }}}$ will be divisible by ${\textstyle p-1,}$ and vice versa. But the index of the number ${\textstyle A^{\frac {p-1}{\delta }}}$ is ${\textstyle {\frac {k(p-1)}{\delta }}.}$ Therefore, if ${\textstyle {\sqrt[{n}]{A}}{\pmod {p}}}$ has real values, ${\textstyle A^{\frac {p-1}{\delta }}}$ will be congruent to unity, and otherwise it will not be congruent to unity. Thus in the example of the previous article, we have ${\textstyle 2^{10}=1024\equiv 1{\pmod {31}},}$ from which we conclude that ${\textstyle {\sqrt[{21}]{2}}{\pmod {31}}}$ has real values. Similarly, we see from this that ${\textstyle {\sqrt[{2}]{-1}}{\pmod {p}}}$ always has two real values when ${\textstyle p}$ is of the form ${\textstyle 4m+1,}$ and has none when ${\textstyle p}$ is of the form ${\textstyle 4m+3;}$ for ${\textstyle (-1)^{2m}=1}$ and ${\textstyle (-1)^{2m+1}=-1.}$ This elegant theorem, which is usually stated as follows: If ${\textstyle p}$ is a prime number of the form ${\textstyle 4m+1,}$ then we can find a square ${\textstyle aa}$ such that ${\textstyle aa+1}$ is divisible by ${\textstyle p;}$ but if ${\textstyle p}$ is of the form ${\textstyle 4m-1,}$ no such square can be found, was demonstrated in this way by Euler, Comm. nov. Acad. Petrop. T. XVIII, p. 112, in 1773. He had given another proof of it much earlier, Comm. nov. T. V, p. 5, which came out in 1760. In an earlier dissertation (T. iv, p. 25), he had not yet reached the goal. Lagrange later also provided a proof of this theorem, Nouveaux Mém. de l’Ac. de Berlin, 1775, p. 342. We will present yet another proof in the following section, in which this topic will be treated properly.

Article 65

After examining how one can reduce all expressions ${\textstyle {\sqrt[{n}]{A}}{\pmod {p}}}$ to others in which ${\textstyle n}$ is a divisor of ${\textstyle p-1,}$ and after finding a criterion which allows to recognize whether there are real roots or not, let us consider with more care the expressions ${\textstyle {\sqrt[{n}]{A}}{\pmod {p}},}$ where ${\textstyle n}$ is a divisor of ${\textstyle p-1.}$ We will first discuss the relationship between the different values of this expression, and then we will indicate some tricks through which one can often find one of the values.

First, when ${\textstyle A\equiv 1,}$ and ${\textstyle r}$ is one of the ${\textstyle n}$ values of the expression ${\textstyle {\sqrt[{n}]{1}}{\pmod {p}},}$ or equivalently ${\textstyle r^{n}\equiv 1{\pmod {p}},}$ then all powers of ${\textstyle r}$ will also be values of this expression; and there will be as many different values as there are units in the exponent to which ${\textstyle r}$ belongs (Art. 48). So, if ${\textstyle r}$ is a value belonging to the exponent ${\textstyle n,}$ then its powers ${\textstyle r,}$ ${\textstyle r^{2},}$ ${\textstyle r^{3}\dots r^{n}}$ (where the last can be replaced with unity) will include all values of the expression ${\textstyle {\sqrt[{n}]{1}}{\pmod {p}}.}$ We will explain in more detail in section VIII how one can find these values belonging to the exponent ${\textstyle n.}$

Second, when ${\textstyle A}$ is not congruent to unity, and one knows a value ${\textstyle z}$ of the expression ${\textstyle {\sqrt[{n}]{A}}{\pmod {p}},}$ then the other values can be found as follows. Let

$$1,r,r^{2}\dots r^{n-1}$$

be the values of the expression ${\textstyle {\sqrt[{n}]{1}}.}$ Then

$$z,zr,zr^{2}\dots zr^{n-1}$$

will be the values of ${\textstyle {\sqrt[{n}]{A}}.}$ For it is clear that all these numbers satisfy the congruence ${\textstyle x^{n}\equiv A.}$ Indeed, if one of them is ${\textstyle \equiv zr^{k}}$, then since ${\textstyle r^{k}\equiv 1}$ and ${\textstyle z^{n}\equiv A,}$ its ${\textstyle n^{th}}$ power ${\textstyle z^{n}r^{nk}}$ will be congruent to ${\textstyle A:}$ from Art. 23 it is easy to see that all these values are distinct; thus the expression ${\textstyle {\sqrt[{n}]{A}}}$ cannot have other values, as it cannot have more than ${\textstyle n.}$ For example, if one value of ${\textstyle {\sqrt[{2}]{A}}}$ is ${\textstyle z,}$ then the other will be ${\textstyle -z.}$ From all of this, it must be concluded that one cannot find all the values of ${\textstyle {\sqrt[{n}]{A}}}$ unless one also has all the values of ${\textstyle {\sqrt[{n}]{1}}.}$

Article 66

The second topic that we had promised to discuss was how to determine when a single value of the expression ${\textstyle {\sqrt[{n}]{A}}{\pmod {p}}}$ (where ${\textstyle n}$ is assumed to be a divisor of ${\textstyle p-1}$) can be found directly. This occurs whenever there is a value congruent to a power of ${\textstyle A,}$ and since this case is very common, it is appropriate to dwell on it briefly. Let ${\textstyle z}$ be this value, if it exists, so that ${\textstyle z\equiv A^{k}}$ and ${\textstyle z^{n}\equiv A{\pmod {p}}.}$ Then we have ${\textstyle A\equiv A^{kn};}$ and if one can determine ${\textstyle k}$ in such a way that this condition is satisfied, then ${\textstyle A^{k}}$ will be the required value; but the previous condition is equivalent to ${\textstyle kn\equiv 1{\pmod {t}},}$ where ${\textstyle t}$ is the exponent to which ${\textstyle A}$ belongs (Art. 46, 48). If ${\textstyle n}$ and ${\textstyle t}$ are relatively prime, then it is possible to solve this congruence, and indeed we will have ${\textstyle k={\frac {1}{n}}{\pmod {t}};}$ on the other hand, if ${\textstyle t}$ and ${\textstyle n}$ have a common divisor, then no value of ${\textstyle z}$ will be congruent to any power of ${\textstyle A.}$

Article 67

Since the above solution requires us to know the number ${\textstyle t,}$ let us see how to proceed when it is not known. First of all, it is easy to see that ${\textstyle t}$ must be a divisor of ${\textstyle {\frac {p-1}{n}},}$ provided that ${\textstyle {\sqrt[{n}]{A}}{\pmod {p}}}$ has real values, which we assume here. Let ${\textstyle y}$ be any of these values. Then we will have ${\textstyle y^{p-1}\equiv 1,}$ and ${\textstyle y^{n}\equiv A{\pmod {p}};}$ raising both parts of the latter congruence to the ${\textstyle {\frac {p-1}{n}}^{th}}$ power, we find that ${\textstyle A^{\frac {p-1}{n}}\equiv 1;}$ therefore ${\textstyle {\frac {p-1}{n}}}$ is divisible by ${\textstyle t}$ (Art. 48). Now if ${\textstyle {\frac {p-1}{n}}}$ is relatively prime to ${\textstyle n,}$ then the congruence ${\textstyle kn\equiv 1}$ can be solved modulo ${\textstyle {\frac {p-1}{n}},}$ and it is clear that any value of ${\textstyle k}$ that satisfies this congruence will satisfy the same congruence modulo ${\textstyle t,}$ this being a divisor of ${\textstyle {\frac {p-1}{n}}}$ (Art. 5), and thus we have found what we were looking for. On the other hand, if ${\textstyle {\frac {p-1}{n}}}$ is not relatively prime to ${\textstyle n,}$ then we first remove all prime factors of ${\textstyle {\frac {p-1}{n}}}$ which also divide ${\textstyle n}$. From this we obtain a number ${\textstyle {\frac {p-1}{nq}},}$ which is relatively prime to ${\textstyle n,}$ where ${\textstyle q}$ denotes the product of the remaining prime factors of ${\textstyle {\frac {p-1}{n}}.}$ Then if the condition that ${\textstyle t}$ is relatively prime to ${\textstyle n}$ holds, ${\textstyle t}$ will also be relatively prime to ${\textstyle q,}$ and therefore it will divide ${\textstyle {\frac {p-1}{nq}}.}$ If we now solve the congruence ${\textstyle kn\equiv 1{\pmod {\frac {p-1}{nq}}}}$ (which is possible because ${\textstyle n}$ and ${\textstyle {\frac {p-1}{nq}}}$ are relatively prime), then the value we find for ${\textstyle k}$ will satisfy the same congruence modulo ${\textstyle t,}$ as required. The art here lies in finding a number that can replace ${\textstyle t,}$ which we do not know. However, we must be mindful of the fact that when ${\textstyle {\frac {p-1}{n}}}$ is not relatively prime to ${\textstyle n,}$ the condition assumed in the previous article is not met, and all of the resulting conclusions are false; and if by blindly following the rules, we find a value for ${\textstyle z}$ whose ${\textstyle n^{th}}$ power is not congruent to ${\textstyle A,}$ this merely shows the condition does not hold, and therefore the method is not applicable.

Article 68

But even in this case, it is often useful to carry out the above procedure, and it is well worth the effort, because the resulting false values may be related to true ones. Indeed, suppose that the numbers ${\textstyle k}$ and ${\textstyle z}$ have been thus determined, but ${\textstyle z^{n}}$ is not ${\textstyle \equiv A{\pmod {p}}.}$ Then if the values of ${\textstyle {\sqrt[{n}]{\frac {A}{z^{n}}}}{\pmod {p}}}$ could be determined, multiplying these different values by ${\textstyle z}$ would give those of ${\textstyle {\sqrt[{n}]{A}}.}$ Indeed, if ${\textstyle \nu }$ is a value of ${\textstyle {\sqrt[{n}]{\frac {A}{z^{n}}}},}$ we will have ${\textstyle \nu ^{n}z^{n}\equiv A;}$ but the expression ${\textstyle {\sqrt[{n}]{\frac {A}{z^{n}}}}}$ is simpler than ${\textstyle {\sqrt[{n}]{A}},}$ because ${\textstyle {\frac {A}{z^{n}}}}$ usually belongs to a smaller exponent than ${\textstyle A.}$ Namely, if ${\textstyle d}$ is the greatest common divisor of ${\textstyle t}$ and ${\textstyle q,}$ then ${\textstyle {\frac {A}{z^{n}}}{\pmod {p}}}$ will belong to the exponent ${\textstyle d,}$ which can be demonstrated as follows. Substituting the value ${\textstyle z\equiv A^{k}}$ gives ${\textstyle {\frac {A}{z^{n}}}\equiv {\frac {1}{A^{kn-1}}}{\pmod {p}};}$ but ${\textstyle kn-1}$ is divisible by ${\textstyle {\frac {p-1}{nq}}}$ (by the previous article), and ${\textstyle {\frac {p-1}{n}}}$ is divisible by ${\textstyle t}$ (ibid.), or equivalently ${\textstyle {\frac {p-1}{nd}}}$ is divisible by ${\textstyle {\frac {t}{d}}.}$ Also, ${\textstyle {\frac {t}{d}}}$ is relatively prime to ${\textstyle {\frac {q}{d}};}$ thus ${\textstyle {\frac {p-1}{nd}}}$ is divisible by ${\textstyle {\frac {tq}{dd}},}$ or equivalently ${\textstyle {\frac {p-1}{nq}}}$ is divisible by ${\textstyle {\frac {t}{d}},}$ and therefore ${\textstyle kn-1}$ is divisible by ${\textstyle {\frac {t}{d}},}$ or equivalently ${\textstyle (kn-1)d}$ is divisible by ${\textstyle t.}$ Thus ${\textstyle A^{(kn-1)d}\equiv 1{\pmod {p}};}$ from which it easily follows that ${\textstyle {\frac {A}{z^{n}}}}$ raised to the ${\textstyle d^{th}}$ power is congruent to unity. It would be easy to show that ${\textstyle {\frac {A}{z^{n}}}}$ cannot belong to an exponent smaller than ${\textstyle d,}$ but since this is not required for our purposes, we will not dwell on it. We are thus certain that ${\textstyle {\frac {A}{z^{n}}}{\pmod {p}}}$ always belongs to a smaller exponent than that of ${\textstyle A,}$ except in the case where ${\textstyle q}$ divides ${\textstyle t}$, and therefore ${\textstyle d=t.}$

Now how does it help, when ${\textstyle {\frac {A}{z^{n}}}}$ belongs to a smaller exponent than ${\textstyle A}$? More numbers are possible for ${\textstyle A}$ than there are for ${\textstyle {\frac {A}{z^{n}}},}$ so when we have occasion to solve many expressions of the form ${\textstyle {\sqrt[{n}]{A}},}$ following the same modulus, we gain the ability to draw several solutions from the same source. So e.g. we can always find at least one value of ${\textstyle {\sqrt[{n}]{A}}{\pmod {29}},}$ given only the values of ${\textstyle {\sqrt[{2}]{-1}}{\pmod {29}},}$ which are ${\textstyle \pm 12.}$ Indeed, it is easy to see, from the previous articles, that we will determine a value directly when ${\textstyle t}$ is odd, and that ${\textstyle d}$ will be ${\textstyle =2}$ when ${\textstyle t}$ is even; but only ${\textstyle -1}$ belongs to the exponent ${\textstyle 2.}$

Examples. Suppose we want to find ${\textstyle {\sqrt[{3}]{31}}{\pmod {37}}.}$ Here we have ${\textstyle p-1=36,}$ ${\textstyle n=3,}$ ${\textstyle {\frac {p-1}{n}}=12,}$ and hence ${\textstyle q=3:}$ so we must have ${\textstyle 3k\equiv 1{\pmod {4}},}$ from which we obtain ${\textstyle k\equiv 3.}$ Therefore ${\textstyle z\equiv 31^{3}\equiv 6{\pmod {37}},}$ and indeed we find that ${\textstyle 6^{3}\equiv 31{\pmod {37}}.}$ Given the values of the expression ${\textstyle {\sqrt[{3}]{1}}{\pmod {37}}}$, we could also determine the remaining values of the expression ${\textstyle {\sqrt[{3}]{31}}.}$ In fact, the values of ${\textstyle {\sqrt[{3}]{1}}{\pmod {37}}}$ are ${\textstyle 1,}$ ${\textstyle 10,}$ ${\textstyle 26;}$ and multiplying these by ${\textstyle 6}$ we obtain ${\textstyle 6,}$ ${\textstyle 23,}$ ${\textstyle 8.}$

Now suppose we want to find the values of expression ${\textstyle {\sqrt[{2}]{3}}{\pmod {37}}.}$ Then we have ${\textstyle p-1=36,}$ ${\textstyle n=2;}$ ${\textstyle {\frac {p-1}{n}}=18,}$ therefore ${\textstyle q=2.}$ Hence we must have ${\textstyle 2k\equiv 1{\pmod {9}},}$ from which we obtain ${\textstyle k\equiv 5.}$ Therefore ${\textstyle z\equiv 3^{5}\equiv 21{\pmod {37}};}$ but ${\textstyle 21^{2}}$ is not congruent to ${\textstyle 3,}$ but rather ${\textstyle 34;}$ so we have ${\textstyle {\frac {3}{34}}{\pmod {37}}\equiv -1}$ and ${\textstyle {\sqrt[{2}]{-1}}{\pmod {37}}\equiv \pm 6;}$ thus we obtain the correct values ${\textstyle \pm 6\cdot 21\equiv \pm 15.}$

This is all we are able to present here on solving these expressions. It is clear that direct methods will often escape from being too verbose; but this inconvenience applies to almost all direct methods in number theory, so we did not wish to neglect to show how much they can achieve here. It is also worth noting that it was not our intention to explain individually the specific techniques that often present themselves to the experienced practitioner.

Article 69

Relationships between indices in different systems.

We now return to the roots we have called primitive. We have shown that, if we take an arbitrary primitive root as a base, then all numbers whose indices are relatively prime to ${\textstyle p-1}$ will also be primitive roots, and that there are no others: from this we have deduced the number of such roots. See Art. 53. Since the choice of the base we take is generally arbitrary, we see that here, as with logarithms, we can have many different systems.^[2] Let us look for the relations that link them together. Let ${\textstyle a}$ and ${\textstyle b}$ be two primitive roots, and ${\textstyle m}$ another number. Suppose that the index of ${\textstyle b}$ is ${\textstyle =\beta }$ and the index of ${\textstyle m}$ is ${\textstyle \equiv \mu {\pmod {p-1}}}$ when ${\textstyle a}$ is taken as base. On the other hand, let ${\textstyle \operatorname {Ind.} a\equiv \alpha {\pmod {p-1}}}$ and ${\textstyle \operatorname {Ind.} m\equiv \nu {\pmod {p-1}}}$ when ${\textstyle b}$ is taken as the base. Then we will have ${\textstyle \alpha \beta \equiv 1{\pmod {p-1}};}$ indeed ${\textstyle a^{\beta }\equiv b,}$ so ${\textstyle a^{\alpha \beta }\equiv b^{\alpha }\equiv a{\pmod {p}}}$ (by hypothesis), hence ${\textstyle \alpha \beta \equiv 1{\pmod {p-1}}.}$ By similar reasoning, we find that ${\textstyle \nu \equiv \alpha }$ and ${\textstyle \mu \equiv \beta \nu {\pmod {p-1}}.}$ Therefore, if we have created an index table for the base ${\textstyle a,}$ we can easily change it to another one with base ${\textstyle b.}$ Indeed, if the index of ${\textstyle b}$ is ${\textstyle \equiv \beta }$ for the base ${\textstyle a}$, then the index of ${\textstyle a}$ will be ${\textstyle \equiv {\frac {1}{\beta }}{\pmod {p-1}}}$ for the base ${\textstyle b,}$ and by multiplying all of the indices in the table by this number, we will have all the indices for the base ${\textstyle b.}$

Article 70

However, although a given number may have many different indices, depending on which primitive root is taken as the base, all of these indices will have a common property, that their greatest common divisor with ${\textstyle p-1}$ is the same. In fact, if the index of a given number is ${\textstyle m}$ for the base ${\textstyle a}$ and ${\textstyle n}$ for base ${\textstyle b,}$ and if the greatest common divisors ${\textstyle \mu ,}$ ${\textstyle \nu }$ of these indices with ${\textstyle p-1}$ are assumed to be different, e.g. ${\textstyle \mu >\nu ,}$ then ${\textstyle \mu }$ will not divide ${\textstyle n.}$ On the other hand, if ${\textstyle \alpha }$ denotes the index of ${\textstyle a}$ for the base ${\textstyle b,}$ then we will have (by the previous article) ${\textstyle n\equiv \alpha m{\pmod {p-1}},}$ and hence ${\textstyle \mu }$ will divide ${\textstyle n.}$ Q.E.A.

We can also show that this common divisor of the indices of a given number and ${\textstyle p-1}$ is independent of the base by observing that it is equal to ${\textstyle {\frac {p-1}{t}},}$ where ${\textstyle t}$ is the exponent to which the number belongs. Indeed, if the index is ${\textstyle k}$ for any base, then as we saw in Arts. 48, 58, ${\textstyle t}$ will be the smallest number (excluding zero), that when multiplied by ${\textstyle k,}$ gives a product divisible by ${\textstyle p-1,}$ or equivalently it will be the smallest value of the expression ${\textstyle {\frac {0}{k}}{\pmod {p-1}}}$ except for zero; but it is easy to deduce from Art. 29 that this value is the greatest common divisor of the numbers ${\textstyle k}$ and ${\textstyle p-1.}$

Article 71

It is easy to show that one can always find a base such that a number belonging to the exponent ${\textstyle t}$ has a given index, as long as the greatest common divisor of this index and ${\textstyle p-1}$ is ${\textstyle ={\frac {p-1}{t}}.}$ For the sake brevity, denote this divisor by ${\textstyle d,}$ let the index be ${\textstyle \equiv dm,}$ and let ${\textstyle dn}$ be the index of the given number when some primitive root ${\textstyle a}$ is chosen as the base. Then ${\textstyle m}$ and ${\textstyle n}$ will be relatively prime to ${\textstyle {\frac {p-1}{d}}}$, i.e. to ${\textstyle t.}$ Now if ${\textstyle \varepsilon }$ is a value of the expression ${\textstyle {\frac {dn}{dm}}{\pmod {p-1}},}$ which is also relatively prime to ${\textstyle p-1,}$ then ${\textstyle a^{\varepsilon }}$ will be the desired primitive root, because we will have ${\textstyle a^{\varepsilon dm}\equiv a^{dn}\equiv }$ the proposed number ${\textstyle {\pmod {p}},}$ as desired. But it can be shown that the expression ${\textstyle {\frac {dn}{dm}}{\pmod {p-1}}}$ admits arbitrary values coprime to ${\textstyle p-1.}$ Indeed, it is equivalent to ${\textstyle {\frac {n}{m}}{\pmod {\frac {p-1}{d}}}}$ or ${\textstyle {\frac {n}{m}}{\pmod {t}},}$ as we saw in Arts. 2, 31, and all such values will be coprime with ${\textstyle t;}$ for if one such value ${\textstyle e}$ had a common divisor with ${\textstyle t,}$ this divisor would also have to divide ${\textstyle me,}$ and consequently it would divide ${\textstyle n,}$ which is congruent to ${\textstyle me}$ modulo ${\textstyle t,}$ contrary to the hypothesis that ${\textstyle n}$ is relatively prime to ${\textstyle t.}$ Thus, when all the prime divisors of ${\textstyle p-1}$ also divide ${\textstyle t,}$ all values of the expression ${\textstyle {\frac {n}{m}}{\pmod {t}}}$ will be relatively prime to ${\textstyle p-1,}$ and their multitude will be ${\textstyle =d;}$ but when ${\textstyle p-1}$ still contains other prime factors ${\textstyle f,}$ ${\textstyle g,}$ ${\textstyle h}$ etc. which do not divide ${\textstyle t,}$ let ${\textstyle e}$ be an arbitrary value of ${\textstyle {\frac {n}{m}}{\pmod {t}}.}$ Then since ${\textstyle t,}$ ${\textstyle f,}$ ${\textstyle g,}$ ${\textstyle h}$etc. are mutually relatively prime, one can find a number ${\textstyle \varepsilon ,}$ which is congruent to ${\textstyle e}$ modulo ${\textstyle t,}$ and which is congruent modulo ${\textstyle f,}$ ${\textstyle g,}$ ${\textstyle h}$ etc. to arbitrary given numbers that are relatively prime to the corresponding modulus (Art. 32). Such a number will not be divisible by any factor of ${\textstyle p-1,}$ and thus will be relativley prime with it, as required. It can be easily shown from the theory of combinations that the number of these values is ${\textstyle {\frac {p-1}{t}}\cdot {\frac {f-1}{f}}\cdot {\frac {g-1}{g}}\cdot {\frac {h-1}{h}}}$etc.; but we omit this demonstration, which will not be necessary for us.

Article 72

Bases adapted to particular purposes.

Although in general one can arbitrarily choose any primitive root as a base, certain particular advantages may make one base preferred over another. In Table I we have always taken ${\textstyle 10}$ as the base when it was a primitive root, and in other cases we have chosen the base in such a way that the index of the number ${\textstyle 10}$ was as small as possible, i.e. so that it would be ${\textstyle ={\frac {p-1}{t}},}$ where ${\textstyle t}$ is the exponent to which ${\textstyle 10}$ belongs. The advantage of this will be recognized in Sect. VI, where the same table will be used for other purposes. But since this still leaves a degree of arbitrariness, as we saw in the previous article, we have always chosen, among all primitive roots that satisfy this requirement, the smallest one as the base. So, for ${\textstyle p=73,}$ we have ${\textstyle t=8,}$ ${\textstyle d=9,}$ and ${\textstyle a^{\varepsilon }}$ has ${\textstyle {\frac {72.2}{8.3}},}$ i.e. 6 values, which are ${\textstyle 5,}$ ${\textstyle 14,}$ ${\textstyle 20,}$ ${\textstyle 28,}$ ${\textstyle 39,}$ ${\textstyle 40.}$ We have therefore chosen ${\textstyle 5}$ to be the base.

Article 73

Method for finding primitive roots.

Most of the methods used to find primitive roots rely largely on trial and error. If we combine what we have said in Art. 55 with what we will say below about solving the congruence ${\textstyle x^{n}\equiv 1,}$ then we will have almost everything that can be done using general methods. Euler admits (Opuscula analyt. T. i, p. 152.) that it seems extremely difficult to determine these numbers, and that their nature must be considered as one of the most thorny points of number theory. However, they can be found quite easily using the following method. Experienced individuals can easily shorten the calculation by using various tricks; but these are better learned by practice than by rules.

1^st. Choose an arbitrary number ${\textstyle a,}$ (often the calculation becomes simpler when one chooses ${\textstyle a}$ as small as possible, e.g. ${\textstyle 2;}$) which is relatively prime to the given modulus ${\textstyle p}$ (we will always denote the modulus with this letter), and determine its period (Art. 46), i.e. the minimal residues of its powers up to the first power ${\textstyle a^{t}}$ which has ${\textstyle 1}$ as its minimal residue.^[3] If ${\textstyle t=p-1,}$ then ${\textstyle a}$ is a primitive root.

2^nd. On the other hand, if ${\textstyle t<p-1,}$ one can choose another number ${\textstyle b}$ that is not in the period of ${\textstyle a,}$ and determine its period in exactly the same way. Letting ${\textstyle u}$ denote the exponent to which ${\textstyle b}$ belongs, it is easy to see that ${\textstyle u}$ is neither equal to ${\textstyle t,}$ nor one of its aliquot parts, for in both cases we would have ${\textstyle b^{t}\equiv 1,}$ which is impossible, since the period of ${\textstyle a}$ contains all numbers whose ${\textstyle t^{th}}$ power is congruent to unity (Art. 53). Now, if ${\textstyle u}$ is ${\textstyle =p-1,}$ then ${\textstyle b}$ will be a primitive root; but if ${\textstyle u}$ is not ${\textstyle =p-1,}$ but instead a multiple of ${\textstyle t,}$ then we still have the advantage of knowing a number that belongs to a larger exponent, and thus we are closer to our goal, since we are looking for the number that belongs to the maximum exponent. Finally, if ${\textstyle u}$ is neither ${\textstyle =p-1,}$ nor a multiple of ${\textstyle t,}$ we can find a number belonging to an exponent larger than ${\textstyle t}$ and ${\textstyle u;}$ namely, this exponent will be the least common multiple of ${\textstyle t}$ and ${\textstyle u.}$ Indeed, letting this ${\textstyle =y,}$ we can decompose ${\textstyle y}$ into two relatively prime factors ${\textstyle m}$ and ${\textstyle n}$, with the former dividing ${\textstyle t}$ and the latter dividing ${\textstyle u}$ ^[4]. If we set ${\textstyle a^{\frac {\epsilon }{m}}\equiv A}$ and ${\textstyle b^{\frac {u}{n}}\equiv B{\pmod {p}},}$ then ${\textstyle AB}$ will belong to the exponent ${\textstyle y;}$ it is easy to see that ${\textstyle A}$ belongs to the exponent ${\textstyle m}$ and ${\textstyle B}$ to the exponent ${\textstyle n,}$ and therefore the product ${\textstyle AB}$ will belong to the exponent ${\textstyle mn,}$ since ${\textstyle m}$ and ${\textstyle n}$ are relatively prime, as can be demonstrated by following exactly the procedure of Art. 55, II.

3^rd. If ${\textstyle y=p-1,}$ then ${\textstyle AB}$ will be a primitive root; otherwise one can similarly find a third number which does not appear in the period of ${\textstyle AB;}$ this number will either be a primitive root, or it will belong to an exponent ${\textstyle >y,}$ or finally, it can be used to determine a number belonging to an exponent ${\textstyle >y.}$ Since the numbers produced by repeating this operation belong to exponents which are always increasing, it is clear that one will eventually find a number that belongs to the maximum exponent ${\textstyle p-1,}$ i.e. a primitive root, q.e.f.

Article 74

Let us clarify the above with an example. Let ${\textstyle p=73}$ for which we seek a primitive root. Let us first try the number ${\textstyle 2,}$ whose period is

$${\begin{matrix}1&2&4&8&16&32&64&55&37&1&\dots \\0&1&2&3&4&5&6&7&8&9&\dots \end{matrix}}$$

Therefore, since its ${\textstyle 9^{th}}$ power is congruent to unity, ${\textstyle 2}$ is not a primitive root. Let us try another number, which is not in the period of ${\textstyle 2,}$ e.g. ${\textstyle 3,}$ whose period is

$${\begin{matrix}1&3&9&27&8&24&72&70&64&46&65&49&1&\dots \\0&1&2&3&4&5&6&7&8&9&10&11&12&\dots \end{matrix}}$$

So ${\textstyle 3}$ is also not a primitive root; but the least common multiple of the exponents to which ${\textstyle 2}$ and ${\textstyle 5}$ belong (i.e. the numbers ${\textstyle 9}$ and ${\textstyle 12}$), is ${\textstyle 36,}$ which can then be resolved into factors ${\textstyle m=9}$ and ${\textstyle n=4,}$ according to the rules from the previous article. Therefore, raising ${\textstyle 2}$ to the power ${\textstyle {\frac {9}{9}}=1,}$ raising ${\textstyle 3}$ to the power ${\textstyle {\frac {12}{4}}=3,}$ and taking the product, we obtain of ${\textstyle 54,}$ which will belong to the exponent ${\textstyle 36.}$ Finally, if we calculate the period of ${\textstyle 54}$ and try a number not contained in it, e.g. ${\textstyle 5,}$ we find that it is a primitive root.

Article 75

Various theorems on periods and primitive roots.

Before leaving this subject, we will present some propositions that do not seem unworthy of attention due to their simplicity.

The product of all terms in the period of any number is ${\textstyle \equiv 1}$ when their multitude, or the exponent to which the number in question belongs, is odd, and ${\textstyle \equiv -1}$ when the exponent is even.

Ex. For the modulus ${\textstyle 13,}$ the period of ${\textstyle 5}$ is composed of the terms ${\textstyle 1,}$ ${\textstyle 5,}$ ${\textstyle 12,}$ ${\textstyle 8,}$ whose product ${\textstyle 480\equiv -1{\pmod {13}}.}$

For the same modulus, the period of ${\textstyle 3}$ is composed of the terms ${\textstyle 1,}$ ${\textstyle 3,}$ ${\textstyle 9,}$ whose product ${\textstyle 27\equiv 1{\pmod {13}}.}$

Proof. Letting ${\textstyle t}$ be the exponent to which the number belongs, we can always find (Art.71) a base for which the index of the number is ${\textstyle {\frac {p-1}{t}}.}$ The index of the product of all the terms will be

$$\equiv (1+2+3+{\text{etc.}}+t-1){\frac {p-1}{t}}={\frac {(t-1)(p-1)}{2}}$$

i.e. ${\textstyle \equiv 0{\pmod {p-1}},}$ when ${\textstyle t}$ is odd; and ${\textstyle \equiv {\frac {p-1}{2}},}$ when ${\textstyle t}$ is even; hence in the first case, the product is ${\textstyle \equiv 1{\pmod {p}};}$ but in the second it is ${\textstyle \equiv -1{\pmod {p}}.}$ Q.E.D.

Article 76

If the number in the previous theorem is a primitive root, then its period will include all of the numbers ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3\dots p-1,}$ whose product will therefore always be ${\textstyle \equiv -1}$ (for ${\textstyle p-1}$ is always even, except when ${\textstyle p=2,}$ in which case ${\textstyle +1}$ and ${\textstyle -1}$ are equivalent. This elegant theorem, which is usually stated in the following way: The product of all numbers smaller than a prime number, increased by unity, is divisible by this prime number, was published by Waring who attributes it to Wilson Meditationes algeb. Ed. 3, p. 380. Yet neither of them could prove it, and Waring admits that the proof seems to him all the more difficult as there is no notation in which a prime number can be expressed. As for us, we believe that the proofs of these kinds of truths must be drawn from principles rather than from notation. Lagrange subsequently provided a proof, Nouv. Mém. de l’Ac. de Berlin, 1771. It is based on considering of the coefficients that are found by expanding the product

$$x+1.x+2.x+3\dots x+p-1$$

Namely, he shows that by setting this product

$$=x^{p-1}+x^{p-2}+x^{p-3}+\dots +Mx+N,$$

the coefficients ${\textstyle A,}$ ${\textstyle B}$ etc., ${\textstyle M}$ are divisible by ${\textstyle p;}$ and therefore ${\textstyle N=1.2.3\dots p-1.}$ Now, for ${\textstyle x=1,}$ the product is divisible by ${\textstyle p;}$ but then it will be ${\textstyle \equiv 1+N{\pmod {p}};}$ therefore ${\textstyle 1+N}$ must necessarily be divisible by ${\textstyle p.}$

Finally Euler (Opusc. analyt. T. i, p. 529) provided a proof that is similar to the one we have just explained. Since such men judged this theorem not unworthy of their reflections, we hope it will not meet with disapproval if we add yet another demonstration.

Article 77

When the product of two numbers ${\textstyle a,}$ ${\textstyle b}$ is congruent to unity modulo ${\textstyle p,}$ we will say that ${\textstyle a,}$ ${\textstyle b}$ are associated, as did Euler. Then by the preceding section, every positive number less than ${\textstyle p}$ will always have one and only one associated number that is positive and less than ${\textstyle p.}$ Now, it is easy to prove that among the numbers ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3\dots p-1,}$ only ${\textstyle 1}$ and ${\textstyle p-1}$ are associated with themselves, because those that enjoy this property will be given by the congruence ${\textstyle xx\equiv 1,}$ which is of the second degree and can therefore only have two roots, i.e. apart from ${\textstyle 1}$ and ${\textstyle p-1}$ we can have no others. Therefore, upon removing these, the remaining numbers ${\textstyle 2,}$ ${\textstyle 3\dots p-2}$ will be associated in pairs; thus their product will be ${\textstyle \equiv 1,}$ and therefore the product of all the numbers${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3\dots p-1}$ will be ${\textstyle \equiv p-1,}$ or ${\textstyle \equiv -1.}$ Q.E.D.

E.g. for ${\textstyle p=13,}$ the numbers ${\textstyle 2,}$ ${\textstyle 3,}$ ${\textstyle 4\dots 11}$ are associated as follows: ${\textstyle 2}$ with ${\textstyle 7;}$ ${\textstyle 3}$ with ${\textstyle 9;}$ ${\textstyle 4}$ with ${\textstyle 10;}$ ${\textstyle 5}$ with ${\textstyle 8;}$ ${\textstyle 6}$ with ${\textstyle 11;}$ so that ${\textstyle 2.7\equiv 1;}$ ${\textstyle 3.9\equiv 1}$ etc. Hence ${\textstyle 2\cdot 3\cdot 4\dots 11\equiv 1;}$ therefore ${\textstyle 1\cdot 2\cdot 3\dots 12\equiv 12\equiv -1.}$

Article 78

Wilson's theorem can be made more general by stating it as follows: The product of all numbers less than and relatively prime to a given number ${\textstyle A}$ is congruent, modulo ${\textstyle A,}$ to a positive or negative unit. The unit should be taken negatively when ${\textstyle A}$ is of the form ${\textstyle p^{m}}$ or ${\textstyle 2p^{m},}$ where ${\textstyle p}$ is a prime number different from ${\textstyle 2,}$ or when ${\textstyle A=4;}$ in all other cases it should be taken positively. Wilson’s theorem falls within the first case. E.g. For ${\textstyle A=15,}$ the product of the numbers ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 4,}$ ${\textstyle 7,}$ ${\textstyle 8,}$ ${\textstyle 11,}$ ${\textstyle 13,}$ ${\textstyle 14}$ is ${\textstyle \equiv 1{\pmod {15}}.}$ For the sake of brevity,we omit the the demonstration: we merely observe that we can achieve it in the same way as in the previous article, except that the congruence ${\textstyle x^{2}\equiv 1}$ can have more than two roots, which requires certain particular considerations. One could also derive it from the consideration of indices, as in Art. 75, in combination with that which we will say shortly about composite moduli.

Article 79

Let us return to the enumeration of the other propositions (Art. 75).

The sum of all terms in the period of any number is ${\textstyle \equiv 0,}$ as in the example of article 75,

$$1+5+12+8=26\equiv 0{\pmod {13}}.$$

Proof. Let ${\textstyle a}$ be the number in question, and let ${\textstyle t}$ be the exponent to which it belongs. The sum of all terms in the period will be

$$\equiv 1+a+a^{2}+a^{3}+\dots +a^{t-1}\equiv {\frac {a^{t}-1}{a-1}}{\pmod {p}}$$

However, ${\textstyle a^{t}-1\equiv 0:}$ thus the sum must be ${\textstyle \equiv 0}$ (Art. 22) if ${\textstyle a-1}$ is not divisible by ${\textstyle p,}$ or ${\textstyle a\equiv 1;}$ thus we must exclude this case if we wish to call even a single term a period.

Article 80

The product of all primitive roots is ${\textstyle \equiv 1}$ unless ${\textstyle p=3;}$ because in this case there is only one primitive root, ${\textstyle 2.}$

Proof. If we take an arbitrary primitive root as a base, then the indices of all primitive roots will be numbers less than and relatively prime to ${\textstyle p-1.}$ However, the sum of all these numbers, i.e. the index of the product of all primitive roots, is ${\textstyle \equiv 0{\pmod {p-1}},}$ and therefore the product is ${\textstyle \equiv 1{\pmod {p}};}$ it is easy to see that if ${\textstyle k}$ is a number relatively prime to ${\textstyle p-1,}$ then ${\textstyle p-1-k}$ will also be relatively prime to ${\textstyle p-1,}$ and therefore the sum of the numbers relatively prime to ${\textstyle p-1}$ is composed of pairs whose sum is divisible by ${\textstyle p-1.}$ (but ${\textstyle k}$ can never be equal to ${\textstyle p-1-k,}$ except in the case ${\textstyle p-1=2,}$ or ${\textstyle p=3,}$ which we excluded; for it is clear that in all other cases ${\textstyle {\frac {p-1}{2}}}$ is not relatively prime to ${\textstyle p-1}$.

Article 81

The sum of all primitive roots is ${\textstyle \equiv 0}$ (when ${\textstyle p-1}$ is divisible by a square), or ${\textstyle \equiv \pm 1,}$ (when ${\textstyle p-1}$ is the product of distinct prime factors; the sign is positive when the number of factors is even, and it is negative when the number of factors is odd).

Ex 1. For ${\textstyle p=13,}$ the primitive roots are ${\textstyle 2,}$ ${\textstyle 6,}$ ${\textstyle 7,}$ ${\textstyle 11,}$ and their sum is ${\textstyle 26\equiv 0{\pmod {13}}.}$

Ex 2. For ${\textstyle p=11,}$ the primitive roots are ${\textstyle 2,}$ ${\textstyle 6,}$ ${\textstyle 7,}$ ${\textstyle 8,}$ and their sum is ${\textstyle 23\equiv +1{\pmod {11}}.}$

Ex 3. For ${\textstyle p=31,}$ the primitive roots are ${\textstyle 5,}$ ${\textstyle 11,}$ ${\textstyle 12,}$ ${\textstyle 13,}$ ${\textstyle 17,}$ ${\textstyle 21,}$ ${\textstyle 22,}$ ${\textstyle 24,}$ and their sum is ${\textstyle 123\equiv -1{\pmod {31}}.}$

We have shown earlier (Art. 55, II) that if ${\textstyle p-1}$ is ${\textstyle =a^{\alpha }b^{\beta }c^{\gamma }}$etc. (where ${\textstyle =a,}$ ${\textstyle =b,}$ ${\textstyle =c}$ etc. are distinct prime numbers), and ${\textstyle A,}$ ${\textstyle B,}$ ${\textstyle C}$ etc. are arbitrary numbers that belong to the exponents ${\textstyle a^{\alpha },}$ ${\textstyle b^{\beta },}$ ${\textstyle c^{\gamma }}$ etc., then all products ${\textstyle ABC}$etc. will be primitive roots. However, it is easy to show that any primitive root can only be expressed in one way as a product of this form.^[5]

It follows from this that the primitive roots can be replaced with products of this form; but in these products we must combine all values of ${\textstyle A}$ with all those of ${\textstyle B}$etc. So, by the theory of combinations, the sum of all such products will be equal to the product of the sum of all values of ${\textstyle A,}$ the sum of the values of ${\textstyle B,}$ the sum of the values of ${\textstyle C}$ etc. Denoting the values of ${\textstyle A}$ by ${\textstyle A,}$ ${\textstyle A',}$ ${\textstyle A''}$etc., and the values of ${\textstyle B}$ by ${\textstyle B,}$ ${\textstyle B',}$ ${\textstyle B''}$etc. etc., it follows that the sum of all primitive roots will be

$$(A+A'+{\text{etc.}})(B+B'+{\text{etc.}}){\text{etc.}}$$

Now I say that if ${\textstyle \alpha =1,}$ the sum ${\textstyle A+A'+A''+}$etc. will be ${\textstyle \equiv -1{\pmod {p}},}$ and if ${\textstyle \alpha >1,}$ this sum will be ${\textstyle \equiv 0,}$ and likewise for ${\textstyle \beta ,}$ ${\textstyle \gamma }$etc., If these two assertions are proved, then the truth of the theorem will be evident. Indeed, when ${\textstyle p-1}$ is divisible by a square, one of the exponents ${\textstyle \alpha ,}$ ${\textstyle \beta ,}$ ${\textstyle \gamma }$ etc., will be greater than unity, hence one of the factors, whose product is congruent to the sum of primitive roots, will be ${\textstyle \equiv 0,}$ and thus so will be the product itself: but when ${\textstyle p-1}$ is not divisible by any square, all of the exponents ${\textstyle \alpha ,}$ ${\textstyle \beta ,}$ ${\textstyle \gamma }$etc., will be equal to one, so the sum of the primitive roots will be congruent to the product of as many factors ${\textstyle \equiv -1,}$ as there are numbers ${\textstyle a,}$ ${\textstyle b,}$ ${\textstyle c}$etc., and therefore the product will be ${\textstyle \equiv \pm 1,}$ depending on whether the number of such factors is even or odd. This can be shown as follows:

1^st. When ${\textstyle \alpha =1,}$ and ${\textstyle A}$ is a number belonging to the exponent ${\textstyle a,}$ the remaining numbers belonging to the same exponent will be ${\textstyle A^{2},}$ ${\textstyle A^{3}\dots A^{a-1};}$ But

$$1+A+A^{2}+A^{3}+A^{4}+\dots A^{a-1}$$

is the sum of a complete period, and therefore is ${\textstyle \equiv 0}$ (Art. 79), and thus

$$A+A^{2}+A^{3}+A^{4}+\dots A^{a-1}\equiv -1.$$

2^nd. When ${\textstyle \alpha >1,}$ and ${\textstyle A}$ is a number belonging to the exponent ${\textstyle a^{\alpha },}$ the remaining numbers belonging to the same exponent are obtained by removing ${\textstyle A^{a},}$ ${\textstyle A^{2a},}$ ${\textstyle A^{3a}}$ etc. from the sequence ${\textstyle A^{2},}$ ${\textstyle A^{3},}$ ${\textstyle A^{4},}$ ${\textstyle }$etc. ${\textstyle A^{a^{\alpha }-1},}$ see Art. 53. Thus their sum will be

$$\equiv 1+A+A^{2}+\dots +A^{a^{\alpha }-1}-(1+A^{a}+A^{2a}+\dots +A^{a^{\alpha }-a})$$

i.e. it will be congruent to the difference of two periods, and therefore ${\textstyle \equiv 0.}$ Q.E.D.

Article 82

On moduli which are prime powers.

All that we have explained so far assumes that the modulus is a prime number. We still need to consider the case where we take a composite number as the modulus. However, there are not as many elegant properties in this case as in the first one, and there is no need for very delicate devices to find them, as everything is deduced almost solely from the application of the previous principles, so it would be superfluous and tedious to exhaust all the details here. Therefore, we will briefly explain what this second case has in common with the first, and what distinguishes it.

Article 83

The propositions of Arts. 45–48 have already been proved in general, but the one in Art. 49 must be modified as follows:

If ${\textstyle f}$ denotes the number of integers less than and relatively prime to ${\textstyle m}$, i.e., if ${\textstyle f=\phi m}$ (Art. 38), and ${\textstyle a}$ is a given number which is relatively prime to ${\textstyle m,}$ then the smallest exponent ${\textstyle t}$ such that ${\textstyle a^{t}}$ is congruent to unity modulo ${\textstyle m}$ will be ${\textstyle =f,}$ or an aliquot part of ${\textstyle f.}$

The proof of the proposition in Art. 49 can also be applied in this case, by substituting ${\textstyle m}$ for ${\textstyle p}$ and ${\textstyle f}$ for ${\textstyle p-1,}$ and instead of the numbers ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 3,}$ ${\textstyle \dots p-1,}$ the numbers relatively prime to ${\textstyle m}$ and less than it. We leave this to the reader. But the other proofs we have mentioned (Arts. 50, 51), can only be applied in this case after many modifications. As for the following propositions (Art. 52 and onwards), there is a great difference between moduli that are powers of a prime number and those that are divisible by several prime numbers. Therefore, we will separately consider moduli of the first type.

Article 84

If the modulus is ${\textstyle m=p^{\alpha },}$ where ${\textstyle p}$ is a prime number, then we have ${\textstyle f=p^{\alpha -1}(p-1),}$ (Art. 38). Now, if we apply the investigations of Arts. 53, 54 in this case, mutatis mutandis as in the previous article, we find that everything that has been shown there would also hold if it could be shown that the congruence ${\textstyle x^{t}-1\equiv 0{\pmod {p^{n}}}}$ does not have more than ${\textstyle t}$ different roots. It is from a more general proposition (Art. 43) that we deduced this truth for a prime modulus, but this proposition only holds for prime modules, and therefore cannot be applied to this case. We will therefore prove it by a more specialized method. Later (Sect. VIII) we will prove it even more easily.

Article 85

We aim to prove the following theorem:

If the greatest common divisor of the numbers ${\textstyle t}$ and ${\textstyle p^{n-1}(p-1)}$ is ${\textstyle e,}$ then the congruence ${\textstyle x^{t}\equiv 1{\pmod {p^{n}}}}$ will have ${\textstyle e}$ distinct roots.

Let ${\textstyle e=kp^{\nu },}$ where ${\textstyle k}$ is not divisible by ${\textstyle p,}$ and therefore divides ${\textstyle p-1.}$ Then the congruence ${\textstyle x^{t}\equiv 1}$ will have ${\textstyle k}$ distinct roots modulo ${\textstyle p,}$ and if these are denoted by ${\textstyle A,}$ ${\textstyle B,}$ ${\textstyle C}$ etc., then any root of this same congruence modulo ${\textstyle p^{n}}$ must be congruent to one of the numbers ${\textstyle A,}$ ${\textstyle B,}$ ${\textstyle C}$ etc. modulo ${\textstyle p.}$ We will prove that the congruence ${\textstyle x^{t}\equiv 1{\pmod {p^{n}}}}$ has ${\textstyle p^{\nu }}$ roots congruent to ${\textstyle A,}$ just as many congruent to ${\textstyle B}$ etc. modulo ${\textstyle p.}$ Thus the total number of roots will be ${\textstyle kp^{\nu }}$ or ${\textstyle e,}$ as we claimed. To carry this out, we will show that first, if ${\textstyle \alpha }$ is a root congruent to ${\textstyle A}$ modulo ${\textstyle p,}$ then

$$\alpha +p^{n-\nu },\alpha +2p^{n-\nu },\alpha +3p^{n-\nu },\dots \alpha +p^{\nu -1}p^{n-\nu },$$

will also be roots; and second, no number congruent to ${\textstyle A}$ can be a root, unless it is of the form ${\textstyle \alpha +hp^{n-\nu }}$ (where ${\textstyle h}$ is an integer); hence there will clearly be ${\textstyle p}$ distinct roots, and no more; the same thing will happen with respect to ${\textstyle B,}$ ${\textstyle C}$ etc.; and third, we will show how one can always find a root congruent to ${\textstyle A}$ modulo ${\textstyle p.}$

Article 86

Theorem. If, as in the preceding article, ${\textstyle t}$ is a number divisible by ${\textstyle p^{\nu }}$ and not by ${\textstyle p^{\nu +1},}$ then

$$(\alpha +hp^{\mu })^{t}-\alpha ^{t}\equiv 0{\pmod {p^{\mu +\nu }}},{\text{ and }}\equiv \alpha ^{t-1}hp^{\mu }t{\pmod {p^{\mu +\nu +1}}}.$$

The second part of the theorem does not hold when ${\textstyle p=2}$ and ${\textstyle \mu =1.}$

We could deduce this theorem from the binomial formula, if we were to show that all terms, after the second, are divisible by ${\textstyle p^{\mu +\nu +1};}$ but since considering the denominators of the coefficients leads to some confusion, we prefer the following method.

We assume first that ${\textstyle \mu >1}$ and ${\textstyle \nu =1.}$ Then because

$$x^{t}-y^{t}=(x-y)(x^{t-1}+x^{t-2}y+x^{t-3}y^{2}+{\text{etc.}}+y^{t-1})$$

we have

$$(\alpha +hp^{\mu })^{t}-\alpha ^{t}=hp^{\mu }\{(\alpha +hp^{\mu })^{t-1}+(\alpha +hp^{\mu })^{t-2}\alpha +{\text{etc.}}+\alpha ^{t-1}\};$$

But

$$\alpha +hp^{\mu }\equiv \alpha {\pmod {p^{2}}}$$

and therefore each term ${\textstyle (\alpha +hp^{\mu })^{t-1},}$ ${\textstyle (\alpha +hp^{\mu })^{t-2}\alpha }$ etc., will be ${\textstyle \equiv \alpha ^{t-1}{\pmod {p^{2}}},}$ and therefore the sum of all terms will be ${\textstyle \equiv t\alpha ^{t-1}{\pmod {p^{2}}},}$ or equivalently this sum will be of the form ${\textstyle t\alpha ^{t-1}+Vp^{2},}$ for some number ${\textstyle V}$. Hence ${\textstyle (\alpha +hp^{\mu })^{t}-\alpha ^{t}}$ will be of the form

$$\alpha ^{t-1}hp^{\nu },{\text{ i.e. }}\equiv \alpha ^{t-1}hp^{\mu }t{\pmod {p^{\mu +2}}}{\text{ and }}\equiv 0{\pmod {p^{\mu +1}}}.$$

For this case, the theorem is proved.

If the theorem were not true for the other values of ${\textstyle \nu ,}$ with ${\textstyle \mu }$ still being ${\textstyle >1,}$ then there would necessarily be a limit up to which the theorem would be true, and beyond which it would be false. Let ${\textstyle \varphi }$ be the smallest value of ${\textstyle \nu }$ for which the theorem is false. It is easy to see that the theorem is true if ${\textstyle t}$ is divisible by ${\textstyle p^{\varphi -1}}$ and not by ${\textstyle p^{\varphi },}$ but if ${\textstyle tp}$ is substituted for ${\textstyle t,}$ it is no longer true. Therefore, we have

$$(\alpha +hp^{\nu })^{t}\equiv \alpha ^{t}+\alpha ^{t-1}hp^{\mu }t{\pmod {p^{\mu +\varphi }}},{\text{ or }}=\alpha ^{t}+\alpha ^{t-1}hp^{\mu }t+up^{\mu +\varphi },$$

for some integer ${\textstyle u}$; but since the theorem is already proven for ${\textstyle \nu =1,}$ we will have

$$\left(\alpha ^{t}+\alpha ^{t-1}hp^{\mu }t+up^{\mu +\varphi }\right)^{p}\equiv \alpha ^{tp}+\alpha ^{tp-1}hp^{\mu +1}t+\alpha ^{tp-1}up^{\mu +\varphi +1}{\pmod {p^{\mu +\varphi +1}}}$$

and hence

$$(\alpha +hp^{\mu })^{tp}\equiv \alpha ^{tp}+\alpha ^{tp-1}hp^{\mu }tp{\pmod {p^{\mu +\varphi +1}}}$$

i.e. the theorem is still true if we substitute ${\textstyle tp}$ in place of ${\textstyle t}$ or ${\textstyle \varphi +1}$ instead of ${\textstyle \varphi ,}$ contradicting the assumption. Thus the theorem is true for all values of ${\textstyle \nu .}$

Article 87

The case where ${\textstyle \mu =1}$ remains. By a method precisely similar to that of the previous article, we will prove, without using the binomial theorem, that

$${\begin{aligned}(\alpha +hp)^{t-1}&\equiv \alpha ^{t-1}+\alpha ^{t-2}(t-1)hp{\pmod {p^{2}}}\\\alpha (\alpha +hp)^{t-2}&\equiv \alpha ^{t-1}+\alpha ^{t-2}(t-2)hp\\\alpha ^{2}(\alpha +hp)^{t-3}&\equiv \alpha ^{t-1}+\alpha ^{t-2}(t-3)hp\\{\text{etc.}}&\end{aligned}}$$

and therefore (since the number of terms is ${\textstyle t}$)

$$\equiv t\alpha ^{t-1}+{\frac {(t-1)t}{2}}\alpha ^{t-2}hp{\pmod {p^{2}}}$$

However, since ${\textstyle t}$ is divisible by ${\textstyle p,}$ ${\textstyle {\frac {(t-1)t}{2}}}$ will also be divisible by ${\textstyle p,}$, except in the case where ${\textstyle p=2,}$ which we have excluded in the previous article. In the remaining cases, we have ${\textstyle {\frac {(t-1)t}{2}}\alpha ^{t-2}hp\equiv 0{\pmod {p^{2}}},}$ and therefore the sum will be ${\textstyle \equiv t\alpha ^{t-1}{\pmod {p^{2}}}.}$ The rest of the proof proceeds as before.

It generally follows from this that, except in the case where ${\textstyle p=2,}$ we have

$$(\alpha +hp^{\mu })^{t}\equiv \alpha ^{t}{\pmod {p^{\mu +\nu }}}$$

and ${\textstyle (\alpha +hp^{\mu })}$ not ${\textstyle \equiv \alpha ^{t},}$ for any modulus that is a power of ${\textstyle p}$ higher than ${\textstyle p^{\mu +\nu },}$ provided that ${\textstyle h}$ is not divisible by ${\textstyle p,}$ and that ${\textstyle p^{\nu }}$ is the highest power of ${\textstyle p}$ that divides ${\textstyle t.}$

From this the first two propositions of that we set out to prove in Art. 85 follow immediately: namely

First, if ${\textstyle \alpha ^{t}\equiv 1,}$ then we also have ${\textstyle (\alpha +hp^{n-\nu })^{t}\equiv 1{\pmod {p^{n}}}.}$

Second, if a number ${\textstyle \alpha '}$ is congruent to ${\textstyle A}$ and consequently to ${\textstyle \alpha }$ modulo ${\textstyle p,}$ then it cannot satisfy the congruence ${\textstyle x^{t}\equiv 1{\pmod {p^{n}}}}$ unless it is congruent to ${\textstyle \alpha }$ modulo ${\textstyle p^{n-\nu }.}$ Indeed, if we had ${\textstyle \alpha '=\alpha +lp^{\lambda }}$, where ${\textstyle l}$ is not divisible by ${\textstyle p}$ and ${\textstyle \lambda <n-\nu ,}$ then we would have ${\textstyle (\alpha +lp^{\lambda })^{t}\equiv \alpha ^{t}}$ modulo ${\textstyle p^{\lambda +\nu },}$ but not modulo the higher power ${\textstyle p^{n},}$ so ${\textstyle \alpha '}$ would not be a root of the congruence ${\textstyle x^{t}\equiv 1.}$

Article 88

Third, we must find a root of the congruence ${\textstyle x^{t}\equiv 1{\pmod {p^{n}}}}$ which is congruent to ${\textstyle A}$ modulo ${\textstyle p.}$ It will suffice to show how this can be achieved if we know a root of the congruence modulo ${\textstyle p^{n-1},}$ since we can then proceed from the modulus ${\textstyle p,}$ for which ${\textstyle A}$ is a root, to the modulus ${\textstyle p^{2},}$ and from there to all consecutive powers.

Let ${\textstyle \alpha }$ be a root of the congruence ${\textstyle x^{t}\equiv 1{\pmod {p^{n-1}}},}$ and let us seek a root of the same congruence modulo ${\textstyle p^{n},}$ which we assume to be ${\textstyle =\alpha +hp^{n-\nu -1},}$ since the previous article tells us it must have this form (later we will separately consider the case where ${\textstyle \nu =n-1;}$ ${\textstyle \nu }$ cannot be greater than ${\textstyle n-1}$). We will then have

$$(\alpha +hp^{n-\nu -1})^{t}\equiv 1{\pmod {p^{n}}}$$

but also

$$(\alpha +hp^{n-\nu -1})^{t}\equiv \alpha ^{t}+\alpha ^{t-1}htp^{n-\nu -1}{\pmod {p^{n}}}$$

Thus if we determine ${\textstyle h}$ in such a way that ${\textstyle 1\equiv \alpha ^{t}+\alpha ^{t-1}htp^{n-\nu -1}{\pmod {p^{n}}};}$ or (since ${\textstyle 1\equiv \alpha ^{t}{\pmod {p^{n-1}}},}$ and ${\textstyle t}$ is divisible by ${\textstyle p^{\nu }}$ by hypothesis) in such a way that ${\textstyle {\frac {\alpha ^{t}-1}{p^{n-1}}}+\alpha ^{t-1}h{\frac {t}{p^{t}}}}$ is divisible by ${\textstyle p,}$ the problem will be solved. Since ${\textstyle t}$ cannot be divisible by a power of ${\textstyle p}$ higher than ${\textstyle p^{\nu },}$ and therefore ${\textstyle \alpha ^{t-1}{\frac {t}{p}}}$ is relatively prime with ${\textstyle p,}$ so it follows from what was shown in the Sect. II that this is always possible.

On the other hand, if ${\textstyle \nu =n-1,}$ i.e. if ${\textstyle t}$ is divisible by ${\textstyle p^{n-1}}$ or by a higher power of ${\textstyle p,}$ then any value ${\textstyle A}$ that satisfies the congruence ${\textstyle x^{t}\equiv 1}$ modulo ${\textstyle p,}$ will satisfy the same congruence modulo ${\textstyle p^{n}.}$ Indeed, if ${\textstyle t=p^{n-1}\tau ,}$ then we will have ${\textstyle t\equiv \tau {\pmod {p-1}};}$ and therefore, since ${\textstyle A^{t}\equiv 1{\pmod {p}},}$ we will also have ${\textstyle A^{\tau }\equiv 1{\pmod {p}}.}$ Thus if ${\textstyle A^{\tau }=1+hp,}$ we will have ${\textstyle A^{t}=(1+hp)p^{n-1}\equiv 1{\pmod {p^{n}}}}$ (Art. 87).

Article 89

Everything that we have demonstrated, starting in Art. 57, with the help of the theorem that the congruence ${\textstyle x^{t}\equiv 1}$ can have no more than ${\textstyle t}$ roots, can be applied to a modulus that is a power of a prime number, and if we call primitive roots the numbers that belong to the exponent ${\textstyle p^{n-1}(p-1),}$ that is to say those whose period contains all numbers not divisible by ${\textstyle p,}$ then there will also be primitive roots in this case. Everything we have said about indices and their use, including the solution of the congruence ${\textstyle x^{t}\equiv 1,}$ can be applied in this case as well. Since the proofs are not difficulty, it would be superfluous to repeat them. We have also shown how one can deduce from the roots of the congruence ${\textstyle x^{t}\equiv 1{\pmod {p}},}$ those of the congruence ${\textstyle x^{t}\equiv 1{\pmod {p^{n}}};}$ but something must be added about the case ${\textstyle p=2,}$ which we had excluded above.

Article 90

On moduli which are powers of two.

If the modulus is a power of two, say ${\textstyle 2^{n},}$ and ${\textstyle n}$ is greater than ${\textstyle 2,}$ then any odd number will become congruent to unity when it is raised to the power ${\textstyle 2^{n-2}.}$

E.g. ${\textstyle 3^{8}=6561\equiv 1{\pmod {32}}.}$

Indeed, every odd number is either of the form ${\textstyle 1+4h}$ or of form ${\textstyle -1+4h,}$ from which the proposition follows immediately (theor. Art. 86).

Therefore, the exponent to which any given odd number belongs modulo ${\textstyle 2^{n}}$ must be a divisor of ${\textstyle 2^{n-2};}$ such a number will therefore belong to one of the exponents ${\textstyle 1,}$ ${\textstyle 2,}$ ${\textstyle 4,}$ ${\textstyle 8,}$ ${\textstyle \dots 2^{n-2};}$ and moreover it is easy to determine the exponent to which it belongs. Let the proposed number be ${\textstyle =4h\pm 1,}$ and let ${\textstyle 2^{m}}$ the largest power of ${\textstyle 2}$ that divides ${\textstyle h}$ (here ${\textstyle m}$ is ${\textstyle =0}$ when ${\textstyle h}$ is odd); then the exponent to which the given number belongs will be ${\textstyle =2^{n-m-2},}$ if ${\textstyle n>m+2;}$ but if ${\textstyle n=}$ or is ${\textstyle <m+2,}$ the proposed number will be ${\textstyle \equiv \pm 1,}$ and therefore will belong to the exponent ${\textstyle 1}$ or to the exponent ${\textstyle 2.}$ Indeed, a number of the form ${\textstyle \pm 1+2^{m+2}k}$ (or equivalently, ${\textstyle 4h\pm 1}$) becomes congruent to unity modulo ${\textstyle p^{n}}$ when raised to the power ${\textstyle 2^{n-m-2},}$ but will not be congruent to unity when raised to any power of lower degree. Thus any number of the form ${\textstyle \pm 1+4h,}$ where ${\textstyle h}$ is odd, that is any number of the form ${\textstyle 8k+3}$ or ${\textstyle 8k+5,}$ belongs to the exponent ${\textstyle p^{n-2}.}$

Article 91

It follows that in this case there are no primitive roots, in the sense that we have given to this expression. That is, there are no numbers whose period contains all the numbers less than and relatively prime to the modulus. However, it is easy to see that something analogous happens here. Indeed, every odd power of a number of the form ${\textstyle 8k+3}$ is itself of the form ${\textstyle 8k+3,}$ and every even power is of the form ${\textstyle 8k+1;}$ therefore no power can be of the form ${\textstyle 8k+5}$ or ${\textstyle 8k+7.}$ Therefore, because the period of a number of the form ${\textstyle 8k+3}$ is composed of ${\textstyle 2^{n-2}}$ distinct terms, each of which is of the form ${\textstyle 8k+1}$ or ${\textstyle 8k+3,}$ and there are no more than ${\textstyle 2^{n-2}}$ such numbers which are smaller than the modulus, it is evident that every number of the form ${\textstyle 8k+1}$ or ${\textstyle 8k+3}$ is congruent to a power of a certain number of the form ${\textstyle 8k+3}$ modulo ${\textstyle 2^{n}.}$ It can be shown in a similar way that the period of a number of the form ${\textstyle 8k+5}$ includes all numbers of the form ${\textstyle 8k+1}$ and ${\textstyle 8k+5.}$ So, if we take a number of the form ${\textstyle 8k+5}$ as a base, we will find real indices for all numbers of the form ${\textstyle 8k+1}$ and ${\textstyle 8k+5}$ taken positively, and for all numbers of the form ${\textstyle 8k+3}$ and ${\textstyle 8k+7}$ taken negatively, where the indices are considered to be equivalent if they are congruent modulo ${\textstyle 2^{n-2}.}$ This is how we must understand Table I, in where for the moduli ${\textstyle 16,}$ ${\textstyle 32}$ and ${\textstyle 64}$ (no table is needed for the modulus ${\textstyle 8}$), we always took the number ${\textstyle 5}$ as the base. E.g. the number ${\textstyle 19,}$ which is of the form ${\textstyle 8n+3}$ and so must be taken negatively, has the index ${\textstyle 7}$ modulo ${\textstyle 64,}$ which means that ${\textstyle 5^{7}\equiv -19{\pmod {64}}.}$ If one were to take numbers of the form ${\textstyle 8n+1}$ and ${\textstyle 8n+5}$ negatively, and those of the form ${\textstyle 8n+3}$ and ${\textstyle 8n+7}$ positively, one would have to give them indices that are, in a sense, imaginary. Introducing these would reduce the indicial calculus to a very simple algorithm; but as we would be led too far if we wanted to treat this subject with complete rigor, we reserve this point for another occasion, when perhaps we will undertake to treat in more detail the theory of imaginary quantities, which, in our opinion, has not yet been reduced to clear notions by anyone. Experts will easily find this algorithm for themselves; those who are less practiced can nevertheless use the table, provided they have properly understood the principles established above, just as those who are not familiar with modern knowledge on imaginary logarithms use logarithms.

Article 92

On moduli which are composed of several prime factors.

For a modulus which is composed of several prime numbers, everything related to residues of powers can be deduced from the general theory of congruences; but since we will present a method below to reduce congruences whose modulus is composed of several prime numbers to others whose modulus is a prime number, or a power of a prime number, we will not dwell much on this matter. We will content ourselves to merely observe that the beautiful property that holds for other moduli, namely that there always exist numbers whose period contains all numbers relatively prime to the modulus, does not hold here, except in the case where the module is twice a prime number, or a power of a prime number. Indeed, if we reduce the modulus ${\textstyle m}$ to the form ${\textstyle A^{a}B^{b}C^{c}}$ etc., with ${\textstyle A,}$ ${\textstyle B,}$ ${\textstyle C}$ etc. being distinct prime numbers, and if we also denote ${\textstyle A^{a-1}(A-1)}$ by ${\textstyle \alpha ,}$ ${\textstyle B^{b-1}(B-1)}$ by ${\textstyle \beta ,}$ etc., and let ${\textstyle z}$ be relatively prime wto ${\textstyle m,}$ then we will have ${\textstyle z^{\alpha }\equiv 1{\pmod {A^{a}}},}$ ${\textstyle z^{\beta }\equiv 1{\pmod {B^{b}}}}$ etc. Therefore, if ${\textstyle \mu }$ is the least common multiple of ${\textstyle \alpha ,}$ ${\textstyle \beta ,}$ ${\textstyle \gamma }$etc., we will have ${\textstyle z^{\mu }\equiv 1}$ with respect to each of the moduli ${\textstyle A^{a},}$ ${\textstyle B^{b}}$ etc., and therefore, modulo ${\textstyle m}$ which is equal to their product. However, except in the case where ${\textstyle m}$ is twice a prime number or a power of a prime number, we will always have ${\textstyle \mu <\alpha \beta \gamma }$ etc., since the numbers ${\textstyle \alpha ,}$ ${\textstyle \beta }$ etc. are all divisible by ${\textstyle 2,}$ and thus cannot be relatively prime. Therefore no number can have a period which contains as many terms as there are numbers less than and relatively prime to the modulus, since the number of the latter is equal to the product ${\textstyle \alpha \beta \gamma }$etc. E.g. for ${\textstyle m=1001=7\cdot 11\cdot 13,}$ the ${\textstyle 60^{th}}$ power of any number relatively prime to ${\textstyle m}$ is congruent to unity, since ${\textstyle 60}$ is the least common multiple of ${\textstyle 6,}$ ${\textstyle 10,}$ and ${\textstyle 12.}$ Finally, the case where the module is twice a prime number or twice a power of a prime number is exactly similar to the case where the modulus is a prime number or a power of a prime number.

Article 93

We have occasionally mentioned the works in which other geometers have spoken about the subject treated in this section. However, those who wish to have certain things explained more fully than our desire for brevity has permitted, we refer them above all to the following works of Euler, which are highly commendable due to the perspicuity that has always distinguished this great man above all others.

Theoremata circa residua ex divisione potestatum relicta Comm. nov. Petr. T. VII, p. 49 sqq.

Demonstrationes circa residua ex divisione potestatum per numeros primos resultantia. (Ibid. T. xviii, p. 85).

To these can also be added Opusculorum analyt. T. I, Diss. 5 and 8.

1. This great man had not quite achieved this goal in a previous commentary. Comm. Petr. T. VI. p. 106. — In the famous debate between Maupertuis and Konig on the principle of least action, a debate that led to unrelated digressions, Konig claimed to have in his possession an autographed manuscript of Leibniz, containing a proof of this theorem which was exactly identical to that of Euler. Appel au public. p. 106. Although we do not want to deny this testimony, it is certain that Leibniz never published his proof. See Hist. de l’Ac. de Prusse, A. 1750. p. 530.
2. However, they differ in that while for logarithms the number of systems is infinite, here it is equal to the number of primitive roots, because congruent bases obviously produce the same systems.
3. It is plain to see that it is unnecessary to know these powers themselves, as one can obtain the minimal residue of each power from that of the previous power.
4. It is easy to see from Art. 18 how to derive this decomposition. We decompose ${\textstyle y}$ into factors that are prime numbers or powers of different prime numbers; each of these divides either ${\textstyle t}$ or ${\textstyle u,}$ or both. We will assign to ${\textstyle t}$ and to ${\textstyle u}$ those prime powers that divide only ${\textstyle t}$ or only ${\textstyle u}$ respectively. As for those dividing both ${\textstyle u}$ and ${\textstyle t,}$ it does not matter which one they are assigned to. If we then let the product of those assigned to ${\textstyle t}$ be ${\textstyle =m,}$ and let the product of those assigned to ${\textstyle u}$ be ${\textstyle =n,}$ then it is easy to se that ${\textstyle m}$ divides ${\textstyle t,}$ ${\textstyle n}$ divides ${\textstyle u,}$ and ${\textstyle mn=y.}$
5. Specifically, we can determine numbers ${\textstyle {\mathfrak {a}},}$ ${\textstyle {\mathfrak {b}},}$ ${\textstyle {\mathfrak {c}},}$ etc. such that ${\textstyle {\mathfrak {a}}\equiv 1{\pmod {a^{\alpha }}}}$ and ${\textstyle \equiv 0{\pmod {b^{\beta }c^{\gamma }\dots }};}$ ${\textstyle {\mathfrak {b}}\equiv 1{\pmod {b^{\beta }}}}$ and ${\textstyle \equiv 0{\pmod {a^{\alpha }c^{\gamma }\dots }}}$ etc., (see Art. 32); then we will have ${\textstyle {\mathfrak {a}}+{\mathfrak {b}}+{\mathfrak {c}}+{\text{etc.}}\equiv 1{\pmod {p-1}},}$ (Art. 19). Now, to express any primitive root ${\textstyle r}$ as a product ${\textstyle ABC}$ etc., we take ${\textstyle A\equiv r^{\mathfrak {a}},}$ ${\textstyle B\equiv r^{\mathfrak {b}},}$ ${\textstyle C\equiv r^{\mathfrak {c}}}$ etc., so that ${\textstyle A}$ will belong to the exponent ${\textstyle a^{\alpha },}$ ${\textstyle B}$ will belong to the exponents ${\textstyle b^{\beta },}$ etc.; the product ${\textstyle A,}$ ${\textstyle B,}$ ${\textstyle C}$etc. will then be ${\textstyle \equiv r{\pmod {p}};}$ finally it is easy to see that ${\textstyle A,}$ ${\textstyle B,}$ ${\textstyle C}$etc., cannot be determined in any other way.