$ \DeclareMathOperator{\arccosh}{arccosh} \DeclareMathOperator{\arcsinh}{arcsinh} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\rot}{rot} \DeclareMathOperator{\grad}{grad} \DeclareMathOperator{\diver}{div} $

既約剰余類群と原始根

$n$ を法として掛け算を行うことを考えます。 例えば $n = 10$ のとき $3 \times 7 = 21 \equiv 1 \mod 10$ といった具合に、計算結果に対して $\mod n$ をとることにします。 このときある自然数 $a$ の冪乗が $n$ 未満のほぼ全て[1]の自然数を埋め尽くすとき、このような $a$$n$ の原始根であるといいます。 たとえば $n = 7$ とすると $a = 3$ は次の表のようにこの条件を満たします。
$k$$3^k \mod 7$
$1$$3^1 = 3$
$2$$3^2 = 9 \equiv 2$
$3$$3^3 = 27 \equiv 6$
$4$$3^4 = 81 \equiv 4$
$5$$3^5 = 243 \equiv 5$
$6$$3^6 = 729 \equiv 1$
$a = 5$ も同様に上の条件を満たし、これも原始根となっていることが分かります。 すなわち、原始根は複数存在する場合があります。 一方で $a = 2$ は順番に $2, 4, 8 \equiv 1, \cdots$ となって全ての自然数を埋め尽くしません。
しかしながら例えば $n = 15$ に対しては原始根は一つも存在しないことが分かります ($a = 2, 3, \cdots, 14$ のそれぞれに対して冪乗を求めてみて、実際に存在しないことを確かめてみてください) 。
それでは $n$ がどのようなときに原始根が存在するのだろうか?という疑問に答えるのが本記事のゴールです。
まずはじめに議論を厳密にするために「既約剰余類群」と呼ばれる群を定義します。 それを用いて原始根の定義を厳密に与え、まずはじめに $n$ が素数の場合には必ず原始根を持つことを示します (定理 1) 。 最後に原始根を持つような $n$ の必要十分条件と、その証明を与えることで上の疑問の解答を与えます (定理 2) 。
群論および環論の基礎的な知識を仮定します。

[1]「ほぼ全て」の厳密な定義は本文中で与えます

1用語説明

1.1既約剰余類群

