ルジャンドル記号まわりについて理解したい

はじめに

突然だが、次のような問題について考察したい。

このような問題を脳死で解くためには「平方剰余」なるものをよく知っているとよい。この記事では、第一補充法則の証明を通して以前書いた記事の復習を行うとともに、平方剰余の扱いに慣れることのできるようなテクニックを記していく。

平方剰余とルジャンドル記号

平方剰余まわりの用語について定義する。

最初の問題に戻る

つまり、最初の問題「$p \mid x^2+5$なる$x$が存在する$p$の必要十分条件」とは、次のように言い換えられる。

武器の準備(4つの定理)

$p$を$3$以上の素数とし、$a,\ b$は$p$と互いに素である整数とする。また、$l$も$3$以上の整数であり、$p$と$l$は異なるとする。このとき、以下の4つの定理が成立：

一応場合分けをしないで次のように書くこともできる。
$${(\frac{l}{p})=(-1)^{\frac{p-1}{2}\cdot\frac{l-1}{2}}\cdot(\frac{p}{l})}$$

一応場合分けしないで次のように書くこともできる。

$${(\frac{-1}{p})=(-1)^{\frac{p-1}{2}}}$$

一応場合分けしないで次のように書くこともできる。

$${(\frac{2}{p})=(-1)^{\frac{p^2-1}{8}}}$$

これから注意してほしいことは、「$p=2$のときに注意しないといけないこと」「相互法則を使いたいときは$p\neq l$に注意しないといけないこと」である。これは次の例を見てもわかるだろう。

冒頭の問題を解いて性質に慣れる

では、冒頭の問題を解いてみよう。

おお、きれい。

類題を2つ解く

(解答)
$p=2,\ 7$は明らかに十分。以降、$p\neq2,\ 7$とする。

$(\frac{-7}{p})=(\frac{-1}{p})\cdot(\frac{7}{p})$で、第一補充法則と平方剰余の相互法則を考えると$p$を$\text{mod}\ 4$で場合分けすることになるが、今回は$\text{mod}\ 4$で$1$でも$3$でも結局$(\frac{-1}{p})\cdot(\frac{7}{p})=(\frac{p}{7})$となるため、$p\equiv1,\ 2,\ 4\ (\text{mod\ 7})$のときが必要十分。

よって、「$p\equiv0,\ 1,\ 2,\ 4\ (\text{mod}\ 7)$」が求まるものである。

(解答)
$p=2,\ 3$は明らかに十分。以降、$p\neq2,\ 3$とする。

$(\frac{6}{p})=(\frac{2}{p})\cdot(\frac{3}{p})$
今度は第二補充法則と平方剰余の相互法則を考えないといけないため、$p$を$\text{mod}\ 8$で分類するのがよい($3\equiv3\ (\text{mod}\ p)$より相互法則も$p$によって場合分けしないといけないから)。

• $p\equiv 1\ (\text{mod}\ 8)$のとき
  $(\frac{2}{p})=1$であり、$p\equiv 1\ (\text{mod}\ 4)$だから$(\frac{3}{p})=(\frac{p}{3})$でこれが$1$にならないといけないため$p\equiv1\ (\text{mod}\ 3)$
  したがって$p\equiv1\ (\text{mod}\ 24)$

$\\$

• $p\equiv 3\ (\text{mod}\ 8)$のとき
  $(\frac{2}{p})=-1$であり、$p\equiv 3\ (\text{mod}\ 4)$だから$(\frac{3}{p})=-(\frac{p}{3})$で$(\frac{p}{3})$が$1$にならないといけないため$p\equiv1\ (\text{mod}\ 3)$
  したがって$p\equiv19\ (\text{mod}\ 24)$

$\\$

• $p\equiv 5\ (\text{mod}\ 8)$のとき
  $(\frac{2}{p})=-1$であり、$p\equiv 1\ (\text{mod}\ 4)$だから$(\frac{3}{p})=(\frac{p}{3})$でこれが$-1$にならないといけないため$p\equiv2\ (\text{mod}\ 3)$
  したがって$p\equiv5\ (\text{mod}\ 24)$

