素数に関するオイラーの定理

この記事の所要時間: 415

素数に関するオイラーの定理

ここでは,(フェルマーの) 2平方定理の証明で用いる素数に関するオイラーの定理の証明をします.

2平方定理

奇素数(奇数かつ素数,すなわち 3 以上の素数) \(p\) が 4 で割ると 1 余るとき,\(p\) は 2 つの平方数の和として表される.

2平方定理については,詳しくは上のリンク先に記事がありますので,そちらをどうぞ.

以下が素数に関するオイラーの定理です.オイラーの名前が残っている数多くの定理のうちの一つです.

定理.

奇素数 \(p\) について,

\begin{align*}
p\equiv 1 \pmod{4}
\end{align*}

\begin{align*}
x^2\equiv -1\pmod{p}
\end{align*}

が解を持つことは同値.

証明には,ウィルソンの定理フェルマーの小定理など,合同式についての有名な定理を用います.

証明.

まず,奇素数 \(p\) に対して,\(q=(p-1)/2\) とおくと,\(q\) は自然数であって \(p=2q+1\) となります.

[1] (\(\Rightarrow\)) の証明

\(p\equiv 1\pmod{4}\) より,\(q\) は偶数となるので,

\begin{align*}
(p-1)! &= \prod_{k=1}^{p-1} k\\
&= \left(\prod_{k=1}^qk\right)\left(\prod_{k=q+1}^{p-1}k\right)\\
&= \left(\prod_{k=1}^qk\right)\left\{\prod_{k=1}^{p-q-1}(q+k)\right\}\\
&\equiv  \left(\prod_{k=1}^qk\right)\left\{\prod_{k=1}^{p-q-1}(q+k-p)\right\}\\
&\equiv \left(\prod_{k=1}^qk\right)\left\{\prod_{k=1}^q(k-q-1)\right\}\\
&\equiv \left(\prod_{k=1}^qk\right)\left\{\prod_{k=1}^q(-k)\right\}\\
&\equiv q!\times q!\times(-1)^q\\
&\equiv (q!)^2 \pmod{p}.
\end{align*}

一方で,ウィルソンの定理より \((p-1)!\equiv -1\) なので,\((q!)^2\equiv -1\) となります.

[2] (\(\Leftarrow\)) の証明

\(x^2\equiv -1\pmod{p}\) の解を \(x = x_1\) とします.

まず,\(x_1\) と \(p\) が互いに素であることを示します.

\(x_1, p\) の最大公約数を \(M\) として,\(x_1=M\alpha, p=M\beta\) とします.

ある整数 \(k\) が存在して

\begin{align*}
x_1^2=-1+kp
\end{align*}

が成り立つので,代入,変形すると

\begin{align*}
M\alpha^2-k\beta=-\frac{1}{M}
\end{align*}

となり,左辺は整数なので,右辺も整数となることから \(M=1\).

よって,\(x_1, p\) は互いに素.

ここで,

\begin{align}
x_1^{p-1} &= x_1^{2q}\nonumber\\
&= (x_1^2)^q\nonumber\\
&\equiv (-1)^q\pmod{p}\tag{\(\ast_1\)}
\end{align}

また,\(x_1, p\) が互いに素なので,フェルマーの小定理 を用いて

\begin{align}
x_1^{p-1}\equiv 1\pmod{p}\tag{\(\ast_2\)}
\end{align}

なので,(\(\ast_1\)), (\(\ast_2\)) から

\begin{align*}
(-1)^q\equiv 1\pmod{p}
\end{align*}

\(p\geq 3\) であるから,この式が成り立つとき,\(q\) は偶数.

よって,\(p=2q+1\) は 4 で割ると 1 余る.

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加