既約剰余類群とは何かについて軽く解説します。
まずはじめに $n$ を法とする剰余類環というものを定義します。
定義 1: 剰余類環
$n$$2$ 以上の自然数とする。 任意の整数に対して $n$ を法として合同な数を同一視するという同値関係を用いて作られた同値類を $\mathbb{Z}/n\mathbb{Z}$ と書き、 これを特に 剰余類 という。 この剰余類の元 $[a], [b]$[1]に対し ($a, b$ はそれぞれ代表元)、次のように加法および乗法を定義するとこれは環になることが分かる。
\begin{equation} [a] + [b] := [a + b] \end{equation}
(1)
\begin{equation} [a] \times [b] := [a \times b] \end{equation}
(2)
こうして定められた環のことを $n$ を法とする 剰余環 (residue ring) または 剰余類環 (residue class ring) という。
さて、いきなり小難しいことをいわれて戸惑っているかもしれませんが、 上でいっていることを簡潔に言うと「足し算も掛け算も $\textrm{mod} \ n$ の世界で考えろ!」ということです。 例えば $n = 10$ としたときには足し算は $6 + 8 = 14 \equiv 4 \mod 10$ のように計算し、 掛け算も同様に $4 \times 9 = 36 \equiv 6 \mod 10$ といった具合に計算せよ、ということです。 ただし $n$ を法として同じ整数は同じものとみなすので、$-1$$9$ も「同じ数」ということになります。
上の定義とはややかけ離れた感じの説明ですが、とりあえずはこのように思ってもらえれば問題はありません。
定義 2: 既約剰余類群
剰余類環 $\mathbb{Z}/n\mathbb{Z}$ の単元群、 すなわち $\mathbb{Z}/n\mathbb{Z}$ の乗法に関する単元 (可逆元) のみを取り出して作った群を、
\begin{equation} (\mathbb{Z}/n\mathbb{Z})^\times \end{equation}
(3)
と書き、これを $n$ を法とする 既約剰余類群[2]という。 $\mathbb{Z}/n\mathbb{Z}$ の乗法に関する単元のみたすべき必要十分条件は $n$ と互いに素であることであるから、この群の元は、
\begin{equation} (\mathbb{Z}/n\mathbb{Z})^\times = \{ [a] | 1 \leqslant a < n, \gcd(a, n) = 1 \} \end{equation}
(4)
である。
またもや難しいことをいっていますが、 これも先ほどのように平易に言い換えると「足し算は忘れろ!」「掛け算に関して逆元の存在しない元も忘れろ!」ということです。 足し算は考えない、というのは特に説明は要らないかと思いますが、 「掛け算に関して逆元が存在しない元」とは何を指すのかよく分からん、という人に少し補足をしたいと思います。 整数 $a$ の積に関する逆元とは $a \cdot b = b \cdot a \equiv 1 \mod n$ となるような整数 $b$ のことを指します。 例えば $n = 10$ のとき、$a = 3$ の逆元は $3 \cdot 7 = 21 \equiv 1 \mod n$ より $7$ だと分かります。 では逆元が存在しない場合、というのはどういうことでしょうか? たとえば $a = 2$ とすると、$b = 0, 1, 2, \cdots, 9$ に対して掛け算をしてみても $1$ にはならないことがすぐに分かります。 従って $a = 2$ は「逆元の存在しない元」ということになります。
上の定義の後半にもあるとおり、逆元の存在しない元とは $n$ とは互いに素でない元であり、かつそのときに限ります。 この証明は練習問題として残しておきます。 まだ何となく雰囲気をつかめていない方はこの問題を解けば少しは納得がいけるかと思います。
練習問題 1: $\mathbb{Z}/n\mathbb{Z}$ の単元の満たすべき必要十分条件
$n$$2$ 以上の自然数とし、$a$ を整数とする。 このとき $a \cdot b = b \cdot a \equiv 1 \mod n$ となる $b$ が存在するための必要かつ十分な条件は $a$$n$ が互いに素であること、 すなわち $\gcd(a, n) = 1$ であることを示せ。
必要であることは背理法を使ってすぐに示せると思います。 十分条件の方は少し難しい…というか前提知識が必要なので次のキーワードをあげておきます: 拡張された Euclid の互除法
ところで既約剰余類群の位数 (元の個数) はいくつなのでしょうか? 上の演習問題より明らかにそれは $n$ 未満の $n$ と互いに素な自然数の数に一致します。 それを $\varphi(n)$ と書きます。 $\varphi(\cdot)$ は Euler の トーティエント (totient) 函数 と呼ばれています。 詳しくは Wikipeida:オイラーのφ関数 に説明を預けたいと思います。 証明の途中でトーティエント函数の持つ性質を使うので、ご存じでない方は読み進む前に一読をお願いします。

1.2原始根

