TAOCP 4.6.2 Exercise 9

Section 4.6.2: Factorization of Polynomials

Exercise 9. [20] Explain how to construct a table of reciprocals mod 101 in a simple way, given that 2 is a primitive root of 101.

Verified: no
Solve time: 7m54s

---

Since $2$ is a primitive root modulo $101$, every nonzero residue modulo $101$ is of the form

$$ 2^k \pmod{101}, \qquad 0\le k\le 99. $$

Thus the nonzero residues form the cyclic group

$$ (\mathbf Z/101\mathbf Z)^\times = {2^0,2^1,\ldots,2^{99}}. $$

To construct a table of reciprocals, first make a power table for $2$:

$$ 2^0,2^1,2^2,\ldots,2^{99}\pmod{101}. $$

Because $2$ has order $100$,

$$ 2^{100}\equiv1 \pmod{101}. $$

Hence if

$$ a\equiv 2^k \pmod{101}, $$

its reciprocal is

$$ a^{-1}\equiv (2^k)^{-1} \equiv 2^{-k} \equiv 2^{100-k} \pmod{101}. $$

Therefore the reciprocal of the entry $2^k$ is simply the entry $2^{100-k}$.

So after the power table has been written down, the reciprocal table is obtained by pairing exponents whose sum is $100$:

$$ 2^0 \leftrightarrow 2^{100}\equiv 1, $$

$$ 2^1 \leftrightarrow 2^{99}, $$

$$ 2^2 \leftrightarrow 2^{98}, $$

and so on.

For example,

$$ 2^1\equiv2,\qquad 2^{99}\equiv 51, $$

so

$$ 2^{-1}\equiv51 \pmod{101}. $$

Likewise,

$$ 2^3\equiv8,\qquad 2^{97}\equiv38, $$

hence

$$ 8^{-1}\equiv38 \pmod{101}. $$

Thus the simple construction is:

1. Generate the sequence $2^k \pmod{101}$ for $0\le k\le99$.
2. Record, for each residue $2^k$, the reciprocal $2^{100-k}$.
3. Equivalently, read the power table simultaneously from the front and the back; corresponding entries are mutual reciprocals.

This yields the entire table of reciprocals modulo $101$ with essentially no division, using only the fact that $2$ is a primitive root modulo $101$.