数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

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

定義・定理・公式

スポンサードリンク

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

ここでは，(フェルマーの) 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 余る．