既約剰余類群は一般に巡回群にはなりませんが、特定の $n$ に対しては巡回群になることがあります。 ここで既約剰余類群が巡回群になるとは、ある元 $\alpha$ が存在して $\alpha, \alpha^2, \alpha^3, \cdots$ が考えている既約剰余類群の全ての元を尽くすこと、 すなわち任意の元 $x$ に対しある自然数 $k$ が存在してその元が $x = \alpha^k$ の形に書けることを意味します。 既約剰余類群が巡回群になるとき、この巡回群の生成元のことを特に 原始根 (primitive root) といいます。 例えば $n = 7$ のとき、冒頭で述べたように $a = 3$ は原始根です。
ここでは本記事の本題である「$n$ がどのような条件を満たせば $n$ を法とする既約剰余類群は巡回群となる (以下では「原始根を持つ」ということにします) のだろうか?」ということを議論するのは後にまわすことにして、 ここでは原始根が存在する場合にはいくつの相異なる原始根が存在するのかを考えたいと思います。
命題 1: 原始根の個数
$n$$2$ 以上の自然数とする。 このとき $n$ を法とする既約剰余類群が原始根を持つとすると、互いに異なる原始根はちょうど $\varphi(\varphi(n))$ 個だけ存在する。
証明 1
まずはじめに原始根は生成元であるから、原始根の位数と群の位数は一致しなければならないこと、 すなわちちょうど $\varphi(n)$ にならなければいけないことに注意しておく。
原始根を $\alpha$ とおく。 原始根の定義より任意の既約剰余類群の元は $k = 1, 2, \cdots, \varphi(n)$ を用いて $\alpha^k$ とかける。 よって $\alpha^k$ が原始根となる $k$ が満たすべき必要十分条件を調べればよいことが分かる。 この必要十分条件は $k$$\varphi(n)$ が互いに素になることである。 なぜならば、まず必要条件であることは、もし $k$$\varphi(n)$ が互いに素でないとすると共通の因数 $l$ を持つことになるが、 このとき、
\begin{equation} (\alpha^k)^{\varphi(n)/l} = (\alpha^{\varphi(n)})^{k/l} = 1 \end{equation}
(5)
となりこれは $\alpha^k$ の位数が $\varphi(n)/l$ 以下であることを表しており、このことは $\alpha$ が原始根であることに反す。 次に十分条件であるが、$\alpha^k$ の位数を $l$ とおくと、$\alpha^{kl} = 1$ より $\varphi(n) | kl$ である。 ここで $k$$\varphi(n)$ は仮定より互いに素であるから、$\varphi(n) | l$ でなければならない。 ところが $l \leqslant \varphi(n)$ であることから $l = \varphi(n)$ でなければならないことが分かり、 $\alpha^k$ の位数は $\varphi(n)$ であること、すなわち $\alpha^k$ は原始根であることが分かる。
以上より原始根は $\varphi(n)$ と互いに素な自然数 $k$ をもちいて $\alpha^k$ とかけるとき、かつそのときに限るため、 原始根は全部でちょうど $\varphi(\varphi(n))$ 個だけあることが分かる。
上の命題から $n = 7$ の場合、原始根の個数は $\varphi(\varphi(7)) = \varphi(6) = 2$ であることが分かります。 実際、原始根は $a = 3, 5$ のみであり、矛盾がないことが分かります。

[1]以下では剰余類を表すための括弧 ("[", "]") を省略してしまうことがあります。 たとえば $1$ と書いたら $[1]$ のことを指すことがあります。 このようにしてしまう理由としては単に面倒、というのも一つありますが、 むしろ省略した方が混乱が起きにくいと感じたためです。 厳密なことが気になる方は不快な思いをするかもしれませんが、ご容赦ください
[2]英語では irreducible residue class group とかで良い気がするのですが、ググってもヒットしません…。 日本語のようにかっこいい(?)名前はないのか、multiplicative group of integers modulo n などというらしいです

2n が素数のときには原始根が必ず存在すること

