Diophantine Equation

Diophantine Equation ディオファントス方程式
Pell Equation ペル方程式ぺるぺる
解き方を説明するよ。ぺる方程式を手で解けるようになりましょう。

http://www.alpertron.com.ar/QUAD.HTM の解説の翻訳

$Ax^2+Bxy+Cy^2+Dx+Ey+F=0$

A=B=C=0の場合 (Dx+Ey+F=0) - 線形
- D=E=F=0
- D=E=0,F!=0
- D=0,E!=0
- E=0,D!=0
- D!=0,E!=0
A=C=0,B!=0の場合 - 簡単な双曲線形
- DE-BF=0の場合
- DE-BF!=0の場合、
B^2-4AC<0の場合 - 楕円形
B^2-4AC=0の場合 - 放物線形
B^2-4AC>0の場合 - 双曲線形

A=B=C=0の場合 (Dx+Ey+F=0) - 線形

D=E=F=0

つねに成立

D=E=0,F!=0

解なし

D=0,E!=0

y=-F/E,x=すべての整数

E=0,D!=0

x=-F/D,y=すべての整数

D!=0,E!=0

g=gcd(|D|,|E|)とする。
Fがgの倍数でなければ解なし。
$Du+Ev=g$ の解u,vを拡張互除法で求める。
$\begin{cases}x=u(-F/g)+(E/g)t,\\ y=v(-F/g)-(D/g)t,\\ t\in \mathbb{Z}\end{cases}$ が解。

A=C=0,B!=0の場合 - 簡単な双曲線形

$Bxy+Dx+Ey+F=0$ から
$(Bx+E)(By+D)=DE-BF$ となる。

DE-BF=0の場合

Bx+E=0かBy+D=0になる。
B|Eの場合、x=-E/B,y=すべての整数
B|Dの場合、x=すべての整数,y=-D/B

DE-BF!=0の場合、

DE-BFの約数をdとして列挙、
$\begin{cases}x=\frac{d-E}{B}\\ y=\frac{(DE-BF)/d-D}{B}\end{cases}.$

B^2-4AC<0の場合 - 楕円形

(x,y)は楕円上に存在するため、xの上限下限を決めて、がんばって走査する。
変形して
$Cy^2+(Bx+E)y+(Ax^2+Dx+F)=0$
$y=\frac{-(Bx+E)\pm \sqrt{(Bx+E)^2-4C(Ax^2+Dx+F)}}{2C}$
上限下限は根号内が0のときなので、 $(Bx+E)^2-4C(Ax^2+Dx+F)=(B^2-4AC)x^2+2(BE-2CD)x+(E^2-4CF)=0$ の2解の間の整数を走査すればよい。

B^2-4AC=0の場合 - 放物線形

まだだよ！

B^2-4AC>0の場合 - 双曲線形

変数変換によってD,Eは消せる。 $Ax^2+Bxy+Cy^2=-F$ が解ければ良い。
F=0ならx=y=0が自明な解。非自明な解を求める。
4Aを両辺にかけて変形すると、
$(2Ax+By)^2-(B^2-4AC)y^2=-4AF$
これを因数分解して
$(2Ax+By+\sqrt{B^2-4AC}y)(2Ax+By-\sqrt{B^2-4AC}y)=-4AF$

B^2-4ACが平方数のとき

4AFの正、負のすべての約数dについて、

$\begin{cases}y=(d+4AF/d)/(2\sqrt{B^2-4AC})\\ x=(d-(B+\sqrt{B^2-4AC})y)/(2A)\end{cases}$
が成り立つのでOK.

B^2-4ACが非平方数, F!=0

gcd(A,B,C)|Fでない場合解なし。A,B,Cをgcdで割っておく。

$4F^2&lt;B^2-4AC$ の場合

解が存在するとすれば $At^2+Bt+C=0$ の根の連分数展開のconvergents(途中生成された有理数列)の中にある。2次方程式の解の連分数展開は周期的なので、解は無限個かあるいはなしになる。

$4F^2\ge B^2-4AC$ の場合

x,yのgcdをGとおき、u=x/G,v=y/Gとすると、
$Au^2+Buv+Cv^2+F/G^2=0$ となる。G>1ならばF/G^2が整数になるようにGを選んで解けば良い。
gcd(x,y)=1としてしまおう。

gcd(A,B,F)=1ならば、次のようにして解ける。
s,zを使って $x=sy-Fz$ として元の式に代入すると、
$-(As^2+Bs+C)y^2/F+(2As+B)yz-AFz^2=1$ となる。
$As^2+Bs+C\equiv 0(\text{mod}\ F)$ なる $s\in [0,F-1]$ が見つかるならば、t=y/zとして、
$-(As^2+Bs+C)/F*t^2+(2As+B)t-AF=0$ の根の連分数展開のconvergentsから解が求まる。存在しなければ解は存在しない。

gcd(B,C,F)=1ならば同様に $y=sx-Fz$ として、
$-(Cs^2+Bs+A)/F*t^2+(2Cs+B)t-CF=0$ の根の連分数展開のconvergentsから解が求まる。存在しなければ解は存在しない。

