2

ペル方程式と平方数和分解の話

120
0

ペル方程式を解く手続き。D2以上の平方でない整数とし、
x2Dy2=1
の解を考えてみる。
N=D
とおく(整数部分)。3つ組:
f=(1, N, N2D)
を取る。次の操作を繰り返す。
(a, b, c)  (c, b, a).
ここに、まずbはどう求めるかというと、N+b  mod|c|で得られる0以上|c|未満の整数を取ってこれをNから引いたものをbとする。
D=b2ac,   a=Db2c
としてaが決まる。これを繰り返していくとき、もし、
(1, N, DN2)
に到達するなら、
x2Dy2=1
が最小の整数解を持つことになる。この場合の最小の整数解(x0, y0)x0+Dy0であらわすとき、
(x0+Dy0)2=(x02+Dy02+2x0y0D)
みたいになってx2Dy2=1の最小整数解は(x02+Dy02, 2x0y0)になる。
 (1, N, DN2)に到達することなく
(1, N, N2D)
に戻ってくる場合には、そのまま計算するとx2Dy2=1の解が出る。
 その計算方法について述べる。まず、
(a, b, c)  (c, b, a)
においてb+b|c|で割る。この値を、
(1, N, N2D)  (N2D, b, c)  (±1, N, ±(N2D))
の隣接部分すべてに対して計算し、これを
h0, h1, , hm
とおいて行列の積:
(011h0)(011h1)(011hm)=(pq)
を計算する。こうして得られるp,qについて、
p+q(N+D)
を計算するとき(p+qN, q)が最小解になる。1に到達するなら1の解が出るし、1が出ないまま1に戻るならそのまま+1の解が出る。

x2199y2=1

解く。D=199, N=14.
(1, 14, 3)  (3, 13, 10)    (14(14+14  mod 3)=13)  (10, 7, 15)    (14(14+13  mod 10)=7)  (15, 8, 9)    (14(14+7  mod 15)=8)  (9, 10, 11)    (14(14+8  mod 9)=10)  (11, 12, 5)    (14(14+10  mod 11)=12)  (5, 13, 6)    (14(14+12  mod 5)=13)  (6, 11, 13)    (14(14+13  mod 6)=11)  (13, 2, 15)    (14(14+11  mod 13)=2)  (15, 13, 2)    (14(14+2  mod 15)=13)  (2, 13, 15).    (14(14+13  mod 2)=13)
ここで、実は(a, b, c)  (c, b, a)を満たす形式はアンビグという名前が付いているんだけど、ここから先は折り返しになる。ここのh=2b/|c|を中心としてこの先はここまで作ったものの逆配列が現れる。そして(3, 14, 1)まで戻った後で(1, 14, 3)が出てきて終了する。これでhを求めてみる。
(1, 14, 3)(3, 13, 10)14+133=9.
以下同様に、
9, 2, 1, 2, 2, 5, 4, 1, 1, 13
13はアンビグ隣接:(15, 13, 2)  (2, 13, 15)だからその先は
1, 1, 4, 5, 2, 2, 1, 2, 9, 28
になる。28は戻るとき。これより行列は、
A=(0119)(0111)  A(01113)tA(01128)
となるが、最後にできる行列の左半分が欲しいので、最後の行列は要らなくて、
A(01113)tA=(pq)
を計算して右半分を取ればいい。計算により、
A=(53496550039041)
がわかるので、
A(01113)tA=(1230751341153080099)
となる。これらに対して(p+14q, q)を計算すると、
{p+14q=16266196520q=1153080099
になるから、結局x2199y2=1の整数解は存在せず、x2199y2=1の最小解として、
16266196520219911530800992=1
を得る。実際、
162661965202=264589149227260110400,199×11530800992=264589149227260110399
が確かめられる。
もうひとつやってみたい。

x261y2=1

D=61, N=7でやってみる。
(1, 7, 12)  (12, 5, 3)    (7(7+7  mod 12)=5)  (3, 7, 4)    (7(7+5  mod 3)=7)  (4, 5, 9)    (7(7+7  mod 4)=5)  (9, 4, 5)    (7(7+5  mod 9)=4)  (5, 6, 5).    (7(7+4  mod 5)=6)
ここでそのまま進んでもいいんだけど、実は、
(a, b, a)  (a, b, a)
が現れるとそのあとはそのまま両端の符号が逆転したものが展開される。そして(12, 7, 1)まで戻った後、最後に(1, 7, 12)となり、そこから先は両端の符号が逆なだけで同じ流れになる。先程の議論で2つだったところがひとつになるイメージ。その区切りまでh=(b+b)/|c|を計算すると、
1, 4, 3, 1, 2
となりそこからは2, 1, 3, 4, 1, 14みたいになる。行列も、やっぱり最後のやつは計算しなくてよくて、
A=(0111)(0114)(0113)(0111)(0112)A tA=(pq)
を出せばいい。
A=(17472158),   A tA=(30833805),  {x=3083+3805N=29718,y=3805.
x2=883159524,   61y2=883159525,   x261y2=1.
x261y2=1の最小の整数解は、このxyから出すのだが、めちゃんこ大きくなる。
(x+61y)2=(x2+61y2)+2xy61=1766319049+22615398061
だからこの2数になる。すごい大きい・・。

まとめ

結局、最初の形式まで戻る必要はなくて、
(a, b, c)  (c, b, a)
となるか、
(a, b, a)
が現れるところまで計算すればいい。そして前者の場合はそこまでのhに対する行列Aと中央のひとつとAの転置を順番に掛けて右半分を見てNをかませていじる、後者の場合は普通にそこまでのhに対するAに対しその転置を掛けてやはり右半分を見てNをかませていじればいい。そうすると1の方の解が出るので+1が欲しい場合は最後みたいにする。以上。
 ちなみに(a, b, a)が現れる場合、すべての(a, b, c)b2ac=Dを満たしているので、
D=a2+b2
が成立する。実は平方数和分解できるすべてのDはこの方法で平方数和分解することができる。

投稿日:20201116
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

黒狐
黒狐
34
4950
数学ちょっと好きです!

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中