$n$ が素数のときには必ず原始根を持つことが知られています。
定理 1: 素数を法とする既約剰余類群は必ず原始根を持つ
$p$ を素数とすると、$p$ を法とする既約剰余類群は必ず原始根を持つ。
この定理の証明に入る前にいくつかの補題を示しておく必要があります。
補題 1: 多項式と根の個数
$p$ を素数とし、自然数 $d$$d | (p-1)$ を満たすものとする。 このとき多項式、
\begin{equation} f(x) := x^d - 1 \in (\mathbb{Z}/p\mathbb{Z})[x] \end{equation}
(6)
はちょうど $d$ 個の相異なる根を持つ。
証明 2
$e := (p-1) / d$ とおく。 このとき、
\begin{align*} x^{p-1} - 1 & = (x^d)^e - 1 \\ & = (x^d - 1) ((x^d)^{e-1} + (x^d)^{e-2} + \cdots + 1) \\ & =: (x^d - 1) g(x) \end{align*}
(7)
となる。 ここで Fermat の小定理から $x^{p-1} - 1$$x = 1, 2, \cdots, p-1$ のちょうど $p-1$ 個の相異なる根を持つ。 一方 $g(x)$ の次数は $d(e-1) = p - d - 1$ であるから $g(x)$ は高々 $p - d - 1$ 個の相異なる根を持ち、 $x^d - 1$ は高々 $d$ 個の相異なる根を持つ。 従って (7) 式の最終行が $p - 1$ 個の相異なる根を持つためには $x^d - 1$$d$ 個の相異なる根を持たなければならないことが分かり、補題が成立することが分かる。
補題 2: 積をとったときの元の位数
$G$ を Abel 群 (可換群) とする。 $a, b \in G$ に対してそれぞれの位数を $r, s$ とおく。 $r, s$ は互いに素であると仮定する。 このとき $a \circ b \in G$ ($\circ$ は群 $G$ の二項演算。以下適宜省略する) の位数はちょうど $rs$ となる。
証明 3
$(ab)^{rs} = (a^r)^s (b^s)^r = 1$ であるから、$ab$ の位数は $rs$ の約数である。 すなわち $\tilde{r} | r, \tilde{s} | s$ なる $\tilde{r}, \tilde{s}$ をもちいて $ab$ の位数は $\tilde{r} \tilde{s}$ と書ける。 このとき、
\begin{equation} a^{\tilde{r}\tilde{s}} b^{\tilde{r}\tilde{s}} = 1 \end{equation}
(8)
の両辺を $r / \tilde{r}$ 乗することで、
\begin{equation} 1 = a^{r\tilde{s}} b^{r\tilde{s}} = b^{r\tilde{s}} \end{equation}
(9)
を得る。 従って $s | r\tilde{s}$ であるが、いま仮定から $s, r$ は互いに素であったから $s | \tilde{s}$ でなければならず、 $\tilde{s} | s$ と合わせて $s = \tilde{s}$ を得る。 $r$ についても同様の議論を繰り返すことで $r = \tilde{r}$ を得るため、$ab$ の位数は $\tilde{r} \tilde{s} = rs$ であることが分かる。
以上で準備は終わりです。 いよいよ定理 1 の証明に入りましょう。
証明 4: 定理 1 の証明
まず $p = 2$ の場合は自明であるから、$p$ は奇素数であるとする。 このとき $p - 1$ を素数の積に分解する。
\begin{equation} p-1 = q_1^{e_1} q_2^{e_2} \cdots q_k^{e_k} \end{equation}
(10)
ただし各 $q_i$ は互いに異なる素数であり、$e_i \geqslant 1, k \geqslant 1$ である。 いま補題 1 より、
  • $x^{q_i^{e_i}} - 1$ はちょうど $q_i^{e_i}$ 個の根を持つ
  • $x^{q_i^{e_i-1}} - 1$ はちょうど $q_i^{e_i-1}$ 個の根を持つ
ということがいえるので、$\alpha_i^{q_i^{e_i}} = 1$ かつ $\alpha_i^{q_i^{e_i-1}} \neq 1$ をみたすような $\alpha_i$ の個数はちょうど $q_i^{e_i} - q_i^{e_i-1} = q_i^{e_i-1} (q_i - 1) \quad (> 0)$ 個だけ存在する。 特にこの $\alpha_i$ の位数は明らかに $q_i^{e_i}$ である。 このような $\alpha_i$ を各 $i$ に対して一つずつ選び出し、それらの積を考える。
\begin{equation} \alpha := \alpha_1 \alpha_2 \cdots \alpha_k \end{equation}
(11)
すると補題 2 を繰り返し適用することにより $\alpha$ の位数は $q_1^{e_1} q_2^{e_2} \cdots q_k^{e_k} = p - 1$ であり、 $\alpha$ は原始根であることが分かる。
途中の議論から明らかなように原始根の個数はちょうど、
\begin{equation} \prod_{i=1}^k q_i^{e_i-1} (q_i - 1) \end{equation}
(12)
であり、これは $\varphi(p-1) = \varphi(\varphi(p))$ と一致することが知られているので[1]この結果は命題 1 の主張と整合します。

[1]一般に $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ と相異なる素数の積に分解したとき、トーティエント函数は、
\begin{equation} \varphi(n) = \prod_{i=1}^k p_i^{e_i-1} (p_i - 1) = n \prod_{i=1}^k \left( 1 - \frac{1}{p_i} \right) \end{equation}
(13)
であることが知られています

3原始根の存在する必要十分条件

さて、$n$ が素数の場合には必ず原始根が存在することは示されたわけですが、 ではそれ以外の場合にはどのようなときに原始根が存在するのでしょうか?
このことに関して次のことが知られています。
定理 2: 原始根を持つための必要十分条件
$n$$2$ 以上の自然数とする。 このとき $n$ を法とする既約剰余類群が原始根を持つための必要かつ十分な条件は、$p$ を奇素数とし、$k$ を自然数としたとき、
\begin{equation} n = 2, 4, p^k, 2p^k \end{equation}
(14)
のいずれかの形でかけることである。
この定理を十分であることと、必要であることの二つに分けて証明していきたいと思います。

3.1十分であること

実際の議論に入る前に、証明の中で必要となるので次の定理を紹介しておきます。
定理 3: Euler の定理
$n$ を自然数、$a$ を整数とし、$\gcd(n, a) = 1$ であるとする。 このとき $\varphi(\cdot)$ を Euler のトーティエント函数として、
\begin{equation} a^{\varphi(n)} \equiv 1 \mod n \end{equation}
(15)
が成り立つ。
この定理の証明は平易ですので練習問題としておきます。
練習問題 2: Euler の定理の証明
上述の Euler の定理を証明せよ。
ヒント: 群論の初歩的な知識から、一般に $G$ を群とし、$H$$G$ の部分群としたとき $|H| \Big| |G|$ である。 このことと $a$$(\mathbb{Z}/n\mathbb{Z})^\times$ の元とみたときの $a$ の生成する巡回部分群を考える。

