平方剰余と Euler の規準
前提知識 : 合同式
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
平方剰余
始めに, 以下の問題を見る.
平方数を$5$で割った余りとして有りうる数を全て挙げよ.
整数を$5$で割った余りは$0,1,2,3,4$の$4$通り在る. 任意の整数$x$に対し$x^2$と$(x+5)^2$などは合同であるため, $0,1,2,3,4$の平方を${\rm mod}\ 5$において考えればよろしく,
$$
\begin{align}
&0^2\equiv0\ \ ({\rm mod}\ 5)\\
&1^2\equiv1\ \ ({\rm mod}\ 5)\\
&2^2\equiv4\ \ ({\rm mod}\ 5)\\
&3^2\equiv4\ \ ({\rm mod}\ 5)\\
&4^2\equiv1\ \ ({\rm mod}\ 5)
\end{align}
$$のように$2$や$3$が現れることは無いことが判る. これは, 二乗を展開して
$$
\begin{align}
3^2=&\;(5-2)^2\\
\equiv&\;(-2)^2\equiv2^2\ \ ({\rm mod}\ 5),\\
4^2=&\;(5-1)^2\\
\equiv&\;(-1)^2\equiv1^2\ \ ({\rm mod}\ 5),
\end{align}
$$などと示せば了解されることであろう. このとき, $0,1,4$を$5$を法とした平方剰余, $2,3$を平方非剰余と言って区別する. 余りにも大雑把な言いかたであるが, 全ての剰余の内, 平方剰余であるのは「半分くらい」である.
続いて, 次の問題を取りあつかう.
$2$以上なる整数$n$であって, $n-1$が$n$を法とした平方剰余に成るようなものを全て決定せよ.
特に$n=10$のとき, これは, 十進法において一の位が$9$であるような平方数が存在するか否かを問い, $3^2=9$などによって$n=10$の条件への整合が示される. 後に見るように, $n$が奇素数のとき, 該当するのは$4$で割って$1$余るもののみであることが証明できる.
以上に見たように, 平方数をある法によって還元したさいの余りには制約が存在し, $x$についての合同方程式
$$
\begin{align}
x^2\equiv a\ \ ({\rm mod}\ n)
\end{align}
$$の解の存在性の解析は整数論において大いに役だつ. そこで, Legendre 記号を次のように導入する.
素数$p$と整数$a$に対して, $a$が$p$で割りきれないとき, $x$についての合同方程式
$$
\begin{align}
x^2\equiv a\ \ ({\rm mod}\ p)
\end{align}
$$が解を有することを$\displaystyle\left(\frac{a}{p}\right)=1$と, そうでないことを$\displaystyle\left(\frac{a}{p}\right)=-1$と表す. $a$が$p$で割りきれるときは, $\displaystyle\left(\frac{a}{p}\right)=0$と定める.
尚, 記号$\displaystyle\left(\frac{a}{p}\right)$は a p などと発音する.
以下が成りたつ.
$$
\begin{align}
&\left(\frac{5}{5}\right)=\left(\frac{0}{5}\right)=\left(\frac{-5}{5}\right)=0,\\
&\left(\frac{1}{5}\right)=\left(\frac{4}{5}\right)=1,\\
&\left(\frac{2}{5}\right)=\left(\frac{3}{5}\right)=-1.
\end{align}
$$
任意の素数$p$と整数$a,b$に対して, 以下が成りたつ.
$\quad(1)\ $$a\equiv b\ \ ({\rm mod}\ p)$$\Longrightarrow$$\displaystyle\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right).$
$\quad(2)\ $$\displaystyle\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right).$
$(1)\quad$定義から自明である.
$(2)\quad$後に示す Euler の規準を用いれば指数法則に帰結される. $\quad\Box$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
Euler の規準
任意の素数$p$と整数$a,b$に対して, $a$が$p$で割りきれないのならば, $ax\equiv b\ \ ({\rm mod}\ p)$を満足する整数$x$が$0\leqslant x\lt p$の範囲にただ一つ存在する.
このような$x$を$p$を法として$b/a$あるいは$b\cdot a^{-1}$などと書き, 特に$b=1$のときの$1/a$を, $p$を法とした$a$の逆元と言う. 有理数の体系にそのまま当てれば, いわゆる非零有理数の逆数に類似する.
$p$個の整数
$$
\begin{align}
0a,\ 1a,\ 2a,\ \ldots,\ (p-1)a
\end{align}
$$から二つを選んで引いた差は$p$の倍数とは成りえないから, これらを$p$で割った余りは相異なり, $0,1,2,\ldots,p-1$の全てが一度ずつ現れる. その中にただ一つだけ存在する, $b$と合同なるものを$xa$と成らしめれば, 示すべき$x$の存在が確かめられる. $\quad\Box$
任意の素数$p$に対して, $(p-1)!\equiv-1\ \ ({\rm mod}\ p)$が成りたつ.
$(p-1)!$の計算の順序を入れかえて, $1,2,3,\ldots,p-1$から二数の組を作り, 「約分」によって$1$を生じるように為せば
$$
\begin{align}
(p-1)!\equiv(p-1)\cdot1\cdot\cdots\cdot1\cdot1\equiv-1\ \ ({\rm mod}\ p)
\end{align}
$$と計算できる. ただし, 逆元が自身である二数$1,p-1$を特別に見なければならないことに留意せよ. $\quad\Box$
具体例を示そう. $p=5$のとき, $5$を法として
\begin{align}
&1\cdot1\equiv1\\
&2\cdot3\equiv1\\
(&3\cdot2\equiv1)\\
&4\cdot4\equiv1
\end{align}
であるから, 自身が自身の逆元である$1$と$4$を除けて「約分」すると
\begin{align}
(p-1)!\equiv4\cdot(3\cdot2)\cdot1\equiv-1\cdot1\cdot1\equiv-1
\end{align}
のように成る.
任意の整数$a$と奇素数$p$に対して, $\displaystyle\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\ \ ({\rm mod}\ p)$が成りたつ.
以下のように場合を分けて再び$(p-1)!\ {\rm mod}\ p$を計算する.
$(1)\quad$$\displaystyle\left(\frac{a}{p}\right)=-1$なるとき
$1,2,3,\ldots,p-1$から二数の組を$(p-1)/2$度作り, 「約分」によって$a$を生じるように為せば
$$
\begin{align}
(p-1)!\equiv a\cdot a\cdot\cdots\cdot a\equiv a^{\frac{p-1}{2}}\ \ ({\rm mod}\ p)
\end{align}
$$と計算でき, Wilson の定理と合わせれば証明が完了する. ただし, 仮定によって$x\cdot x\equiv a\ \ ({\rm mod }\ p)$は解を持たず, $1,2,3,\ldots,p-1$の全てが他のものと対を成すことに留意せよ.
$(2)\quad$$\displaystyle\left(\frac{a}{p}\right)=1$なるとき
同じように考えて, 方程式$x^2\equiv a\ \ ({\rm mod}\ p)$の「二つの」解を$x_0,\ p-x_0$と書くと
$$
\begin{align}
(p-1)!\equiv x_0\cdot(p-x_0)\cdot(a\cdot a\cdot\cdots\cdot a)\equiv-x_0^2\cdot a^{\frac{p-3}{2}}\equiv -a^{\frac{p-1}{2}}\ \ ({\rm mod}\ p)
\end{align}
$$と計算でき, Wilson の定理と合わせれば証明が完了する. $\quad\Box$
$(2)$において,
$$
\begin{align}
&x^2\equiv a\ \ ({\rm mod}\ p)\\
\Longleftrightarrow&\;x^2\equiv a_0^2\ \ ({\rm mod}\ p)\\
\Longleftrightarrow&\;(x+a_0)(x-a_0)\equiv0\ \ ({\rm mod}\ p)\\
\Longleftrightarrow&\;x-a_0\equiv0\ \ ({\rm mod}\ p)\ \mbox{または}\ x+a_0\equiv0\ \ ({\rm mod}\ p)
\end{align}
$$および$a_0\not\equiv-a_0\ \ ({\rm mod}\ p)$のため, 合同方程式$x^2\equiv a\ \ ({\rm mod}\ p)$の解である剰余$x$は「二個」である.
$a=-1$を代入すると次が得られる.
任意の奇素数$p$に対して, $\displaystyle\left(\frac{-1}{p}\right)=1$$\Longleftrightarrow$$p\equiv1\ \ ({\rm mod}\ 4)$が成りたつ.
Euler の規準から左辺は$(-1)^\frac{p-1}{2}\equiv1\ \ ({\rm mod}\ p)$に同値であって, さらにこれは$(p-1)/2$が偶数であることに等しい. $\quad\Box$
任意の整数$a$と素数$p$に対して, $a$が$p$で割りきれないのならば, $a^{p-1}\equiv1\ \ ({\rm mod}\ p)$が成りたつ.
たとえば$a=10,\ p=7$のとき$10^6\equiv1\ \ ({\rm mod}\ 7)$と成り, これは, 等比数列
$$
\begin{align}
1,\ 10,\ 100,\ 1000,\ \ldots
\end{align}
$$を${\rm mod}\ 7$で見れば,
$$
\begin{align}
1,\ 3,\ 2,\ 6,\ 4,\ 5,\ 1,\ 3,\ 2,\ 6,\ 4,\ 5,\ \ldots
\end{align}
$$のように, 少なくとも$6$項進めば元に戻る周期列と成ることを表現している. 十進法という視点で見れば, これは分数$1/7$の小数表示が$0.142857142857\cdots$と, 少なくとも$6$桁毎で周期することを表現するとも言いかえられる.
Euler の規準から$a^\frac{p-1}{2}\equiv\pm1\ \ ({\rm mod}\ p)$であり, 両辺を二乗すれば得られる. $\quad\Box$
Euler の規準の応用については次の記事で紹介している.
https://mathlog.info/articles/664
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
原始根を用いた証明
Euler の規準は, $p$の原始根$r$が存在することから容易に証明することができるため, 参考として紹介する.
$$
\begin{align}
&\exists x\in\mathbb{Z}[x^2\equiv a\ \ ({\rm mod}\ p)]\\
\Longleftrightarrow&\;2\mid{\rm Ind}_ra\\
\Longleftrightarrow&\;a^\frac{p-1}{2}\equiv1\ \ ({\rm mod}\ p).
\end{align}
$$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$
$\color{white}.\color{black}$