quadratic_field.html

<title>二次体の整数論</title>
二次体$\mathbb{Q}(\sqrt{d})$の整数環を考えることで、問題が簡単になる場合がある。

<h3>ガウス整数</h3>
$\mathbb{Z}[i]:=\{a+bi|a,b\in\mathbb{Z}\}$はガウス整数と呼ばれている。
ガウス整数$\mathbb{Z}[i]$は余り付き割り算が行える（gcdが定義できてEuclidの互除法が計算できる）ことから素元分解の一意性が導かれる。

<h4>演習問題</h4>
<a href="https://yukicoder.me/problems/no/321">yukicoder No.321 (P,Q)-サンタと街の子供たち)</a><br>
ガウス整数を用いた夕叢霧香さんの解説が<a href="http://kirika-comp.hatenablog.com/entry/2018/03/12/210446">整数論テクニック集</a>のページ34にある。

<h3>$p=x^2+y^2$の整数解</h3>
$p$を奇素数とする。ガウス整数環$\mathbb{Z}[i]$で考えることにより$O(\log(p))$で求めることができる [1]。$p=3\pmod 4$のとき、解は存在しない($\bmod 4$で考えると分かる)。
$p=1 \pmod 4$のとき平方剰余の相互法則より、$-1$は平方剰余である。従って$u^2=-1 \bmod p$を満たす$u$が存在する。(適当な平方非剰余$k$をとり、$u = k^{(p-1)/4} \pmod p$とすればよい)。
このとき、ある$m$が存在して
$$u^2+1=mp\Leftrightarrow(u+i)(u-i)=mp$$
である。
<!--
$u$を絶対値最小剰余系で取ると、$u^2+1\leq (p-1)^2+1 \leq p(p-1)$より$m \lt p$とできる。
従ってガウス整数環で最小公倍数を取ると
$$\gcd(\mathrm{N}(u+i),\mathrm{N}(p))=\gcd(mp,p^2)=p$$
を満たす。
ただし$\mathrm{N}(a):=a\bar{a}$は$a\in\mathbb{Z}[i]$のノルムとする。
ノルムの乗法性$\mathrm{N}(ab)=\mathrm{N}(a)\mathrm{N}(b)$から
$\mathrm{N}(\gcd(a,b)) | \gcd(\mathrm{N}(a),\mathrm{N}(b))$
が成り立つ。従って$\mathrm{N}(\gcd(u+i))=1,p$となる。同様に$\mathrm{N}(\gcd(u-i))=1,p$だが
$\gcd(u^2+1,p)=p|\gcd(u+i,p)\gcd(u-i,p)$だから
-->
素元 $\pi \mid p$ を適当にとる。$\pi \mid p$ かつ $\pi \mid \alpha$（$\alpha$ は $u\pm i$ のうち都合の良い方）。
$p\nmid \alpha$ なので、$p\nmid \pi$。
$\mathrm{N}(p)=p^2$であるので$p$は2つの素元$p = \pi \pi'$に分解される。
これと $p\nmid \alpha$ より、$\gcd(p,\alpha) = \pi$である。従って$\gcd(u+i,p)=x+yi$となる$(x,y)$をとることで$x^2+y^2=p$となる組$(x,y)$が得られた。
ガウス整数の素元分解の一意性から、$(x,y)$は自明な重複($(y,x)$,$(-x,y)$,etc)を除いて一組に定まる。
計算量は$O(\log p)$である。
<br>
<h4>演習問題</h4>
<a href="https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=3182&mosmsg=Submission+received+with+ID+20304398">UVA 12031 - Summation of Four Squares</a><br>
与えられた$T(< 120000)$個の$n(< 10^{17})$について$n=x^2+y^2+z^2+w^2$を満たす$(x,y,z,w)$をそれぞれ求める問題(四平方数定理より必ず存在)。[1] で$O(\log^2 n)$のアルゴリズムが与えられている。

<br><br>
[1] Rabin, Michael O., and Jeffery O. Shallit. "Randomized algorithms in number theory." Communications on Pure and Applied Mathematics 39.S1 (1986): S239-S256.