1911 Encyclopædia Britannica/Number/Exponents, Primitive Roots, Indices

29. Exponents, Primitive Roots, Indices. Let $p$ denote an odd prime, and $x$ any number prime to p. Among the powers $x,x^{2},\dots x^{p-1}$ there is certainly one, namely $x^{p-1}$, which $\equiv 1{\pmod {p}}$; let $x^{e}$ be the lowest power of $x$ such that $x^{e}\equiv 1{\pmod {p}}$. Then $e$ is said to be the exponent to which $x$ appertains ${\pmod {p}}$: it is always a factor of $(p-1)$ and can only be $1$ when $x\equiv 1$. The residues $x$ for which $e=p-1$ are said to be primitive roots of $p$. They always exist, their number is $\phi (p-1)$, and they can be found by a methodical, though tedious, process of exhaustion. If $g$ is any one of them, the complete set may be represented by $g,g^{a},g^{b},\dots \!\!\And \!\!\!\!\mathrm {c} .$ where $a,b,\!\!\And \!\!\!\!\mathrm {c} .$, are the numbers less than $(p-1)$ and prime to it, other than $1$. Every number $x$ which is prime to $p$ is congruent, ${\pmod {p}}$, to $g^{i}$, where $i$ is one of the numbers $1,2,3,...(p-1$); this number $i$ is called the index of $x$ to the base $g$. Indices are analogous to logarithms: thus

$\operatorname {ind} _{g}(xy)\equiv \operatorname {ind} _{g}x+\operatorname {ind} _{g}y$. $\operatorname {ind} _{g}(x^{h})\equiv h\ \operatorname {ind} _{g}x{\pmod {\overline {p-1}}}$

Consequently tables of primitive roots and indices for different primes are of great value for arithmetical purposes. Jacobi's Canon Arithmeticus gives a primitive root, and a table of numbers and indices for all primes less than $1000$.

For moduli of the forms $2p,p^{m},2p^{m}$ there is an analogous theory (and also for $2$ and $4$); but for a composite modulus of other forms there are no primitive roots, and the nearest analogy is the representation of prime residues in the form $\alpha ^{x}\beta ^{y}\gamma ^{z}\dots$, where $\alpha ,\beta ,\gamma ,\dots$ are selected prime residues, and $x,y,z,\dots$ are indices of restricted range. For instance, all residues prime to $48$ can be exhibited in the form $5^{x}7^{y}13^{z}$, where $x=0,1,2,3$; $y=0,1$; $z=0,1$; the total number of distinct residues being $4.2.2=16=\phi (48)$, as it should be.