平方剰余と Euler の規準

957

前提知識 : 合同式
$.$
$.$
$.$
$.$
$.$
$.$

平方剰余

始めに, 以下の問題を見る.

平方数を $5$ で割った余りとして有りうる数を全て挙げよ.

整数を $5$ で割った余りは $0, 1, 2, 3, 4$ の $4$ 通り在る. 任意の整数 $x$ に対し $x^{2}$ と $(x + 5)^{2}$ などは合同であるため, $0, 1, 2, 3, 4$ の平方を $m o d 5$ において考えればよろしく,
$\begin{aligned} 0^{2} \equiv 0 (m o d 5) \\ 1^{2} \equiv 1 (m o d 5) \\ 2^{2} \equiv 4 (m o d 5) \\ 3^{2} \equiv 4 (m o d 5) \\ 4^{2} \equiv 1 (m o d 5) \end{aligned}$ のように $2$ や $3$ が現れることは無いことが判る. これは, 二乗を展開して
$\begin{aligned} 3^{2} = & (5 - 2)^{2} \\ \equiv & (- 2)^{2} \equiv 2^{2} (m o d 5), \\ 4^{2} = & (5 - 1)^{2} \\ \equiv & (- 1)^{2} \equiv 1^{2} (m o d 5), \end{aligned}$ などと示せば了解されることであろう. このとき, $0, 1, 4$ を $5$ を法とした平方剰余, $2, 3$ を平方非剰余と言って区別する. 余りにも大雑把な言いかたであるが, 全ての剰余の内, 平方剰余であるのは「半分くらい」である.

続いて, 次の問題を取りあつかう.

$2$ 以上なる整数 $n$ であって, $n - 1$ が $n$ を法とした平方剰余に成るようなものを全て決定せよ.

特に $n = 10$ のとき, これは, 十進法において一の位が $9$ であるような平方数が存在するか否かを問い, $3^{2} = 9$ などによって $n = 10$ の条件への整合が示される. 後に見るように, $n$ が奇素数のとき, 該当するのは $4$ で割って $1$ 余るもののみであることが証明できる.

以上に見たように,　平方数をある法によって還元したさいの余りには制約が存在し, $x$ についての合同方程式
$\begin{array}{r} x^{2} \equiv a (m o d n) \end{array}$ の解の存在性の解析は整数論において大いに役だつ. そこで, Legendre 記号を次のように導入する.

Legendre記号

素数 $p$ と整数 $a$ に対して, $a$ が $p$ で割りきれないとき, $x$ についての合同方程式
$\begin{array}{r} x^{2} \equiv a (m o d p) \end{array}$ が解を有することを $(\frac{a}{p}) = 1$ と, そうでないことを $(\frac{a}{p}) = - 1$ と表す. $a$ が $p$ で割りきれるときは, $(\frac{a}{p}) = 0$ と定める.

尚, 記号 $(\frac{a}{p})$ は a p などと発音する.

以下が成りたつ.
$\begin{aligned} (\frac{5}{5}) = (\frac{0}{5}) = (\frac{- 5}{5}) = 0, \\ (\frac{1}{5}) = (\frac{4}{5}) = 1, \\ (\frac{2}{5}) = (\frac{3}{5}) = - 1. \end{aligned}$

任意の素数 $p$ と整数 $a, b$ に対して, 以下が成りたつ.
$(1)$ $a \equiv b (m o d p)$ $⟹$ $(\frac{a}{p}) = (\frac{b}{p}) .$
$(2)$ $(\frac{a b}{p}) = (\frac{a}{p}) (\frac{b}{p}) .$

$(1)$ 定義から自明である.

$(2)$ 後に示す Euler の規準を用いれば指数法則に帰結される. $◻$

$.$
$.$
$.$
$.$
$.$
$.$

Euler の規準

逆元の存在

任意の素数 $p$ と整数 $a, b$ に対して, $a$ が $p$ で割りきれないのならば, $a x \equiv b (m o d p)$ を満足する整数 $x$ が $0 ⩽ x < p$ の範囲にただ一つ存在する.

このような $x$ を $p$ を法として $b / a$ あるいは $b \cdot a^{- 1}$ などと書き, 特に $b = 1$ のときの $1 / a$ を, $p$ を法とした $a$ の逆元と言う. 有理数の体系にそのまま当てれば, いわゆる非零有理数の逆数に類似する.

$p$ 個の整数
$\begin{array}{r} 0 a, 1 a, 2 a, \dots, (p - 1) a \end{array}$ から二つを選んで引いた差は $p$ の倍数とは成りえないから, これらを $p$ で割った余りは相異なり, $0, 1, 2, \dots, p - 1$ の全てが一度ずつ現れる. その中にただ一つだけ存在する, $b$ と合同なるものを $x a$ と成らしめれば, 示すべき $x$ の存在が確かめられる. $◻$

Wilsonの定理

任意の素数 $p$ に対して, $(p - 1)! \equiv - 1 (m o d p)$ が成りたつ.

$(p - 1)!$ の計算の順序を入れかえて, $1, 2, 3, \dots, p - 1$ から二数の組を作り, 「約分」によって $1$ を生じるように為せば
$\begin{array}{r} (p - 1)! \equiv (p - 1) \cdot 1 \cdot \dots \cdot 1 \cdot 1 \equiv - 1 (m o d p) \end{array}$ と計算できる. ただし, 逆元が自身である二数 $1, p - 1$ を特別に見なければならないことに留意せよ. $◻$

