文献あり

整数が二次形式で表現できる条件と応用例

182

はじめに

　この記事では整数$n$がある整数$a,b,c,x,y$を用いて
$$n=ax^2+bxy+cy^2$$
と表せるための条件についてまとめていきます。
　この話については前にも二平方和定理の記事やとある記事でも解説しましたが、これらの記事はどうにも論理のパートが長く、何が重要で何が重要でないかが見えづらくなっています。しかし同記事で紹介されている事実はどれも面白いものばかりですので、この記事ではそれらの事実を鑑賞するとともにその活用例について簡単に紹介していきたいと思います。

語句や記号の紹介

二次形式

二次形式$f(x,y)=ax^2+bxy+cy^2$のことを単に$[a,b,c]$と表したりする。
$D=b^2-4ac$を$[a,b,c]$の判別式と言う。本記事では$D<0$の場合のみを扱う。
$\gcd(a,b,c)=1$を満たすとき$[a,b,c]$は原始的な二次形式であるという。
二次形式$f,g$が変換
$$\begin{pmatrix}X\\Y\end{pmatrix}=\M pqrs\begin{pmatrix}x\\y\end{pmatrix} \quad(p,q,r,s\in\Z,\,ps-qr=1)$$
によって$f(x,y)=g(X,Y)$と写り合うとき、$f$と$g$は(properに)同値であると言う。同値な二次形式は同じ判別式を持つ。
特に$f$を$f$自身に写すような変換のことを自己同型と言う。$f$が$a(x^2+y^2),a(x^2+xy+y^2)$と同値でなければ$f$の自己同型は$(X,Y)=\pm(x,y)$の$2$つで尽くされる。
$f$が原始的であればその自己同型の個数はその判別式$D$によって判別することができ、具体的には
$$w_D=\l\{\begin{array}{cl}6&D=-3\\4&D=-4\\2&D<-4\end{array}\r.$$
個となる。
また特別な場合は以下のようにimproperな自己同型を持つことにも注意したい。
- $f=[a,0,c]$のとき$(X,Y)=(x,-y)$
- $f=[a,a,c]$のとき$(X,Y)=(x+y,-y)$
- $f=[a,b,a]$のとき$(X,Y)=(y,x)$
判別式$D$の原始的な二次形式全体をproperに同値であるという関係で割った集合$C(D)$のことを類群と言い、その元の個数$h(D)$を類数と言う。
$|b|\leq a\leq c$および「$|b|=a$または$a=c$ならば$b\geq0$」を満たすとき$[a,b,c]$は簡約な二次形式であるという。判別式$D$の原始的かつ簡約な二次形式は類群$C(D)$の完全代表系を成す。
$n$が二次形式$f$によってproperに表現できるとは、互いに素な整数$x,y$を用いて$n=f(x,y)$と表せることを言う。

簡約化について

　与えられた二次形式$f=[a,b,c]$に対し、その簡約化は以下のように計算できる。

　簡単のため$a\leq c$とする。$a>c$なら変換$(X,Y)=(-y,x)$を施せばよい。
　このとき$|b+2ka|$が最小となるような整数$k$を取り変換$(X,Y)=(x+2ky,y)$を施したものを$[a,b',c']$とする。もし$|b'|\leq c'$であれば少し整形することで$f$の簡約化が得られる。もし$|b'|>c'$であればまた$|b'+2k'c'|$なる整数$k'$を取り変換$(X,Y)=(x,2k'x+y)$を施していく。
　このようにしていくことで$b$の絶対値は小さくなっていくので、最終的には簡約形式が得られることとなる。

　例えば判別式$-23$の二次形式$[108,349,282]$の簡約化は以下のように計算できる。
\begin{align*} [108,349,282] &\to[108,-83,16] &(X,Y)&=(x-2y,y)\\ &\to[3,13,16] &(X,Y)&=(x,3x+y)\\ &\to[3,1,2] &(X,Y)&=(x-2y,y)\\ &\to[2,-1,3] &(X,Y)&=(-y,x) \end{align*}
またこれらの変換を合成することで
\begin{align*} \begin{pmatrix}X\\Y\end{pmatrix} &=\M1{-2}01\M1031\M1{-2}01\M0{-1}10\begin{pmatrix}x\\y\end{pmatrix}\\ &=\M85{-5}{-3}\begin{pmatrix}x\\y\end{pmatrix} \end{align*}
という関係によって
$$108X^2+349XY+282Y^2=2x^2-xy+3y^2$$
が成り立つことがわかる。

クロネッカー記号

　整数$a,n\;(n>0)$に対してクロネッカー記号$(a|n)=(\frac an)$を以下のように定める。

奇素数$p$に対しては$(a|p)$をルジャンドル記号とする。
$p=2$のときは奇数$a$に対して$(a|2)=(-1)^{\frac{a^2-1}8}$とする。
$n=\prod_{p\mid n}p^{e_p}$と素因数分解されるときは$(a|n)=\prod_{p|n}(a|p)^{e_p}$とする。

クロネッカー記号は完全乗法的な関数となる。つまり任意の$a,b,m,n$に対し
$$\l(\frac{ab}n\r)=\bigg(\frac an\bigg)\bigg(\frac bn\bigg),\quad \bigg(\frac a{mn}\bigg)=\bigg(\frac am\bigg)\bigg(\frac an\bigg)$$
が成り立つ。
奇素数$p$に対して$(a+p|p)=(n|p)$が、$p=2$に対しては$(a+8|2)=(n|2)$が成り立つ。

クロネッカー記号の相互法則

　互いに素な整数$m,n$に対し$m=2^em',n=2^fn'$なる奇数$m',n'$を取ると
$$\bigg(\frac mn\bigg)\l(\frac n{|m|}\r)=(-1)^{\frac{m'-1}2\cdot\frac{n'-1}2}$$
が成り立つ。

定理集

　以下$f=[a,b,c]$は判別式$D$の正定値二次形式、つまり$D<0$かつ$a,c>0$であるものとする。また$n\geq0$とする。

$n$の表現の存在とその個数

　$n$のproperな表現$n=f(x_0,y_0)$に対し
・$0\leq m<2n$
・$m^2\equiv D\pmod{4n}$
・$f$はある$\begin{psmallmatrix}x_0\\y_0\end{psmallmatrix}=A\begin{psmallmatrix}1\\0\end{psmallmatrix}$なる変換によって$[n,m,l]\;(l=(m^2-D)/4n)$と同値
を満たすような整数$m$が一意に存在する。
　特に$n$が判別式$D$のなんらかの二次形式によってproperに表現できるためには合同方程式
$$m^2\equiv D\pmod{4n}$$
が解を持つことが必要十分である。

　$n$の$f$によるproperな表現の個数は
($f$の自己同型の個数)$\times$($[n,m,l]$が$f$と同値となるような$0\leq m<2n$の個数)
となる。

　$D$と互いに素な$n$に対し合同方程式
$$m^2\equiv D\pmod{4n}$$
の$0\leq m<2n$なる解の個数は
$$\prod_{p\mid n}(1+\l(\frac Dp\r))$$
個であり、これが$\neq0$となるためには$n$の任意の素因数$p$に対し$(D|p)=1$が成り立つことが必要十分である。

　類群$C(D)$の完全代表系を$f_1,f_2,\ldots,f_h$とおいたとき、$D$と互いに素な$n$に対し$n=f_k(x,y)$なる整数$(k,x,y)$の取り方($x,y$は互いに素とは限らない)は全部で
$$w_D\sum_{d|n}\l(\frac Dn\r)$$
通りとなる。
　特に素数$p$が$(D|p)=1$を満たすとき、自己同型の違いを除いて丁度$2$通りの表現$p=f_k(x,y),f_{k'}(z,w)$が存在する。

$f$による表現可能性

　$D$の$2$でない素因数を任意に取り$p$とおく。このとき$f$が表現できる任意の$n$に対して$(n|p)$は$0$でなければ$n$に依らず一定の値を取る。
　また$D=4D'$と書けるとき、
・$D'\equiv0,3\pmod4$であれば$(-1|n)$も
・$D'\equiv0,2\pmod8$であれば$\phantom{-}(2|n)$も
・$D'\equiv0,6\pmod8$であれば$(-2|n)$も
$0$でなければ一定の値を取る。

　上のように整数$n$や二次形式$f$に対して$\pm1$を対応させる写像のことを(判別式$D$の)指標と言う。
　いま$D$の$2$以外の素因数の個数を$r$とおくと、判別式$D$の二次形式に付随する指標の個数$\mu$は
$$\mu=\l\{\begin{array}{ll} r&D,D'\equiv1\pmod4\\ r+1&D'\equiv2,3\pmod4\;\mathrm{or}\;D'\equiv4\pmod8\\ r+2&D'\equiv0\pmod8 \end{array}\r.$$
となる。ただし$D\equiv0\pmod4$のとき$D'=D/4$とおくものとした。

　類群$C(D)$の完全代表系を$f_1,f_2,\ldots,f_h$と置いたとき、任意の指標$\chi$に対して$\chi(f)=\chi(f_k)$が成り立つような$k$は丁度$h(D)/2^{\mu-1}$個存在する。

まとめ

　$n$が$D$と互いに素なとき、$n$が原始的な二次形式$f$によってproperに表現できるためには、$n$の任意の素因数$p$に対し$(D|p)=1$が成り立つこと、および$f$に付随する任意の指標$\chi$に対し$\chi(f)=\chi(n)$が成り立つことが必要である。
　特に$h(D)=2^{\mu-1}$が成り立つときは十分でもあり、そのとき$n=f(x,y)$なる互いに素な整数の組$(x,y)$の取り方は全部で
$$w_D\prod_{p\mid n}(1+\l(\frac Dp\r))$$
通りとなる。

　$n$が$D$と互いに素なとき、$n$が原始的な二次形式$f$によって表現できるためには、$n$の無平方因子$N$が$f$によって(properに)表現できることが必要十分である。
　特に$h(D)=2^{\mu-1}$が成り立つとき、$n=f(x,y)$なる整数の組$(x,y)$の取り方は($0$でなければ)全部で
$$w_D\sum_{d|n}\l(\frac Dd\r)$$
通りとなる。

活用例

　テキトーに作った問題をテキトーに解いてみる。なお
$$2023=7\cdot17^2,\quad2024=2^3\cdot11\cdot23$$
と素因数分解できることに注意されたい。

　$2023=x^2+y^2$は整数解$(x,y)$を持たないことを示せ。

解答

　$2023$の無平方因子は$7$であり、
$$\l(\frac{-4}7\r)=\l(\frac{-1}7\r)=(-1)^{\frac{7-1}2}=-1$$
なので$2023$は判別式$-4$の二次形式によって表現することはできない。

　$2$は判別式$-20$の二次形式を用いて表現できるか。また表現できるとき$2=f(x,y)$なる簡約な二次形式$f$と整数の組$(x,y)$を全て求めよ。

解答

　合同方程式
$$m^2\equiv-20\equiv4\pmod{4\cdot2}$$
は$0\leq m<4$において$m=2$のみを解に持つ。
　またこれによって誘導される二次形式$[n,m,l]=[2,2,3]$は簡約なので
$$f=2x^2+2xy+3y^2,\quad(x,y)=(\pm1,0)$$
が求める表現となる。

　$11=x^2+xy+2y^2$の整数解$(x,y)$を全て求めよ。

解答

　簡単に得られる解として$(x,y)=(1,2)$がある。これに対してimproperな自己同型$(X,Y)=(x+y,-y)$を考えることで$4$つの解$(x,y)=\pm(1,2),\pm(3,-2)$が得られる($11$は素数なのでこれ以上表現は存在しない)。

　$37=2x^2+2xy+17y^2$の整数解$(x,y)$を全て求めよ。

解答

　$f=[2,2,17]$の判別式は$-132=-4\cdot33$であり、また$f(0,1)=17$より$(f|3)=-1$が成り立つが$(37|3)=1$より$37$は$f$によって表現することはできない。よって解は存在しない、が答えとなる。
　ちなみに$(-132|37)=(-33|37)=(4|37)=1$より$37$は判別式$-132$の二次形式によって表現することはでき、実際
$$37=f(\pm2,\pm1),\quad f=x^2+33y^2$$
(複号同順)という計$4$つの表現が存在する。

　$2023$は判別式$-84$の二次形式を用いてproperに表現できるか。また表現できるとき$2023=f(x,y)$なる簡約な二次形式$f$と互いに素な整数の組$(x,y)$を全て求めよ。

解答

$$\l(\frac{-84}{17}\r)=\l(\frac{-21}{17}\r)=\l(\frac{-4}{17}\r)=(-1)^{\frac{17-1}2}=1$$
および
$$-84\equiv0\pmod7$$
に注意すると合同方程式
$$m^2\equiv-84\pmod{4\cdot2023}$$
は$0\leq m<2\cdot2023$において丁度$2$個の解を持つことがわかる。
　また判別式$-84$の簡約二次形式は
$$f=x^2+21y^2,3x^2+7y^2,2x^2+2xy+11y^2,5x^2+4xy+5y^2$$
の$4$つによって尽くされ、これらに対応する指標$(f|3)$の値はそれぞれ
$$(f|3)=1,1,-1,-1$$
となるので$(2023|3)=(7|3)=1$に注意すると$2023=f(x,y)$と書けるなら
$$f=x^2+21y^2,3x^2+7y^2$$
である。
　いまこれらに対し$2023=f(x,y)$と表せれば$7\mid x$となるので$x=7x'$とおくと
$$17^2=7x'^2+3y^2,21x'^2+y^2$$
と変形できる。これらの二次形式に対応する指標はそれぞれ$(\cdot|7)=-1,1$となるので$(17^2|7)=1$より前者は不適であり、
$$17^2=21x'^2+y^2$$
と絞れる。あとは
$$21x'^2=(17-y)(17+y)$$
に注意すると$(x',y)=(3,10)$という解が浮かび上がってくるので求める解は
$$f=3x^2+7y^2,\quad(x,y)=(\pm 21,\pm10)$$
(複号任意)の$4$つとなる。

　$2024$は判別式$-2023$の二次形式を用いてproperに表現できるか。また表現できるとき$2024=f(x,y)$なる簡約な二次形式$f$と互いに素な整数の組$(x,y)$を一つ求めよ。

解答

\begin{align*} \l(\frac{-2023}2\r)&=\l(\frac{-7}2\r)=\l(\frac12\r)=1\\ \l(\frac{-2023}{11}\r)&=\l(\frac{-7}{11}\r)=\l(\frac4{11}\r)=1\\ \l(\frac{-2023}{23}\r)&=\l(\frac{-7}{23}\r)=\l(\frac{16}{23}\r)=1 \end{align*}
が成り立つので(自己同型込みで)丁度$2\cdot2^3=16$通りのproperな表現が存在するはずである。
　いま判別式$-2023$の簡約な二次形式は
\begin{align*} f&=x^2+xy+506y^2\\ &=2x^2\pm xy+253y^2\\ &=11x^2\pm xy+46y^2\\ &=22x^2\pm xy+23y^2\\ &=4x^2\pm3xy+127y^2\\ &=8x^2\pm5xy+64y^2\\ &=16x^2\pm5xy+32y^2\\ &=7x^2+7xy+74y^2\\ &=14x^2\pm7xy+37y^2\\ &=22x^2\pm21xy+28y^2 \end{align*}
の$18$で尽くされ、これらは指標$(f|17)$によって二通りに分類できる。
　また$(2024|17)=(1|17)=1$に注意すると整合する二次形式は
\begin{align*} f&=x^2+xy+506y^2\\ &=2x^2\pm xy+253y^2\\ &=4x^2\pm3xy+127y^2\\ &=8x^2\pm5xy+64y^2\\ &=16x^2\pm5xy+32y^2 \end{align*}
の$9$個である。これ無理かも。

解答(続き)

　諦めて合同方程式
$$m^2\equiv-2023\pmod{4\cdot2024}$$
を解いてみる。これは$3$つの合同方程式
\begin{align*} m^2\equiv-2023&\equiv25\pmod{32}\\ m^2\equiv-2023&\equiv1\pmod{11}\\ m^2\equiv-2023&\equiv1\pmod{23} \end{align*}
に分解できるので例えば
\begin{align*} m&\equiv5\cdot(16+1)\equiv-11\pmod{32}\\ m&\equiv1\pmod{11}\\ m&\equiv1\pmod{23} \end{align*}
に対応する解を考えると
$$253\cdot11=32\cdot87-1$$
から
$$m=253\cdot132+1\equiv253\cdot4+1=1013\pmod{4\cdot2024}$$
と求まる。
　いま$[2024,1013,127]$は変換$(X,Y)=(x,-4x+y)$によって$[4,-3,127]$に写るので
$$f=4x^2-3xy+127y^2,\quad(x,y)=(1,4)$$
が求める表現の一つとなる。

おまけ

　ちなみに合同方程式
$$m^2\equiv-2023\pmod{4\cdot2024}$$
の$0\leq m<2\cdot2024$なる解は
$$m=507,1013,1563,1979,2069,2485,3035,3541$$
の$8$つであり、それぞれに対応する表現は
\begin{align*} [2024, 507, 32] &\to[16,-5,32] &(x,y)&=\pm(1,8)\\ [2024, 1013, 127] &\to[4,-3,127]&(x,y)&=\pm(1,4)\\ [2024, 1563, 302] &\to[16,5,32] &(x,y)&=\pm(8,5)\\ [2024, 1979, 484] &\to[2,-1,253]&(x,y)&=\pm(23,2)\\ [2024, 2069, 529] &\to[2,1,253] &(x,y)&=\pm(23,-2)\\ [2024, 2485, 763] &\to[16,-5,32]&(x,y)&=\pm(8,-5)\\ [2024, 3035, 1138] &\to[4,3,127]&(x,y)&=\pm(1,-4)\\ [2024, 3541, 1549] &\to[16,5,32]&(x,y)&=\pm(1,-8) \end{align*}
となる。

おわりに

　先日何となく二平方和定理の記事を読み返してた際に、これってもしや使いようによってはすごく面白いのでは？と思いこの記事を書いてみたのですが、結構タメになったのでないでしょうか。個人的に種の理論(指標による判別)の効かない問題6をゴリ押しで解いてるときが一番楽しかったです。
　皆様もこの記事を参考に整数を二次形式で表現してみてはいかがでしょうか。ちなみにこちらの記事にて$h(-4N)=2^{\mu-1}$や$h(-N)=2^{\mu-1}$なる自然数$N$(便利数)についてまとめていたり、tsujimotterさんの記事「二次形式の類数を求めるプログラム」から飛べるページにて$-3$から$-10000$までの判別式$D$に対して類数$h(D)$および原始的かつ簡約な二次形式が求められてたりします。ぜひこちらも参考にしてみてください。
　とりあえずこの記事はこんなところで。では。