Index Arithmetic

Suppose $r$ is a primitive root of $n$, and $a$ is a positive integer relatively prime to $n$.

We have already seen that all of the powers $r^1, r^2, r^3, \ldots, r^{\varphi(n)}$ produce distinct least positive residues $\pmod{n}$, and are all relatively prime to $n$.

Thus, if $1 \le x \le \varphi(n)$, then $r^x \equiv a \pmod{n}$ must have a unique solution.

Let us call this unique solution the the index, base $r$ of $a$, modulo $n$, and denote it by

$$x = \textrm{ind}_r a$$

Notice this definition has a certain similarity to that of the logarithms one normally encounters in pre-calculus courses -- namely, that the real-value $x$ which solves $r^x = a$ is given by $x = \log_{r} a$.

Of course, when one thinks of logarithms, one immediately remembers the rules for how they can be manipulated -- rules like the following:

One might wonder if an index base $r$ behaves similarly. Our curiosity is well-founded -- we can indeed prove an index-based analog to each of the items shown above: