原始根① 素数の場合とArtin予想

最近、原始根に関するArtin予想というある未解決問題に興味があります。
この記事ではまず原始根を導入しその基本的な性質について議論し、最後にArtin予想について紹介します。

参考文献
Eulerの定理、Fermatの小定理と原始根
位数に関する補題
法が素数の場合の原始根
Artin予想について

参考文献

(1)Elements of number theory*1

リンク

(2)整数論入門

リンク

Eulerの定理、Fermatの小定理と原始根

原始根の導入に先立ち、まずは合同式に関するEulerの定理を証明します。

Theorem1(Eulerの定理)

任意の整数 $m$ と $(a,m)=1$ を満たす整数 $a$ に対して
\begin{equation*}
a^{\varphi (m)} \equiv 1 \quad (\mathrm{mod} \; m)
\end{equation*}が成立する。ここで $\varphi (m)$ はEulerのトーシェント関数とする。

証明乗法群 $(\mathbb{Z}/m\mathbb{Z} )^{\times}$ の元を
\begin{equation*}
(\mathbb{Z}/p\mathbb{Z} )^{\times}=\{ r_1, \dots , r_{\varphi (m)} \}
\end{equation*}と羅列しておく。このとき $(a,m)=1$ から
\begin{equation*}
(\mathbb{Z}/p\mathbb{Z} )^{\times}= \{ ar_1, \dots , ar_{\varphi (m)} \}
\end{equation*}が成立する。したがって両方の成分をすべて掛け合わせると
\begin{align*}
a^{\varphi(m)} \cdot (r_1 \cdots r_{\varphi(m)}) \equiv r_1 \cdots r_{\varphi(m)} \quad (\mathrm{mod} \; m)
\end{align*}が成立する。これより定理の主張が従う。(QED)

Erlerの定理(Theorem1)において $m$ が素数の場合はFermatの小定理とも呼ばれています。Eulerの定理は
\begin{equation}
a^n \equiv 1 \quad (\mathrm{mod}\; m) \label{Euler eq}
\end{equation}を満たす解 $n=\varphi(m)$ を与えますが、他にこの方程式を満たす解 $n$ があるかどうかについては議論していません。これを動機として原始根を定義します。

Definition2(位数と原始根)

$(a,m)=1$ を満たす整数 $a,m$ に対して、 $1\le n \le p-1$ で方程式\eqref{Euler eq}を満たす最小の $n$ を $a$ のmod $m$ における位数と呼び $\mathrm{ord}_m (a)$ と書く。また\begin{equation*}
\mathrm{ord}_m (a)=\varphi(m)
\end{equation*}が成り立つとき $a$ をmod $m$ の原始根と呼ぶ。

群論的な言い方をするとmod $m$ の原始根とは乗法群 $(\mathbb{Z}/m\mathbb{Z})^{\times}$ の生成元のことです。原始根が存在するかどうかは乗法群が巡回群になるか否かを問う問題と同値になります。

位数に関する補題

原始根について議論するために位数に関する基本的な補題をいくつか証明します。
以下 $(a,m)=(a',m)=1$ を仮定して計算します。

Lemma3

整数 $t,t'$ に対し
\begin{equation*}
a^t \equiv a^{t'} \quad (\mathrm{mod}\; m) \Leftrightarrow t \equiv t' \quad (\mathrm{mod } \; \mathrm{ord}_m(a) )
\end{equation*}が成立する。特に $\mathrm{ord}_m(a)$ は $\phi(m)$ の約数。

証明 $\Leftarrow$ は $\mathrm{ord}_m(a)$ の定義から明らかに成立するので $\Rightarrow$ を示す。剰余の定理から適当な整数 $q.q'$ と $0\le r,r' < \mathrm{ord}_m(a)$ を用いて
\begin{equation*}
t=\mathrm{ord}_m(a) \cdot q +r, \quad t'=\mathrm{ord}_m(a) \cdot q' +r'
\end{equation*}と表すことができる。これを仮定の式に代入すれば位数の定義から
\begin{equation*}
a^r \equiv a^{r'} \quad (\mathrm{mod}\; m)
\end{equation*}が成立。従って $r,r'$ の大きさから $r=r'$ が成立することがわかる。これは $t\equiv t'$ がmod $\mathrm{ord}_m(a)$ で成立することを意味している。
特にTheorem1と位数の定義から $a^{\mathrm{ord}_m(a)}\equiv a^{\varphi(m)} \equiv 1\; (\mathrm{mod} \; m)$ なので $\varphi(m) \equiv 0 \; (\mathrm{mod} \; \mathrm{ord}_m(a))$ となる。(QED)

Lemma4

整数 $k,l$ で
\begin{equation*}
\mathrm{ord}_m(a)=kl
\end{equation*}と表されていると仮定する。このとき
\begin{equation*}
\mathrm{ord}_m \left( a^k \right) =l
\end{equation*}が成立する

証明仮定から
\begin{equation*}
\left( a^k \right)^l \equiv 1 \quad (\mathrm{mod}\; m)
\end{equation*}なのでLemma3から $l$ は $\mathrm{ord}_m (a^k)$ の倍数である。一方で
\begin{equation*}
a^{k \cdot \mathrm{ord}_m(a^k)} \equiv 1 \quad (\mathrm{mod} m)
\end{equation*}なのでLemma3から $k \cdot \mathrm{ord}_m(a^k)$ は $\mathrm{ord}_m(a) =kl$ の倍数。つまり $ord_m(a^k)$ は $l$ の倍数となる。以上より $\mathrm{ord}_m(a^k)=l$ が成立する。(QED)

Lemma5

$(\mathrm{ord}_m(a),\mathrm{ord}_m(a'))=1$ ならば
\begin{equation*}
\mathrm{ord}_m(aa')=\mathrm{ord}_m(a) \cdot \mathrm{ord}_m(a')
\end{equation*}が成立する。

証明位数の定義からmod $m$ で
\begin{equation*}
1 \equiv \left( (aa')^{\mathrm{ord}_m(aa')} \right)^{\mathrm{ord}_m(a)} \equiv (a')^{\mathrm{ord}_m(aa')\cdot \mathrm{ord}_m(a)}
\end{equation*}が成立する。したがってLemma3から
\begin{equation*}
\mathrm{ord}_m(aa') \cdot \mathrm{ord}_m(a) \equiv 0 \quad (\mathrm{mod}\; \mathrm{ord}_m(a') )
\end{equation*}が成り立つが $(\mathrm{ord}_m(a),\mathrm{ord}_m(a'))=1$ より
\begin{equation*}
\mathrm{ord}_m(aa') \equiv 0 \quad (\mathrm{mod}\; \mathrm{ord}_m(a') )
\end{equation*}が成立する。さらに、まったく同様に
\begin{equation*}
\mathrm{ord}_m(aa') \equiv 0 \quad (\mathrm{mod}\; \mathrm{ord}_m(a) )
\end{equation*}も成立。すなわち
\begin{equation*}
\mathrm{ord}_m(a) \cdot \mathrm{ord}_m(a') | \mathrm{ord}_m(aa')
\end{equation*}が成立する。一方で
\begin{equation*}
(aa')^{\mathrm{ord}_m(a) \cdot \mathrm{ord}_m(a')} \equiv 1 \quad (\mathrm{mod} \; m)
\end{equation*}が成り立つのでLemma3から
\begin{equation*}
\mathrm{ord}_m(aa') |\mathrm{ord}_m(a) \cdot \mathrm{ord}_m(a')
\end{equation*}以上より主張が成立する。(QED)

法が素数の場合の原始根

法が素数であれば原始根を構成することができます。

Theorem6

素数 $p$ に対して $\mathrm{mod}\; p$ の原始根が存在する。

証明 mod $p$ の位数として取りうる値の集合を
\begin{equation*}
\left\{ \mathrm{ord}_m(a) | a \in ( \mathbb{Z}/p \mathbb{Z} )^{\times} \right\} =\{ \delta_1, \dots , \delta_r \}
\end{equation*}と書くことにする。さらに $\tau =[ \delta_1, \delta_2 ,\dots , \delta_r]$ と定め
\begin{equation*}
\tau = q_1^{\alpha_1} q_2^{\alpha_2} \cdots q_k^{\alpha_k}
\end{equation*}と素因数分解しておく。このとき $\tau$ の定め方から任意の $s=1,\dots , k$ に対して、ある $i_s =1, \dots , r$ が存在して
\begin{equation*}
q_s^{\alpha_s} | \delta_{i_s} \Leftrightarrow \delta_{i_s}=t_sq_s^{\alpha_s} \quad (t_s:=\delta_{i_s}/q_s^{\alpha_s} )
\end{equation*}が成立する。さらに $\delta_{i_s}$ に対応して
\begin{equation*}
\mathrm{ord}_p (a_s)=\delta_{i_s}=t_sq_s^{\alpha_s}
\end{equation*}となる $a_s\in (\mathbb{Z}/p\mathbb{Z})^{\times}$ が取れる。このときLemma4から
\begin{equation*}
\mathrm{ord}_p(a_s^{t_s})=q_s^{\alpha_s}
\end{equation*}が成立。 $q_s \; (s=1,\dots ,k)$ は互いに素なので $g=a_1^{t_1} a_2^{t_2}\cdots a_k^{t_k}$ と定めればLemma5から
\begin{equation*}
\mathrm{ord}_p(g)=q_1^{\alpha_1}\cdots q_k^{\alpha_k} =\tau
\end{equation*}が成立する。したがって $\tau$ はmod $p$ の位数であり、Lemma3から $\tau | p-1$ となる。一方で $\tau$ 次の合同方程式
\begin{equation*}
x^{\tau} \equiv 1 \quad (\mathrm{mod} \; p)
\end{equation*}を考えると $\tau$ の定義から $x=1, \dots ,p-1$ 全てを解に持つ。すなわちこの方程式は $p-1$ 個の解をもつため $\tau \ge p-1$ でなければならない*2。以上より $\tau=p-1$ が成立。原始根の定義から $g$ がmod $p$ の原始根であることがわかる。(QED)

Artin予想について

素数 $p$ に対してmod $p$ の原始根が存在することがわかりましたが、逆に整数 $a$ を固定したとき $a$ を原始根にもつ素数 $p$ がどれだけあるかを問う問題がArtin予想です。

Conjecture7(Artin予想)

整数 $a$ を $\pm 1$ もしくは平方数ではないものとする。このとき $a$ を原始根に持つ素数 $p$ が無限に存在する。

除いた $\pm 1$ と平方数ですが、 $\pm 1$ は位数が2以下なのでmod $p>3$ で原始根にはなりえず、また $a$ が平方数 $a=n^2$ のときはTheorem1から
\begin{equation*}
a^{(p-1)/2} \equiv n^{p-1} \equiv 1 \quad (\mathrm{mod} \; p)
\end{equation*}となるのでやはり原始根にはならないことがわかります。

Artin予想は現在未解決ですが、いろいろと部分的な結果が証明されています。

Theorem8(C. Hooley, 1967)

任意の素数 $q$ に対して代数体 $\mathbb{Q}(k^{1/q})$ 上の一般Riemann予想が成立するならArtin予想が成立する。さらに $\pi_a(x)$ を $p\le x$ で $a$ を原始根にもつものの数とすると\begin{equation*}
\pi_a(x) \sim C(a) \frac{x}{\log x} \quad (x\to \infty)
\end{equation*}が成立。ここで $C(a)$ は $a$ に依存する定数。

unconditionalな結果で最も強いものは次の定理です。

Theorem9(D. R. Heath Brown, 1986)

次が成立する。
(1) Artin予想がなりたたないような素数 $a$ は高々2個
(2) Artin予想が成り立たないようなSquare free数 $a$ は高々3個
(3) Artin予想が成り立たないような $a\le x$ の数は高々 $O((\log x)^2)$ 個

証明はやはり篩法によるものです。

*1:参考文献(1)の初等整数論の本は初学者にとてもおすすめです。著者のVinogradovは整数論や素数分布論で数多くの結果を残した伝説的な数学者です。この本には演習問題が豊富に載っており(しかも解答つき)、そこに著者のこだわりが現れているように思います。参考文献(2)はVinogradovによる(1)の本を日本語に訳したものです。

*2:この部分が法が素数の場合のみ成立する。法が合成数のときは $n$ 次方程式が $n$ 個より多い解を持ちうる。

プライムス

大学院生の数学ノート