$\\$

• $p\equiv 7\ (\text{mod}\ 8)$のとき
  $(\frac{2}{p})=1$であり、$p\equiv 3\ (\text{mod}\ 4)$だから$(\frac{3}{p})=-(\frac{p}{3})$で$(\frac{p}{3})$が$-1$にならないといけないため$p\equiv2\ (\text{mod}\ 3)$
  したがって$p\equiv23\ (\text{mod}\ 24)$

$\\$

以上より求まるものは「$p\equiv1,\ 2,\ 3,\ 5,\ 19,\ 23,\ (\text{mod}\ 24)$」である。

この手の問題は完全に「乗法性で分解する」→「$-1$や$2$の部分と、素数の部分に分かれる」→「相互法則で法をひっくり返す」で解ける。

ここまででなんとなくわかったと思うが、相互法則の気持ちは、「変数が法にあると考えにくいから、定数を法にもってくる」というところにある。

ちょっと難しい問題

(発想)
「〇〇の二乗」の形にしたい→平方完成

二次方程式の解の公式の導出を途中まで眺める。

これと全く同じことをしたらいいのでは...?

(解答)
$3x^2+3x+1\equiv0\ (\text{mod}\ p)$
$3x^2+3x\equiv-1\ (\text{mod}\ p)$
$36x^2+36x\equiv-12\ (\text{mod}\ p)$
$36x^2+36x+9\equiv-3\ (\text{mod}\ p)$
$(6x+3)^2\equiv-3\ (\text{mod}\ p)$

最初の式を見ると$p\neq2,\ 3$は明らか(最後の式は見ない！途中で$12$倍したから、$\text{mod}\ 2$や$3$で$0$をかけてる！)。よって$p\neq2,\ 3$で、$x$の係数と$6$は互いに素だから、$\text{mod}\ p$で$6x$は$p$通りの余りすべてになりうる(除算可能の証明やフェル小の証明、中国剰余定理の証明でやったやつ)。$+3$するのはダイヤルを平行移動させるだけだから無論$6x+3$は$\text{mod}\ p$で$p$通りのすべての値を取りうる。だから、結局は$(\frac{-3}{p})$を考えればいい。

参考1より、$(\frac{-3}{p})=(\frac{p}{3})$であり求まる条件は「$p\equiv1\ (\text{mod}\ 3)$」。

前記事の復習(第一補充定理を示す)

以下、$p$は$3$以上の素数とする。

証明1. オイラーの規準を用いて示す

証明2. 場合分けして直接求める

さいごに

前回の記事 を真面目に読んでいた人にとってはたいへんドパガキ向けのものになったのではないでしょうか。

では最後に、まったくドーパミンの出ない復習問題を解いて終わりましょう。

(解答)
$(\frac{22}{2027})=(\frac{2}{2027})\cdot(\frac{11}{2027})=-1\cdot(-1)\cdot(\frac{2027}{11})=(\frac{25}{11})=1$より、存在する。
ちなみに、「参考2」を用いたら少し早くなるし、$1001=7\cdot11\cdot13$を知っていたらもっと早くなる。

ほんとにさいごに、今回の記事は「第30回　高校生のための仙台数学セミナー」に参加して実際に解いてきた問題を参考に書かせていただきました。セミナーでは補充法則の証明(この記事には書いてないですが、第二補充法則や平方剰余の相互法則の証明も)を、いい感じに誘導をつけて問題にしていたので楽しかったです。ですからこの記事に書かれてある証明は一応自分が頑張って考えたものになります。誤りがあったらすみません。

ラグランジュ記号周りの諸定理をもちいないと解けない問題、は基本的にどこでも出ないかな...と思いつつも、一応記事にしておきました。平方剰余なんて、「$\text{mod}\ 3$で$x^2$は$2$にならない」ぐらいに認識しておけばどうにでもなります。よければ高評価を押してくださると嬉しいです。

ありがとうございました。