6

平方剰余と Euler の規準

824
0
$$$$

前提知識 : 合同式
$\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 記号を次のように導入する.

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$

Wilsonの定理

任意の素数$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}
のように成る.

Eulerの規準

任意の整数$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$

Fermatの小定理

任意の整数$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}$

投稿日:20201110

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

ゆう
ゆう
143
11125
好きな整数は 0, 1, 1, φ, 2, 5, 6, 12, 89 など. || フィボナッチ数列 bot (@Aureus_N) 管理人. || hatena blog || indeterminate equations involving Fibonacci numbers || Disquisitiones Arithmeticae...

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中