具体例を示そう. $p = 5$ のとき, $5$ を法として
$\begin{aligned} 1 \cdot 1 \equiv 1 \\ 2 \cdot 3 \equiv 1 \\ ( & 3 \cdot 2 \equiv 1) \\ 4 \cdot 4 \equiv 1 \end{aligned}$
であるから, 自身が自身の逆元である $1$ と $4$ を除けて「約分」すると
$\begin{array}{r} (p - 1)! \equiv 4 \cdot (3 \cdot 2) \cdot 1 \equiv - 1 \cdot 1 \cdot 1 \equiv - 1 \end{array}$
のように成る.

Eulerの規準

任意の整数 $a$ と奇素数 $p$ に対して, $(\frac{a}{p}) \equiv a^{\frac{p - 1}{2}} (m o d p)$ が成りたつ.

以下のように場合を分けて再び $(p - 1)! m o d p$ を計算する.

$(1)$ $(\frac{a}{p}) = - 1$ なるとき
$1, 2, 3, \dots, p - 1$ から二数の組を $(p - 1) / 2$ 度作り, 「約分」によって $a$ を生じるように為せば
$\begin{array}{r} (p - 1)! \equiv a \cdot a \cdot \dots \cdot a \equiv a^{\frac{p - 1}{2}} (m o d p) \end{array}$ と計算でき, Wilson の定理と合わせれば証明が完了する. ただし, 仮定によって $x \cdot x \equiv a (m o d p)$ は解を持たず, $1, 2, 3, \dots, p - 1$ の全てが他のものと対を成すことに留意せよ.

$(2)$ $(\frac{a}{p}) = 1$ なるとき
同じように考えて, 方程式 $x^{2} \equiv a (m o d p)$ の「二つの」解を $x_{0}, p - x_{0}$ と書くと
$\begin{array}{r} (p - 1)! \equiv x_{0} \cdot (p - x_{0}) \cdot (a \cdot a \cdot \dots \cdot a) \equiv - x_{0}^{2} \cdot a^{\frac{p - 3}{2}} \equiv - a^{\frac{p - 1}{2}} (m o d p) \end{array}$ と計算でき, Wilson の定理と合わせれば証明が完了する. $◻$

$(2)$ において,
$\begin{aligned} x^{2} \equiv a (m o d p) \\ ⟺ & x^{2} \equiv a_{0}^{2} (m o d p) \\ ⟺ & (x + a_{0}) (x - a_{0}) \equiv 0 (m o d p) \\ ⟺ & x - a_{0} \equiv 0 (m o d p) または x + a_{0} \equiv 0 (m o d p) \end{aligned}$ および $a_{0} ≢ - a_{0} (m o d p)$ のため, 合同方程式 $x^{2} \equiv a (m o d p)$ の解である剰余 $x$ は「二個」である.

$a = - 1$ を代入すると次が得られる.

平方剰余の第一補充則

任意の奇素数 $p$ に対して, $(\frac{- 1}{p}) = 1$ $⟺$ $p \equiv 1 (m o d 4)$ が成りたつ.

Euler の規準から左辺は $(- 1)^{\frac{p - 1}{2}} \equiv 1 (m o d p)$ に同値であって, さらにこれは $(p - 1) / 2$ が偶数であることに等しい. $◻$

Fermatの小定理

任意の整数 $a$ と素数 $p$ に対して, $a$ が $p$ で割りきれないのならば, $a^{p - 1} \equiv 1 (m o d p)$ が成りたつ.

たとえば $a = 10, p = 7$ のとき $10^{6} \equiv 1 (m o d 7)$ と成り, これは, 等比数列
$\begin{array}{r} 1, 10, 100, 1000, \dots \end{array}$ を $m o d 7$ で見れば,
$\begin{array}{r} 1, 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, \dots \end{array}$ のように, 少なくとも $6$ 項進めば元に戻る周期列と成ることを表現している. 十進法という視点で見れば, これは分数 $1 / 7$ の小数表示が $0.142857142857 \dots$ と, 少なくとも $6$ 桁毎で周期することを表現するとも言いかえられる.

Euler の規準から $a^{\frac{p - 1}{2}} \equiv \pm 1 (m o d p)$ であり, 両辺を二乗すれば得られる. $◻$

Euler の規準の応用については次の記事で紹介している.

https://mathlog.info/articles/664

$.$
$.$
$.$
$.$
$.$
$.$

原始根を用いた証明

Euler の規準は, $p$ の原始根 $r$ が存在することから容易に証明することができるため, 参考として紹介する.
$\begin{aligned} \exists x \in Z [x^{2} \equiv a (m o d p)] \\ ⟺ & 2 ∣ {I n d}_{r} a \\ ⟺ & a^{\frac{p - 1}{2}} \equiv 1 (m o d p) . \end{aligned}$
$.$
$.$
$.$
$.$
$.$
$.$

投稿日：2020年11月10日

この記事を高評価した人

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

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

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

ゆう

148

13303

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

他の人のコメント

コメントはありません。

読み込み中

ゆう

平方剰余と Euler の規準

平方剰余
Euler の規準
原始根を用いた証明