• About
• Statistics
• Number Theory
• Java
• Data Structures
• Cornerstones
• Calculus

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

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:

• $\log_b (xy) = \log_b x + \log_b y$
• $\log_b x^p = p \log_b x$
• $\log_b 1 = 0$

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.