mod pでの2次方程式
この記事は
日曜数学 Advent Calendar 2020
の17日目の記事です。
日曜数学Advent Calender初日のtsujimotterさんによる
類体論入門
と関係する内容として、$\mod p$での$2$次方程式の解の個数についてのお話をします。
tsujimotterさんの記事の方が豊富な内容を含んでいますが、この記事も合わせてお読みいただくとより楽しめるのではないかと思います。
前提知識は$2$次方程式と合同式です。ここで紹介する話は係数$b,c$が整数であるような$2$次方程式$x^2+bx+c=0$の解の有無を実数の範囲ではなく$\mod p$で考えることです。
$2$次方程式の実数解の個数
はじめに係数$b, c$が実数の場合の$2$次方程式$x^2+bx+c=0$の実数解の個数について復習する。$2$次方程式の解は、$D=b^2-4c$として $$\begin{eqnarray} x=\frac{-b\pm\sqrt{D}}{2}\end{eqnarray}$$で与えられる。
実数の範囲に解が存在するか否かは判別式$D=b^2-4c$の正負でわかる。$D>0$であれば実数の範囲に$\pm\sqrt{D}$を持ち、$D<0$であれば実数の範囲に$\sqrt{D}$が存在しない。$D=0$の場合には解が一つになる。
$\mod p$で解の公式
では、本題である$b, c$が整数の場合の$2$次方程式$x^2+bx+c=0$が素数$p$について$\mod p$での解の個数を調べる。
解の公式は$p$が$2$でなければ同じように導出できる。まず平方完成するため、$\mod p$での$\dfrac{1}{2}$について準備する。
$p$が奇数ならば$\mod p$において$2$は逆数$\dfrac{1}{2}$を持つ。
$p$が奇数のとき$p+1$は偶数であるので、$n=\dfrac{p+1}{2}$は整数である。$2n=p+1=1\mod p$なので、この$n$が$\mod p$での$2$の逆数である。
つまり、$\dfrac{1}{2}=n=\dfrac{p+1}{2}$である。
平方完成により解の公式を導出しよう。 $$\begin{eqnarray} x^2+bx+c&=&(x+\frac{b}{2})^2-\frac{b^2}{4}+c\\ &=&0\\ (x+\frac{b}{2})^2&=&\frac{b^2-4c}{4}\\ x&=&-\frac{b}{2}\pm\frac{\sqrt{b^2-4c}}{2}\end{eqnarray}$$となる。この等式は全て$\mod p$での合同式であることに注意せよ。
次に、$\mod p$で$\sqrt{b^2-4c}$が存在するかだが、これが$p, b, c$に依存して変わる。$D=b^2-4c$を実数の場合と同様に判別式と呼ぶことにする。
$x^2+x+1=0$という方程式について考えよう。 これの判別式は$D=-3$である。
例えば$p=3$においては$D=0$となるため$x^2+x+1=0$は重解を持つ。
実際、$(x+2)^2=x^2+4x+4=x^2+x+1\mod 3$である。
$p=5$であれば$\mod 5$で$D=-3=2$は平方数ではないため解を持たない。
$p=7$であれば$\mod 7$で$D=-3=4=2^2$であるから、$x=-\dfrac{1}{2}\pm1=3\pm1$が解になる。
$p=2$の場合は上の解の公式は使えないので、この場合は別に扱うことにする。
$x^2+1$
では$x^2+1=0$を考えよう。 $D=-4$となる。$4=2^2$だから、結局$\sqrt{-1}$が存在するか否かが問題となる。もちろんこのことは解の公式を使わずとも$x^2=-1$と変形してもわかる。判別式を用いることで、$p\neq2$において重解を持たないことが明確になる。$\mod p$における$\sqrt{-1}$が存在について、tsujimotterさんの記事にあるとおり$\sqrt{-1}^4=1$であることを利用する。ここで、有限体の乗法群が巡回群であるという以下の事実を用いよう。
ある整数$x$が存在して、$\mod p$で$1, x, x^2,x^3,\ldots,x^{p-2}$は全て相異なり、さらに$x^{p-1}=1$となる。
$p=3$であれば、$\mod 3$で$2^2=4=1$である。
$p=5$であれば、$\mod 5$で$2^2=4, 2^3=8=3, 2^4=1$となる。
$p=7$であれば、$\mod 7$で$3^2=9=2, 3^3=6, 3^4=18=4, 3^5=12=5, 3^6=15=1$となる。
$p=13$であれば、$\mod 13$で$2^2=4, 2^3=8, 2^4=16=3, 2^5=6, 2^6=12=-1$となり、さらに$2^7=-2^1, 2^8=-2^2, 2^9=-2^3, 2^{10}=-2^4, 2^{11}=-2^5, 2^{12}=-2^6=1$となる。
このことから、$p-1$が$4$で割り切れることと$\sqrt{-1}$が$\mod p$で存在することが同値であることがわかる。
$p$を奇素数とする。
$p=1\mod 4$のとき$x^2+1=0$は$\mod p$で解を$2$個持ち、$p=3\mod 4$のとき$x^2+1=0$は$\mod p$で解を持たない。
$\sqrt{-1}$は$4$乗して初めて$1$になる数のうち一つである。上の事実から、$\mod p$において、$p-1$が$4$で割り切れる場合、$x^{(p-1)/4}$が条件を満たす。逆に$\sqrt{-1}$が存在したとすると、ある正の整数$k$を用いて$x^k=\sqrt{-1}$とかけ、さらにこの$k$は$\dfrac{p-1}{2}$より小さく取れる。この時$x^{4k}=\sqrt{-1}^4=1$となり$4k$が$p-1$の倍数とわかるが、上の$k$の条件から$4k=p-1$となって$p-1$が$4$で割り切れる。
上で紹介した事実、有限体の乗法群が巡回群であることについてはいずれ別の記事にします。
具体的に幾つかの場合を見てみよう。
$p=5$であれば、$2^2=4=-1\mod5$である。$p=13$であれば、$5^2=25=-1\mod13$である。
$p=3$なら$1^2=2^2=1\mod3$なので$x^2=-1\mod 3$なる$x$は存在しない。$p=7$なら$1^2=6^2=1, 2^2=5^2=4, 3^2=4^2=2\mod7$であるのでやはり$x^2=-1\mod7$なる$x$は存在しない。
$\sqrt{-7}$
次に、tsujimotterさんの記事で紹介されていた$\Q(\sqrt{-7})$の場合を考える。考えるべき二次方程式は$x^2+x+2=0$である。
$x^2+7=0$ではダメかということが気になるかもしれない。
この二つの間には判別式が$-7$になるか$-28$になるかの違いがある。$p\neq2$では$\mod p$での解の個数はどちらでも一緒である。
一方で$p=2$の場合には$x^2+7=0$は$\mod 2$での解は$x=1$が重解になるが、$x^2+x+2=0$は$\mod 2$での解の個数$x=0,1$の$2$個である。
この方程式の$\mod p$での解の個数が$2, 0$のいずれかであることが、$p\mod 7$で$1,2,4$か否かで判別できる。平方剰余の相互法則を知っていれば、$-7$が$\mod p$で平方数であるかという条件に$p\mod 7$が関係してくることがわかり、解の有無が$p\mod 7$で判別できることがわかる。平方剰余の相互法則については冒頭の動画でも簡単に紹介しています。
円分体的な見方についても考えてみよう。$1$の原始$7$乗根の有無について、まず上と同様に有限体の乗法群が巡回群であるという事実を用いれば、$p-1$が$7$で割り切れるかどうかが対応する。$p-1$が$7$で割り切れる、つまり$p=1\mod 7$の場合には$\mod p$で$1$の原始$7$乗根$\zeta_7$が存在することになり、tsujimotterさんの記事にも登場する式 $$\begin{eqnarray} \sqrt{-7}=(\zeta_7+\zeta_7^2+\zeta_7^4)-(\zeta_7^3+\zeta_7^5+\zeta_7^6)\end{eqnarray}$$を用いて$\sqrt{-7}$を持つことがわかる。
ところが$1$の原始$7$乗根がなくても$\sqrt{-7}$があることはありうる。それは$p=2,4\mod7$の場合である。上の例で出てきたように、$2,4$は$\mod 7$での平方数になっているが、これは実は$p^3-1$が$7$で割り切れるという条件になっている。この$3$は$\mod p$で$\sqrt{-7}$をもてば$3$次方程式の解として$\mod p$で$1$の原始$7$乗根を作ることができることと関係する。
上の事実についても詳しくは有限体についての説明が必要なので、別の機会に解説します。
素数の分解との関係
この記事で説明した$x^2+1=0 \mod p$の解の個数の話とtsujimotterさんの記事にある素数$p$の$\Z[i]$の分解の関係について、環の言葉を使って簡単に説明します。以下では環論についての基本的な知識を仮定します。
まず$x^2+1=0\mod p$は$\F_p[x]/(x^2+1)$という環を考えることに対応する。$p$が奇素数のとき、$x^2+1=0\mod p$の解の有無は$x^2+1$が$1$次式の積に因数分解できるかできないかに対応し、これが$\F_p[x]/(x^2+1)$が$2$つの体の直積になるか体になるかに対応する。
一方で、$\Z[i]$において$p$が素数のままであれば$\Z[i]/(p)$は体であり、$p$が$\Z[i]$における素数の積に分解するなら$\Z[i]/(p)$は$2$つの体の直積になる。
ところで上で出てきた二つの環$\F_p[x]/(x^2+1)$と$\Z[i]/(p)$は見た目は違うものの同じ構造を持つ環である。というのも、$\Z[i]=Z[x]/(x^2+1), \F_p=\Z/p$とそれぞれ表示することで、$\F_p[x]/(x^2+1)$と$\Z[i]/(p)$はいずれも$\Z[x]/(x^2+1, p)$と同型であることがわかる。
ちなみに$p=2$のとき、この環は$\F_2[x]/(x^2)$と同型になり、これは体でも体の直積でもない。
幾何的に考える
もう少し幾何的に考えることもできると思いますが、これについては改めて別の記事にしてみようと思います。