Exercise 2.8.20 (The only element $a=2 + 101k$ which is not a primitive root modulo $101^2$)

Question

Of the $101$ integers in a complete residue system $\pmod {101^2}$ that are $\equiv 2 \pmod{101}$, which one is not a primitive root $\pmod{101^2}$

Richard Ganaye · Accepted Answer

\begin{proof} The integer $p = 101$ is prime. Note that $2$ is a primitive root modulo $p$, since
$$ 2^{100} \equiv 1 \pmod {101}, \qquad 2^{50} \equiv -1 
ot \equiv 1 \pmod{101},\qquad 2^{20} \equiv 95 
ot \equiv 1 \pmod{101}.$$
(See the Remark p. 100, or Problem 24.)

\bigskip
We search $k$ such that the order of $a = 2 + 101 k$ modulo $101^2$ is not $\phi(101^2) = 101 	imes 100$. By the proof of Theorem 2.39 (p. 102), such an integer $a$ has order $p-1 = 100$ modulo $101^2$, so that $a$ is a root of the congruence
$$f(x) = x^{100} - 1 \equiv 0 \pmod {101^2}.$$
Then, as in the Hensel's Lemma,
\begin{align*}
f(a) \equiv 0 \pmod{p^2} &\iff (2 + 101k)^{100} \equiv 1 \pmod{101^2}\
&\iff  2^{100} +\binom{100}{1}  2^{99} \cdot 101 k \equiv 1 \pmod{101^2}\
&\iff 2^{100} - 1 + 2^{99}\cdot 100 \cdot 101 k \equiv 0 \pmod{101^2}\
&\iff   2^{99} k \equiv \frac{2^{100} - 1 }{101} \pmod{101} & (	ext{since }100 \equiv -1 \pmod{101}\
&\iff k \equiv 2 \, \frac{2^{100} - 1 }{101} \pmod{101} &(	ext{since } 2^{100} \equiv 1 \pmod{101}).
\end{align*}

To avoid to use the big number $2^{100}$, we note that
$$2^{100} \equiv 9293 \pmod{101^2},$$
therefore
$$ \frac{2^{100} - 1 }{101} \equiv 92 \pmod{101},$$
and $2 	imes 92 \equiv  83 \pmod{101} $, so 
$$ (2 + 101k)^{100} \equiv 1 \pmod{101^2} \iff k \equiv 83 \pmod {101}.$$
 In a complete residue system $\pmod {101^2}$ that are congruent to $2$ modulo $101$, the only one which is not a primitive root is the only integer $a$ in this system such that
 $$a \equiv 8385 = 2 + 101	imes 83 \pmod{101}.$$
\end{proof}
Check:
\begin{verbatim}
sage: for k in range(101):
....:     a = Mod(2 + 101 * k, 101^2)
....:     if a.multiplicative_order() != 10100:
....:         print(a)
....:         
8385
\end{verbatim}

Exercise 2.8.20 (The only element $a=2 + 101k$ which is not a primitive root modulo $101^2$)

Answers

Comments

Exercise 2.8.20 (The only element $a=2 + 101k$ which is not a primitive root modulo $101^2$)

Answers

Comments

Add answer