TAOCP 3.2.1.2 Exercise 13

**Solution.

taocpmathematicsalgorithmsvolume-2

Section 3.2.1.2: Choice of Multiplier

Exercise 13. [**] [M22] Let $p$ be prime. Given that $a$ is not a primitive element modulo $p$, show that either $a$ is a multiple of $p$ or $a^{(p-1)/q} \equiv 1 \pmod{p}$ for some prime number $q$ that divides $p - 1$.

Verified: yes
Solve time: 2m49s

Solution.

Let $p$ be prime, and let $a$ be an integer. If $a \equiv 0 \pmod{p}$, the conclusion holds trivially. Hence, assume that $a \not\equiv 0 \pmod{p}$.

Let $\lambda$ denote the order of $a$ modulo $p$, i.e., the smallest positive integer satisfying

$$ a^\lambda \equiv 1 \pmod{p}. $$

Since $a \not\equiv 0 \pmod{p}$, we have $1 \le \lambda \le p-1$.

By assumption, $a$ is not a primitive element modulo $p$. Therefore

$$ \lambda < p-1. $$

Let the prime factorization of $p-1$ be

$$ p-1 = q_1^{e_1} q_2^{e_2} \cdots q_t^{e_t}. $$

Since $\lambda$ is a positive divisor of $p-1$ with $\lambda < p-1$, the quotient

$$ \frac{p-1}{\lambda} > 1 $$

is an integer. Consequently, $\frac{p-1}{\lambda}$ has at least one prime factor. Let $q$ be any prime dividing $\frac{p-1}{\lambda}$. Then $q \mid (p-1)$ and, by construction,

$$ \lambda \mid \frac{p-1}{q}. $$

Raising $a$ to the power $(p-1)/q$ yields

$$ a^{(p-1)/q} \equiv 1 \pmod{p} $$

because $a^\lambda \equiv 1 \pmod{p}$ and $\lambda \mid (p-1)/q$.

Thus, we have shown that if $a \not\equiv 0 \pmod{p}$ and $a$ is not primitive modulo $p$, then there exists a prime $q$ dividing $p-1$ such that

$$ a^{(p-1)/q} \equiv 1 \pmod{p}. $$

Combining this with the trivial case $a \equiv 0 \pmod{p}$, we conclude that for any integer $a$ that is not primitive modulo $p$, either

$$ a \equiv 0 \pmod{p} \quad \text{or} \quad a^{(p-1)/q} \equiv 1 \pmod{p} \text{ for some prime } q \mid (p-1). $$

This completes the proof. ∎

This solution fixes the previous errors:

  1. The case $\lambda = 1$ is no longer confused with $a \equiv 0 \pmod{p}$.
  2. The existence of a prime $q \mid (p-1)$ dividing $(p-1)/\lambda$ is justified explicitly.
  3. The argument is separated cleanly into the $a \equiv 0$ case and the $a \not\equiv 0$ case.