素数の因数分解

T_NAKAさんのところにあった問題
６で割って１余る素数の分解 T_NAKAの阿房ブログ/ウェブリブログ
を考えてみた。

素数 p = 2011,\;2017 を正整数 m,\;n で p=m^2+mn+n^2 という形に表せという問題。
\omega を 1 の原始3乗根として
\Large m^2+mn+n^2 = (m-\omega n)(m-\omega^2 n)
だから、p を {\mathbb Z}[\omega] で分解すればいい。

まず p=2011 の場合。
いきなりだが 2^{(2011-1)/3} = 2^{670} を {\rm mod}\;2011 で計算する。
\Large 2^{670}\equiv -206\;({\rm mod}\;2011)\vspace{30pt}
フェルマーの小定理から整数 a が 2011 の倍数でなければ
\Large a^{2010}\equiv 1\;({\rm mod}\;2011)
なので
\Large (-206)^3 \equiv (2^{670})^3 = 2^{2010} \equiv 1\;({\rm mod}\;2011)\vspace{30pt}
だから (-206)^3 -1 は 2011 の倍数。これを分解して
\Large (-206)^3-1 = (-206-1)(-206-\omega)(-206-\omega^2)\vspace{30pt}
-206-1 は 2011 の倍数ではないので*1 *2、(-206-\omega)(-206-\omega^2) が 2011 の倍数。実際計算してみると
\Large (-206-\omega)(-206-\omega^2)=(-206)^2+(-206)+1=42231=3\cdot7\cdot2011
分かりづらいから
\Large \omega=\frac{-1+\sqrt{-3}}{2},\;\omega^2=\frac{-1-\sqrt{-3}}{2}
で書き直せば
\Large (411+\sqrt{-3})(411-\sqrt{-3}) = 4\cdot 3\cdot 7\cdot 2011\vspace{25pt}
-(\sqrt{-3})^2 = 3 で辺々割って
\Large (1-137\sqrt{-3})(1+137\sqrt{-3}) = 4\cdot 7\cdot 2011\vspace{30pt}
(2+\sqrt{-3})(2-\sqrt{-3})=7 で辺々割って
\Large \frac{(1-137\sqrt{-3})(1+137\sqrt{-3})}{(2+\sqrt{-3})(2-\sqrt{-3})} = 4\cdot 2011\vspace{30pt}
左辺の分母の因数が分子のどっちに含まれてるか分からないから計算してみると
\Large \frac{1-137\sqrt{-3}}{2+\sqrt{-3}} = -\frac{409+275\sqrt{-3}}{7},\;\;\frac{1-137\sqrt{-3}}{2-\sqrt{-3}} = 59-39\sqrt{-3}
前は使えないが後ろが使える。同様に
\Large \frac{1+137\sqrt{-3}}{2+\sqrt{-3}} = 59+39\sqrt{-3}
だから結局
\Large (59-39\sqrt{-3})(59+39\sqrt{-3}) = 4\cdot 2011
\omega で書き直せば
\Large (10-39\omega)(10-39\omega^2) = 2011
展開すれば
\Large 10^2+10\cdot 39+39^2 = 2011
これで求まった。

p=2017 の場合。
上と同じように 2^{(2017-1)/3}=2^{672} を計算すると
\Large 2^{672}\equiv 1\;({\rm mod}\;2017)\vspace{30pt}
これは使えないが、672 は 3 の倍数だから 2^{672/3}=2^{224} を計算すると
\Large 2^{224}\equiv 294\;({\rm mod}\;2017)\vspace{30pt}
だから 294^{3}-1 は 2017 の倍数で、上と同様に
\Large (294-\omega)(294-\omega^2)=43\cdot 2017
ここで出てきた 43 も分解すると
\Large (6-\omega)(6-\omega^2)=43
試し割りすると
\Large \frac{294-\omega}{6-\omega^2} = 41-7\omega,\;\;\frac{294-\omega^2}{6-\omega} = 41-7\omega^2
であることが分かって、結局
\Large (41-7\omega)(41-7\omega^2)=2017
展開して
\Large 41^2+41\cdot 7+7^2=2017

*1:これが 2011 の倍数だったら、3^{670} などを試してみるところだった。

*2:ここは要するに mod 2011 での 1 の非自明な3乗根を求めている。