どちらでもない場合、A,B,Cを上記の場合に適合するように変形する。
i,j,m,nが $in-jm=1$ を満たすとする。変形後の方程式の解を(X,Y)、変形前の解を(x,y)とする。変形後のA,B,Cをa,b,cとする。 $x=iX+jY, y=mX+nY, X=nx-jy, Y=-mx+iy$ とする。
$Ax^2+Bxy+Cy^2=A(iX+jY)^2+B(iX+jY)(mX+nY)+C(mX+nY)^2=aX^2+bXY+cY^2$
$\begin{cases}a=Ai^2+Bim+Cm^2\\ b=2Aij+Bin+Bjm+2Cmn\\ c=Aj^2+Bjn+Cn^2$
が成り立つ。
$a=Ai^2+Bim+Cm^2$ がFと互いに素であるようにi,mを決める(gcd(i,m)=1)。ひとつi,mが決まったらj,nは拡張互除法から決まる。すると、A,B,Cからa,b,cが求まる。

例

$18x^2+41xy+19y^2-24=0$
あきらかにgcd=1で、 $18s^2+41s+19\equiv 0(\text{mod}\ 24)$ を満たすsによって場合分けする。
s=19の場合
$-(As^2+Bs+C)/F*t^2+(2As+B)t-Af=0$ は
$304t^2+725t+432=0$ となる。これの解の連分数展開は、
$-2 + 1,5,[8,5,1,3,1,1,2,2,1,1,3,1,5,8,1,2,17,2,1]$ となる。ここからconvergentsを求めると、
－7987322433784501/6865878383744439のときに $304num^2+725num*den+432den^2$ が1になる。連分数展開に出てくる数字をc_iとすると、
$num_0=0, den_0=1, num_1=1, den_1=0,$
$\begin{cases}num_i=c_inum_{i-1}+num_{i-2}\\ den_i=c_iden_{i-1}+den_{i-2}\end{cases}$
で計算できる。y=num,z=denなので、x=sy-Fzからxが求まり、x=13021954967961017, y=-7987322433784501となる。やったね！
解は2つあるのでもう一方の連分数展開も存在する。これは省略。

特殊解から一般解を求める

$\binom{X_{n+1}}{Y_{n+1}}=\begin{pmatrix} P&Q\\ R&S\end{pmatrix}\binom{X_n}{Y_n}$
のP,Q,R,Sを決めましょう。
$M(x,y)=Ax^2+Bxy+Cy^2=M, N(u,v)=u^2+Buv+ACv^2=N$ とおくと、
M=0の解は、 $J=\frac{-B+\sqrt{B^2-4AC}}{2A}, J'=\frac{-B-\sqrt{B^2-4AC}}{2A}.$
N=0の解は、 $K=\frac{-B+\sqrt{B^2-4AC}}{2}, K'=\frac{-B-\sqrt{B^2-4AC}}{2}.$
K=AJ,K'=AJ'が成り立つので、X=pr-Cqs, Y=Aps+qr+Bqsとおくと、
$(p-Jq)(r-Ks)=(p-Jq)(r-AJs)=pr-AJps-Jqr+AJ^2qs=pr-AJps-Jqr+A(-(B/A)J-(C/A))qs=pr-Cqs-(Aps+qr+Bqs)J=X-YJ$ J'についても同様。
$M(p,q)/A*N(r,s)=(X-YJ)(X-YJ&#039;)=X^2+(B/A)XY+(C/A)Y^2$ の両辺にAをかけると $AX^2+BXY+CY^2=MN$ になる。M=-F,N=1とすると、X,Yは元の方程式の解になっている。
r,sをN(r,s)=1の解とすると、 $X_n=p,Y_n=q$ (Mを満たしているのでこれらは元の方程式の解)から $X_{n+1}=X,Y_{n+1}=Y$ を求めることができて、
$\binom{X_{n+1}}{Y_{n+1}}=\begin{pmatrix} r & -Cs\\ As & r+Bs\end{pmatrix}\binom{X_n}{Y_n}$ が成り立つ。

F=-1の場合

s=0とできるので結構簡単になる。 $Ct^2+Bt+A=0$ の解を連分数展開して、 $Cy^2+Byx+Ax^2=1$ となる組y/xをみつけたら、それがそのまま特殊解になる。 $u^2+Buv+ACv^2=1$ の非自明(u=1,v=0は自明)な解u,vについて、漸化式
$\binom{X_{n+1}}{Y_{n+1}}=\begin{pmatrix} u & -Cv\\ Av & u+Bv\end{pmatrix}\binom{X_n}{Y_n}$ が成り立つ。

ペル方程式(A=-W<0,B=0,C=1,F=-1)の場合

$-Wx^2+y^2=1$
やはりs=0とできる。 $t^2+A=0$ の解は $t=\sqrt{W}$ となり、Wの平方根の連分数展開を求めれば良い。この連分数展開は周期に関して対称になる。あとはconvergentsを求め、 $num^2-Wden^2=1$ を満たす(num,den)を求めると、それがそのまま特殊解となる。x=den,y=num.
$u^2-Wv^2=1$ の非自明(u=1,v=0は自明)な解u,v(非負？)について、漸化式
$\binom{X_{n+1}}{Y_{n+1}}=\begin{pmatrix} u & -v\\ -Wv & u\end{pmatrix}\binom{X_n}{Y_n}$ が成り立つ。この場合、非自明な解は特殊解そのものなので、X_0=0, Y_0=1と置くことができ、
$\binom{X_n}{Y_n}=\begin{pmatrix} u & -v\\ -Wv & u\end{pmatrix}^n\binom{0}{1}$ が成り立つ。

「Diophantine Equation」をウィキ内検索

最終更新：2014年02月07日 20:14

uwicoder