まず $n = 2, 4$ のときには具体的に確かめることができます[1]
また $p$ を奇素数として $n = p$ のときにはすでに示したとおり原始根を持ちます。 この原始根を $\alpha$ とおくことにします。
$n = 2p$ のとき、$\alpha$$(\mathbb{Z}/2p\mathbb{Z})^\times$ における位数を $l$ とおくと、 $l | \varphi(2p) = p-1$ でなければいけません。 なぜならば群論の初歩的な知識により、一般に部分群の位数はもとの群の位数の約数でなければいけませんから、 このことを $\alpha$ によって生成される位数 $l$ の巡回部分群に対して適用することによって示されます。 一方で $l$$\alpha$ の位数より $\alpha^l \equiv 1 \mod 2p$ でありますから $\alpha^l \equiv 1 \mod p$ も成り立ちます。 $\alpha$$(\mathbb{Z}/p\mathbb{Z})^\times$ の原始根よりこれは $(p - 1) | l$ を表しています。 従って $l = p - 1$ であり、$(\mathbb{Z}/2p\mathbb{Z})^\times$ の位数が $\varphi(2p) = p - 1$ であることを考えれば、 $\alpha$$(\mathbb{Z}/2p\mathbb{Z})^\times$ においても原始根となっていることが分かります。
ここで $n = p^k$ の場合と $n = 2p^k$ の場合を統一的に扱うために $t = 1\ \text{or}\ 2$ とおきます。
$n = tp^2$ のときを考えます。 このとき $(tp + 1)^i \equiv {_iC_1} tp + 1 = itp + 1 \mod tp^2$ なので、$tp + 1$ の位数は $p$ であることが分かります。 また $\alpha$$(\mathbb{Z}/tp^2\mathbb{Z})^\times$ における位数は $n = 2p$ のときの議論と同様の議論により $p-1$ の倍数でなくてはいけないので、 その位数を $s$ をある自然数として $s (p - 1)$ とおきます。 このとき $\alpha^s$ の位数は明らかに $p - 1$ ですから、 $\beta := \alpha^s \times (tp + 1)$ の位数は補題 2 より $(p-1) \times p = \varphi(tp^2)$ であることが分かり、 これは原始根となっていることが分かります。
最後に $n = tp^k$ ($k \geqslant 3$) の場合を考えます。 $\beta$$(\mathbb{Z}/tp^k\mathbb{Z})^\times$ における位数を $l$ とおくと $p(p-1) = \varphi(tp^2) | l$ であることが分かります。 また $\beta$ の生成する位数 $l$ の巡回部分群はもとの群の位数 $\varphi(tp^k) = p^{k-1}(p-1)$ を割り切らなければなりませんから、 $l | p^{k-1}(p-1)$ でなければいけません。 従って以上から $l = p(p-1), p^2(p-1), \cdots, p^{k-1}(p-1)$ のいずれかであることが分かりますが、 次に示す補題から実は $l = p^{k-1} (p-1)$ でなければならないことが分かり、 とくに $\beta$$(\mathbb{Z}/tp^k\mathbb{Z})^\times$ においても原始根となっていることが分かります。
補題 3
$t = 1\ \text{or}\ 2$ とし $p$ を奇素数とする。 また $r$$r^{p-1} \not\equiv 1 \mod tp^k$ なる整数とする。 このとき $2$ 以上の任意の自然数 $k$ に対して、
\begin{equation} r^{p^{k-2}(p-1)} \not\equiv 1 \mod tp^k \end{equation}
(16)
が成り立つ。
証明 5
$k = 2$ のときは仮定より明らかに成立する。 従って以下では数学的帰納法を用いて $2$ 以上の任意の自然数 $k$ に対して補題が成立することを示そう。 定石通り $k = m-1$ のときに補題が成り立つことを仮定し、$k = m$ のときにも補題が成立することを示す。
Euler の定理から $r^{p^{m-3}(p-1)} = r^{\varphi(tp^{m-2})} \equiv 1 \mod tp^{m-2}$ であるからある自然数 $c$ をもちいて、
\begin{equation} r^{p^{m-3}(p-1)} = 1 + ctp^{m-2} \end{equation}
(17)
と書ける。 ただし帰納法の仮定から $r^{p^{m-3}(p-1)} \not\equiv 1 \mod tp^{m-1}$ であるから $p \not| c$ であることに注意する。 上式の両辺を $p$ 乗することで、
\begin{equation} r^{p^{m-2}(p-1)} = 1 + {_pC_1} ctp^{m-2} + {_pC_2} (ctp^{m-2})^2 + \cdots \equiv 1 + ctp^{m-1} \mod tp^m \end{equation}
(18)
ここで $p \not| c$ であったから $ctp^{m-1} \not\equiv 0 \mod tp^m$ であり、$r^{p^{m-2}(p-1)} \not \equiv 1 \mod tp^m$ である。 以上で帰納法は完結し、与えられた補題は示された。
$\beta$ は上の補題の仮定 $\beta^{p-1} \not\equiv 1 \mod tp^k$ を明らかにみたすので[2]この補題を用いることができて、
\begin{equation} \beta^{p^{k-2}(p-1)} \not\equiv 1 \mod tp^k \end{equation}
(19)
です。 このことからただちに $j < k-2$ なる自然数 $j$ に対しても明らかに $\beta^{p^j(p-1)} \not\equiv 1 \mod tp^k$ ですから ($\because$背理法) 、 $\beta$ の位数 $l$$l = p^{k-1}(p-1)$ でなければいけないことが分かります。 従って繰り返しになりますが、$\beta$ の位数は $tp^k$ を法とする既約剰余類群の位数 $\varphi(tp^k)$ と一致し、 $\beta$$(\mathbb{Z}/tp^k\mathbb{Z})^\times$ においても原始根となることがいえます。
従って以上で $n = 2, 4, p^k, 2p^k$ のいずれかの形であれば必ず原始根を持つことが示されました。

3.2必要であること

$2$ 以上の自然数 $n$ を素数の積として、
\begin{equation} n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \end{equation}
(20)
と分解します。 ただし各 $p_i$ は互いに異なる素数であり $e_i \geqslant 1, k \geqslant 1$ を満たすとします。 このとき中国の剰余定理から群準同型、
\begin{equation} (\mathbb{Z}/n\mathbb{Z})^\times \cong (\mathbb{Z}/p_1^{e_i}\mathbb{Z})^\times \times (\mathbb{Z}/p_2^{e_2}\mathbb{Z})^\times \times \cdots \times (\mathbb{Z}/p_k^{e_k}\mathbb{Z})^\times \end{equation}
(21)
が従います。 従って $(\mathbb{Z}/n\mathbb{Z})^\times$ の元のうち最大の位数を持つ元は明らかに、 各 $(\mathbb{Z}/p_i^{e_i}\mathbb{Z})^\times$ の原始根を $\alpha_i$ とおいたとき、 $(\alpha_1, \alpha_2, \cdots, \alpha_k)$ に対応する元です。 その位数は明らかに $\mathrm{lcm}(\varphi(p_1^{e_1}), \varphi(p_2^{e_2}), \cdots \varphi(p_k^{e_k}))$ ですが、 これが $\varphi(n) = \prod_i \varphi(p_i^{e_i})$ に一致するためには各 $\varphi(p_i^{e_i})$ は互いに素でなければいけないことがすぐに分かります。 $p_i$ が奇素数の場合には $\varphi(p_i^{e_i}) = p_i^{e_i-1}(p_i-1)$ でありこれは偶数ですから、 相異なる奇素数が二つ以上含まれてはいけないことが分かります。
以上の議論から $n$$l \geqslant 0, k \geqslant 1$ を満たす整数と素数 $p$ を用いて、
\begin{equation} n = 2^l p^k \end{equation}
(22)
の形でなければならないことが分かります。 ただし $p = 2$ の場合は不定性をなくすため、$k = 1$ であると約束します。 ここで $l \geqslant 2$ であってはならないことが示されれば、 必要条件が示されることに注意します。
$l \geqslant 2$ であるとし、かつ $(\mathbb{Z}/n\mathbb{Z})^\times$ に原始根が存在することを仮定し、矛盾を導きましょう。 $(\mathbb{Z}/n\mathbb{Z})^\times$ の位数 $\varphi(n)$$l \geqslant 2$ より偶数であり、 任意の偶数位数の巡回群 $G$ (生成元を $g$ とする) における $1$ の平方根は $1, g^{|G|/2}$ のちょうど二個であることから、 $(\mathbb{Z}/n\mathbb{Z})^\times$ における $1$ の平方根も $\pm 1$ のみであることが分かります。 ここで $(2^{l-1} p^k + 1)^2 = 2^{2l-2} p^{2k} + 2^{l} p^k + 1 \equiv 1 \mod n$ であるので $2^{l-1} p^k + 1 \equiv \pm 1 \mod n$ でなくてはなりません。 ところがこれはどちらも矛盾をきたすことがただちに分かります。 なぜならば $2^{l-1} p^k \equiv 0 \mod n$ または $2^{l-1} p^k + 2 \equiv 0 \mod n$ ですが、 この二式の左辺は両者とも $n$ 未満であり $0$ と合同になることはあり得ないからです。 従って $(\mathbb{Z}/n\mathbb{Z})^\times$ が原始根を持つためには $l \geqslant 2$ であってはならないことが示され、 従って必要条件も示されたことになります。

[1]$n = 2$ のときには $1$ が原始根、$n = 4$ のときには $3$ が原始根です
[2]$\beta$ の位数はすでに示したとおり $p(p-1), p^2(p-1), \cdots, p^{k-1}(p-1)$ のいずれかなので、 $\beta^{p-1} \equiv 1 \mod tp^k$ は明らかにこの事実と矛盾します