有限体(あまり計算)上の x²+y²=1 の解の個数
$x^2+y^2\equiv 1\pmod p$ ($p$ は素数、$x,y\in\{0,\ldots,p-1\}$) の解の個数を知りたい、というのが大体のモチベーションなのだ
高校生にもわかるように頑張って書いたのだ。有限体の具体例と定義については有限体の紹介を参照してほしいのだ
ここで求めたいのは $x^2+y^2=1$ で $x,y\in K$ としたときの解は全体でいくつか、という話なのだ。当然有限個な訳だから個数はきちんと求まるはずなのだ
ここからは有限体 $K$ の演算を $+,\ \times,\ -,\ \bullet^{-1}$ として話を進めるのだ。$\gdef\Fp{\Bbb{F}_p}\Fp$ 上の計算もやっぱり $+$ で表すので、どの体の話なのか注意深く読んでほしいのだ
記法
有限体 $K$ から $0$ を除いたものを $\gdef\Kt{K^\times}\Kt$ と書くことにするのだ
例えば $\gdef\Fpt{\Fp^\times}\Fpt$ と書いたら $\{1,\ldots,p-1\}$ のことなのだ
また、$a\in K,n\in\N$ に対して $a^n\coloneqq \underbrace{a\times a\times\cdots\times a}_\text{n times}$ とするのだ
有限集合 $X$ に対してその個数を $\#X$ と書くことにもするのだ
$\#\Bbb{F}_{11}=11,\ \#\{0,5,4\}=3$ なのだ
さらに $a\bmod n$ で「$a$ を $n$ で割った余り」を表すことにするのだ
代表元
有限体には素晴らしい性質があるのだ
有限体 $K$ には、ある元 $a\in\Kt $ が存在して全ての $b\in\Kt $ を $b=a^n$ の形で書けるのだ
この元を代表元と呼ぶことにするのだ。一つだけとは限らないから注意するのだ
例えば $\Bbb{F}_7$ だったら
<$>\begin{aligned} 1&=3^6\\ 2&=3^2\\ 3&=3^1\\ 4&=3^4\\ 5&=3^5\\ 6&=3^3 \end{aligned}<$>だから $3$ は $\Bbb{F}_7$ の代表元になるのだ
でも
<$>\begin{aligned} 1&=5^6\\ 2&=5^4\\ 3&=5^5\\ 4&=5^2\\ 5&=5^1\\ 6&=5^3 \end{aligned}<$>だから $5$ も $\Bbb{F}_7$ の代表元なのだ
この代表元を使って解の個数を求めていくのだ。その前にちゃんと証明しないといけないのだ
代表元の存在の証明
元の位数
$a\in\Kt$ に対して $a^n=1$ となる最小の自然数 $n\geq 1$ を位数といい、$\gdef\ord#1{{\lvert#1\rvert}}\ord{a}$ と書くのだ
例えば $5\in\Bbb{F}_{11}$ の累乗を考えると、$5^1=5,\ 5^2=3,\ 5^3=4,\ 5^4=9,\ 5^5=1$ なので $\ord{5}=5$ なのだ
あと簡単のために「割り切れる」に記号を与えるのだ:
$n,m\in\N$ に対して、「$m $ が $n$ で割り切れる」ことを「$n\prec m $」と書くのだ
簡単な事実として次が成り立つのだ:
位数の最小性
$a\in\Kt$ に対して $a^n=1$ だったら、$\ord{a}\prec n$ なのだ
もし割り切れなかったとしたら、<$>n=q\ord{a}+r\quad\bigl(0< r< \ord{a}\bigr)<$> と書けるから、
<$>\begin{aligned} a^r&=1^q\times a^r\\ &=a^{q\ord{a}+r}\\ &=1 \end{aligned}<$>となって $\ord{a}$ が最小であったことに矛盾してしまうのだ
次にこれを示すのだ:
位数最大の元
有限体 $K$ には位数が最大の元 $a\in\Kt$ が存在し、$b\in\Kt$ に対して $\ord{b}\prec\ord{a}$ なのだ
位数が最大の元は $K$ が有限集合だからとってこられるのだ。これを $a\in\Kt$ とするのだ
では $\ord{b}\nprec\ord{a}$ となるような $b\in\Kt$ があったとして矛盾を示すのだ
$g\coloneqq$「$\ord{a}$ と $\ord{b}$ の最大公約数」とし、これに対して帰納法を回すのだ
$g=1$ のとき、$(\frac ab)^{\ord{\frac ab}}=1$ より $a^\ord{\frac ab}=b^\ord{\frac ab}$ が言えるのだ
とくに $1=b^{\ord{\frac ab}\ord{b}}=a^{\ord{\frac ab}\ord{b}}$ より、$\ord a\prec\ord{\frac ab}\ord b$ で、$\ord a$ と $\ord b$ は互いに素だから $\ord a\prec\ord{\frac ab}$ と言っていいのだ
さらに $\ord a$ の最大性より、$\ord{\frac ab}\leq\ord a$ だから $\ord{\frac ab}=\ord a$ が言えたのだ
しかし、$(\frac ab)^{\ord a}=\frac{a^{\ord a}}{b^{\ord a}}=\frac 1{b^{\ord a}}\ne 1$ だから矛盾してしまったのだ……
$g\geq 2$ のとき、$c=b^g$ とすると、$g\ord c=\ord b$ となるので $\ord a$ と $\ord c$ の最大公約数を $h$ とすると、これは $g$ より小さいのだ。よって $c$ を $b$ に置き直せば帰納法の仮定より矛盾が確定したのだ
$n$ 次式の解の個数
$K$ 上の $n$ 次方程式の解の個数は高々 $n$ 個なのだ
帰納法で示すのだ
$n=1$ のとき $x+a=0$ には自明な解 $-a$ が一つだけ存在するのだ。それ以外の元 $b\ne a$ が解になったとすると $0\ne b-a=0$ となって矛盾するのだ
$n\geq 2$ のとき、$n$ 次方程式 $f(x)=0$ を考えるのだ。これに解がなかったとしたら命題は成立するからおしまいなのだ
もしこれに解があればその一つ $\alpha$ をとり、多項式の割り算*1の要領で $n-1$ 次多項式を使って $(x-\alpha)g(x)=0$ とできるのだ
このとき、$g(x)=0$ の解の個数は帰納法の仮定より高々 $n-1$ 個しかないので、これを $\{\beta_1,\ \beta_2,\ \ldots,\ \beta_l\}$ と置くのだ
$x\in K$ で $(x-\alpha)g(x)=0$ と仮定するのだ。$K$ は割り算が定義されているから、$x-\alpha$ か $g(x)$ のどちらかが絶対に $0$ になるのだ*2
したがって $x=\alpha$ または $x\in\{\beta_0,\ldots,\beta_l\}$ となって $f(x)=0$ 全体の解の個数が高々 $l+1$ 個*3、とくに高々 $n$ 個しかないことがわかるのだ
これでやっと上の命題が示せるのだ:
有限体 $K$ には、ある元 $a\in\Kt $ が存在して全ての $b\in\Kt $ を $b=a^n$ の形で書けるのだ
有限体 $K$ の位数が最大な元 $a\in\Kt$ を持ってくるのだ。まず、$a$ から $K$ の元がちょうど $\ord{a}$ 個作れることを示すのだ
まず、$1,a,a^2,\ldots,a^{\ord{a}-1}$ とすることで $\ord a$ 個の元が作れたのだ。これに重複はないのだ
$0\leq i< j<\ord{a}$ となる整数 $i,j$ をとるのだ
すると $0< j-i<\ord{a}$、とくに $a^{j-i}\ne 1$ より両辺に $a^i$ を掛けて $a^i\ne a^j$ なのだ
また、$\ord a$ の最大性から、$\Kt$ の元 $x$ は全て $x^{\ord a}=1$ を満たすはずなのだ。しかし $x^{\ord a}=1$ の解の個数は「$n$ 次方程式の解の個数」より高々 $\ord a$ 個しかなかったから、$\#\Kt\leq\ord a$ なのだ
よって $a^n$ の形で $\Kt$ の元全てが書き下せてしまったのだ
ここまでが有限体に知られる一般的な性質なのだ
ここから $x^2+y^2=1,\ (x,y\in K)$ の解の個数を求めていくのだ
$1=-1$ な有限体
有限体 $K$ で次は同値なのだ:
- $1=-1$
- $\ord{-1}=1$
- $\#K$ が偶数
まず、$1=-1$ だったら $\ord{-1}=\ord{1}=1$ なのだ
それに $\ord{-1}=1$ なら $1=(-1)^{\ord{-1}}=(-1)^1=-1$ なのだ
よって上 $2$ つの同値は明らかなのだ
また、$\#K$ が偶数 のとき、$\ord{-1}\ne 1$ とすると矛盾が導けるのだ
まず $(-1)^2=1$ より $\ord{-1}\prec 2$ だから、$\ord{-1}\ne 1$ なら $\ord{-1}=2$ しかあり得ないのだ
しかし $K$ の代表元 $a$ をとると、$\#K- 1=\#\Kt=\ord{-1}=2$ の倍数となって矛盾するのだ
さらに、$\#K$ が奇数のとき、$1\ne -1$ なのだ
$K$ の代表元 $a$ をとり、$b=a^{\frac{\#K- 1}2}\ne 1$ と置くのだ
このとき、
<$>\begin{aligned} (1-b)\times(1+b)&=1-b^2\\ &=1-1\\ &=0 \end{aligned}<$>より、$b\in\{1,-1\}$ だけれど、$b\ne 1$ より $1\ne -1$ なのだ
$-1$ の平方根
有限体 $K$に対して $x^2=-1$ となる $x\in K$ が存在する必要十分条件は、$\#K\bmod 4\ne 3$ なのだ
まず、$K$ の代表元 $a\in\Kt$ をとるのだ。このとき、$a^{\#\Kt}=a^{\ord{a}}=1$ なのだ
$\ord{-1}$ で場合分けするのだ。$1$ と $2$ の場合にわかれるのだ
$\ord{-1}=1$ のとき、$1=-1$ だから $1^2=1=-1$ で $x=1$ が解になるのだ
さらに $\#K$ は偶数だから $\#K\bmod 4\ne 3$ なのだ
つまり $\ord{-1}$ のときは必要十分性が「どちらも恒等的に真」として示せちゃったのだ
$\ord{-1}=2$ のとき、まず言えるのは $a^{\frac{\#K- 1}2}=-1$ なのだ
<$>\begin{aligned}
(a^{\frac{\#K- 1}2})^2&=a^{\#K- 1}\\
&=a^{\#\Kt}\\
&=1
\end{aligned}<$>
より、$a^{\frac{\#K- 1}2}$ は $x^2-1=0$ の解なのだ。しかし、$1\ne a^{\frac{\#K- 1}2}$ であり、かつ $x^2-1=0$ の解は $2$ つしかないから、$a^{\frac{\#K- 1}2}=-1$ が言えたのだ
次に、$\#K\bmod 4=1\ (\#K\bmod 4\ne 3)$ だとすると、$\frac{\#K- 1}4\in\N$ となるから、めでたく
<$>\begin{aligned} (a^{\frac{\#K- 1}4})^2&=a^{\frac{\#K- 1}2}\\ &=-1 \end{aligned}<$>となって解が存在したのだ
さらに、もし $x^2=-1$ の解が存在したとしたら $K$ の仮定($1\ne -1$)より $x\notin\{1,-1\}$ だから、$x^3=-x\ne 1,\ x^4=1$ より $\ord x=4$ となって、$-1$ と同じ理屈で $\ord a=\#K -1$ は $4$ の倍数、すなわち $\#K\bmod 4=1\ (\#K\bmod 4\ne 3)$ なのだ
よって $\ord{-1}$ に関わらず必要十分性が言えたので証明されたのだ
虚数単位の導入
$\#K\bmod 4=3$ のとき、$K(\gdef\i{\sqrt{-1}}\i$*4$)\coloneqq\{a+b\sqrt{-1}\mid a,b\in K\}$ は体になるのだ
さらに、$(a+b\i)^{\#K+1}=a^2+b^2$ なのだ
$0,1$ の性質や加法乗法の順番を入れ替えても結果が変わらないこと、分配法則などは高校の複素数でやったときと同じようになるから割愛するのだ
ここでは逆元が存在することを示すのだ。結論からいうと、$a+b\i\ne 0$ の逆元は $\dfrac{a-b\i}{a^2+b^2}$ なのだ
まず、$x^2+1=0$ の解は $K$ 上存在しないので、$a,b\in K$ に対して、$a\ne 0$ とすれば
<$>\begin{aligned} a^2+b^2&=a^2\times(1+(\dfrac ba)^2)\\ &\ne 0 \end{aligned}<$>となり、$b\ne 0$ のときも同様に証明できるから $\dfrac{a-b\i}{a^2+b^2}$ はちゃんと定義できるのだ
もちろん
<$>\begin{aligned} (a+b\i)\times\dfrac{a-b\sqrt{-1}}{a^2+b^2}&=\dfrac{(a+b\i)\times(a-b\i)}{a^2+b^2}\\ &=\dfrac{a^2-(b\i)^2}{a^2+b^2}\\ &=1 \end{aligned}<$>より逆元になっていることもたしかめられたのだ
では $(a+b\i)^{\#K+1}=a^2+b^2$ の証明をしていくのだ
まず、$K=\{k_1,k_2,\ldots,k_{\#K}\}$ とすると、$K=\{k_1+1,k_2+1,\ldots,k_{\#K}+1\}$ でもあることを利用して、
<$>\begin{aligned} k_1+k_2+\cdots+k_{\#K}&=(k_1+1)+(k_2+1)+\cdots+(k_{\#K}+1)\\ &=(k_1+k_2+\cdots+k_{\#K})+(\underbrace{1+1+\cdots+1}_{\#K \text{times}})\\ 0&=(\underbrace{1+1+\cdots+1}_{\#K \text{times}}) \end{aligned}<$>がわかるのだ
次に、$n\in\N$ に対して $n\in K$ を $\underbrace{1+1+\cdots+1}_{n\text{times}}$ と書くことにすると、二項定理より
<$>\begin{aligned} (a+b\i)^{\#K}&=a^\#K+\dbinom{\#K}{1}a^{\#K- 1}b\i\\ &+\dbinom{\#K}{2}a^{\#K-2}(b\i)^2\\ &+\cdots+\dbinom{\#K}{\#K- 1}a(b\i)+(b\i)^\#K \end{aligned}<$>だけど、$\#K\prec\dbinom{\#K}{k}\quad$($0< k< \#K$)、さらに $\#K\bmod 4=3$ であることを思い出すと、
<$>\begin{aligned} (a+b\i)^{\#K}&=a^{\#K}+(b\i)^{\#K}\\ &=a^{\#K -1}\times a+b^{\#K -1}\times b\times\i^{\#K}\\ &=a-b\i \end{aligned}<$>よって
<$>\begin{aligned} (a+b\i)^{\#K+1}&=(a+b\i)^{\#K}\times(a+b\i)\\ &=(a-b\i)\times(a+b\i)\\ &=a^2+b^2 \end{aligned}<$>が言えたのだ
全体の証明
有限体 $K$ に対して $x^2+y^2=1$ の解はちょうど $\#K-\sin\frac{\#K\pi}{2}$ 個なのだ
なんで $\sin$ が、とか思わないで欲しいのだ。$\#K$ が偶数のとき $\#K$ 個、$\#K \bmod 4=1$ のとき $\#K -1$ 個、$\#K\bmod 4=3$ のとき $\#K +1$ 個、っていうのをまとめただけなのだ
$2\prec\#K$ のとき、$x^2=1$ の解が $x=1$ であるからこの $2$ つの式が同値であることに注意すると、
<$>\begin{aligned} &&x^2+y^2&=1\\ &\Lrarr&x^2-xy-xy+y^2&=1\\ &\Lrarr&(y-x)^2&=1\\ &\Lrarr&y-x&=1\\ &\Lrarr&y&=x+1 \end{aligned}<$>より、任意の $a\in K$ に対して $(x,y)=(a,a+1)$ が解になることがわかるのだ。よって解は $\#K$ 個なのだ
$\#K\bmod 4=1$ のとき、$a^2=-1$ となる $a\in \Kt$ をとってくれば、$x^2+y^2=(x+ay)(x-ay)$ と書けるのがわかるのだ
$x+ay=b\in \Kt$ とすれば $1+1\ne 0$ だったから $(x,y)=(\frac{b+b^{-1}}2,\frac{b-b^{-1}}{2a})$ とでき、$b$ はどのようにとってもよかったから、解は $\#\Kt=\#K- 1$ 個なのだ
$\#K\bmod 4=3$ のとき、$K(\sqrt{-1})$ の代表元 $a\in K(\sqrt{-1})$ をとるのだ
このとき、$x^2+y^2=(x+y\i)^{\#K+1}$ だから、$x^2+y^2=1\quad$($x,y\in K$) という式と $z^{\#K+1}=1\quad$($z\in K(\i)$) と言う式の意味は $z=x+y\i$ とすれば同じなのだ
また、$z=a^{n(\#K -1)}\quad$($0\leq n\leq\#K$) を考えると、これは $z^{\#K+1}=1$ の解なのだ
<$>\begin{aligned}
z^{\#K+1}&=(a^{n(\#K -1)})^{\#K+1}\\
&=(a^{n(\#K+1)})^{\#K -1}\\
&=1\quad(a^{n(\#K+1)}\in K)
\end{aligned}<$>
これでちょうど $\#K+1$ 個の解が作れたわけだけど、$z^{\#K+1}=1$ の解はそもそも $\#K+1$ 個しかなかったからこれで全部なのだ
実際大学生なら最後の証明以外は一般に知られた事実だから、証明した当初は面白くて眠れなかったのだ
