元祖ワシ的日記

一つ前のエントリで8N+1型以外の素数についての平方根の計算方法を解説しました。8N+1については同じような考えで求めようとしてもなかなかうまくいきません。
\[
a^n = \pm a　（ただしnは偶数）
\]

の形になかなか持ち込めないのがその要因です。今まで考えきた演算は$p$での剰余をもって演算するもので代数学的には$F_p$で演算と呼ばれるものです。$F_p$は$p$個の元からなる有限の集合で、その元同士に加減乗除が定義されているものです。この空間で演算をしている限りこの問題をクリアすのはどうも不可能なようです。そこで発想をちょっと変えて$F_p$ではなく$F_q$で考えることにします。$F_q$とは$F_p$の世界で既約な方程式の根を追加した体（加減乗除がうまく定義された集合）です。$F_p$は$p$個の元からなる体ですが、$F_q$は$q$個の元からなるので$F_q$と表現します。今回はちなみに$q=p^2$なので、$F_{p^2}$と記述するのが正確なのかもしれませんが、とりあえず$F_q$と表現しておきます。なんか難しいこと言ってますが発想としては簡単で$F_p$での平方根が存在しない数の平方根があると仮定してそれを追加したもの・・とゆるく考えておけばよいかと思います。

例えば有理数においても$2$の平方根は存在しませんが、仮にそれを$\sqrt{2}$と書くとすれば
\[
x+y\sqrt{2}
\]
という数の集合を考えることができてその集合に対して加減乗除が定義できます。例えば上記の数は二乗することが可能で二乗した結果は

\[
(x^2+2y^2 )+ (2xy)\sqrt{2}
\]

であってその結果もまた $x + y\sqrt{2}$の形に書けることがわかります。つまり$x+y\sqrt{2}$の形の集合を考えれば全ての加減乗除はその内部で閉じておりまた完結していることになります。

$F_q$もそれと同じ原理を用います。$F_p$から平方非剰余の数を$T$1つ選びその平方根があると仮定してそれを$\sqrt{T}$と表すことにし、この数を$F_p$に追加します。この集合に対して加減乗除が成立するためには
\[
x+y\sqrt{T}
\]と表すことができる数全て集めれば証明は割愛しますが十分で実際演算が閉じてうまく定義できることがわかります。xの選び方はp通りyの選び方はp通りですからこの体は$p^2$個の元からなることになります。この$q=p^2$とするとこの集合に対してもフェルマーの小定理が存在し

\[
x^q=x
\]

が成立することが知られています。つまり$F_q$では$q$乗すると元に戻ります。ところで$F_p$では

\[
x^p=x
\]

が成立しました。したがって$F_q$で任意の元を$p$乗すると、$F_p$に含まれる数はその位置を変えません（固定される）。しかし$F_p$に含まれない数はそうではなく、別な数に移動しますがその数は共役元になることが知られています。つまり
\[
(x+y\sqrt{T})^p = (x-y\sqrt{T})
\]
です。となれば$F_q$では任意の元を$p+1$乗すると

\[
(x+y\sqrt{T})^{p+1} = (x+y\sqrt{T})(x-y\sqrt{T}) = x^2 -y^2 T
\]

となりその数がなんであり$F_p$に属することになります。今

\[
x^2 -y^2 T=a
\]
となるようにうまく$x,y$を選ぶことができれば$p+1$は奇数ですから

\[
(x+y\sqrt{T})^\frac{p+1}{2}
\]

がその平方根になります。仮に$y$を1とすれば

\[
T= x^2 -a
\]

よってこの$T$が平方非剰余であるものを選んでその$\frac{p+1}{2}$乗を計算すればそれが答えになります。なお計算上は$x$と$y$だけが重要で$\sqrt{T}$が何ものであるかとは気にする必要がなく、$x, y$のペアでのみ演算をし$T$は二乗したら$T$となる数とゆるく考えておけば問題ありません。つまり単純に無理数の$\sqrt{T}$と考えても問題ないということになります。

例)
$p=41$とし$8$の平方根を考えます。$5^2-8=17$は非平方剰余です。よって$F_{1681}$で考えることにより
\[
(5+\sqrt{17})^{21}
\]
が答えになります。

実際計算をしてみると
\[
\begin{eqnarray}
(5+\sqrt{17})^2=(1+10\sqrt{17})\\
(5+\sqrt{17})^4=(20+20\sqrt{17})\\
(5+\sqrt{17})^8=(25+21\sqrt{17})\\
(5+\sqrt{17})^{16}=(4+25\sqrt{17})
\end{eqnarray}
\]
ですので
\[
(5+\sqrt{17})^{16}(5+\sqrt{17})^{4}(5+\sqrt{17})^{1} =34
\]

となります。

数が膨れあがらないのはその都度41で係数の剰余を取っているからです。また21回掛け合わせる必要はなく21は16+4+1ですから16乗、4乗、1乗したものを掛け合わせれば十分です。

余談）
$F_p$のような体を有限体（要素の数が有限なので）と言いますがその要素の数（位数とよぶ）は必ず$p$の冪であり、また$p$の冪の有限体は必ず存在することがわかっています。