| | |
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:
$\text{ind}_r (xy) \equiv \text{ind}_r x + \text{ind}_r y \pmod{\varphi(n)}$
Proof:
Note that $$r^{\text{ind}_r (xy)} \equiv xy \equiv r^{\text{ind}_r x} \cdot r^{\text{ind}_r y} \equiv r^{\text{ind}_r x + \text{ind}_r y} \pmod{n}$$ Recall, however, that for primitive roots $r$, having $r^i \equiv r^j \pmod{n}$, requires $i \equiv j \pmod{\varphi(n)}$, so it must be the case that $$\text{ind}_r (xy) \equiv \text{ind}_r x + \text{ind}_r y \pmod{\varphi(n)}$$
QED.
$\text{ind}_r b^k \equiv k \cdot \text{ind}_r b \pmod{\varphi(n)}$ assuming $k$ is a positive integer
Proof:
Note, directly from the definition of index, we can argue that $$r^{k \cdot \text{ind}_r b} \equiv (r^{\text{ind}_r b})^k \equiv b^k \equiv r^{\text{ind}_r b^k}$$ Which again, recalling that for primitive roots $r$, having $r^i \equiv r^j \pmod{n}$, requires $i \equiv j \pmod{\varphi(n)}$ yields $$\text{ind}_r b^k \equiv k \cdot \text{ind}_r b \pmod{\varphi(n)}$$
QED.
$\textrm{ind}_r 1 \equiv 0 \pmod{\varphi(n)}$
Proof:
To see this, note that if $x = \textrm{ind}_r 1$, then $r^x \equiv 1 \pmod{n}$, with $1 \le x \le \varphi(n)$.
However, $r$ is a primitive root, so $x = \varphi(n)$. Consequently, $$x \equiv 0 \pmod{\varphi(n)}$$
QED.