不定方程式 x2−my2=±1を Pell方程式 と呼ぶ。
これは、mが2乗数でないとき、x=±1、y=0以外の解を必ず持つ。
また、sqrt(m) を以下のように表したとき、
1 sqrt(m) = a1 + ------------------------ 1 a2 + ------------------ 1 a3 + ------------ a4 + ……
sqrt(m)の連分数展開と呼ぶ。
このままでは、表記するのが大変なので(ソースを見てください)、
sqrt(m)=a1[a2, a3, a4, ……]
と略記する。
Pell方程式の解及び連分数展開の各桁は以下の漸化式より求められる。
an 連分数展開の各桁の数 pn/qn n番目で打ち切ったときの部分和 Pn、Qn 補助変数
これらの数について第n項目は、
an a1=int(sqrt(m))
……
an=int((a1+Pn)/Q1)Pn P1=0
P2=a1
……
Pn=an-1×Qn-1−Pn-1Qn Q1=1
Q2=m−a12
……
Qn=(m−Pn2)/Qn-1pn p1=a1
p2=a2×a1+1
……
pn=an×pn-1+pn-2qn q1=1
q2=a2 ……
qn=an×qn-1+qn-2
Qn=1となるnについて、 pn-1、qn-1が Pell方程式の解となる。
この漸化式をExcelの計算式で表してみる。
<計算式>A | B | C | D | E | F | G | |
---|---|---|---|---|---|---|---|
1 | m= | (mの値を代入) | |||||
2 | n | Pn | Qn | an | pn | qn | pn^2-mqn^2 |
3 | 1 | 0 | 1 | =INT(SQRT($B$1)) | =D3 | 1 | =E3^2-$B$1*F3^2 |
4 | 2 | =D3 | =$B$1-D3^2 | =INT(($D$3+B4)/C4) | =D4*D3+1 | =D4 | =E4^2-$B$1*F4^2 |
5 | 3 | =D4*C4-B4 | =($B$1-B5^2)/C4 | =INT(($D$3+B5)/C5) | =D5*E4+E3 | =D5*F4+F3 | =E5^2-$B$1*F5^2 |
6 | 4 | =D5*C5-B5 | =($B$1-B6^2)/C5 | =INT(($D$3+B6)/C6) | =D6*E5+E4 | =D6*F5+F4 | =E6^2-$B$1*F6^2 |
n=1,2,3のときは直接式を書き込む。
n=4以降は、n=3の時の行をそのままコピーすると、
行、列の index が自動的に increment される。
B1に求める値を代入し、Cの4行目以降に1が現れるまで、計算式をコピーする。
Cのk行目が1となったとき、
E、Fのk−1行目が Pell方程式の解
Dの3行目〜k行目が連分数展開の各項
となる。
100以下で循環節が最も長くなるm=94の場合について、サンプルを示す。
A | B | C | D | E | F | G | |
---|---|---|---|---|---|---|---|
1 | m= | 94 | |||||
2 | n | Pn | Qn | an | pn | qn | pn^2-mqn^2 |
3 | 1 | 0 | 1 | 9 | 9 | 1 | -13 |
4 | 2 | 9 | 13 | 1 | 10 | 1 | 6 |
5 | 3 | 4 | 6 | 2 | 29 | 3 | -5 |
6 | 4 | 8 | 5 | 3 | 97 | 10 | 9 |
7 | 5 | 7 | 9 | 1 | 126 | 13 | -10 |
8 | 6 | 2 | 10 | 1 | 223 | 23 | 3 |
9 | 7 | 8 | 3 | 5 | 1241 | 128 | -15 |
10 | 8 | 7 | 15 | 1 | 1464 | 151 | 2 |
11 | 9 | 8 | 2 | 8 | 12953 | 1336 | -15 |
12 | 10 | 8 | 15 | 1 | 14417 | 1487 | 3 |
13 | 11 | 7 | 3 | 5 | 85038 | 8771 | -10 |
14 | 12 | 8 | 10 | 1 | 99455 | 10258 | 9 |
15 | 13 | 2 | 9 | 1 | 184493 | 19029 | -5 |
16 | 14 | 7 | 5 | 3 | 652934 | 67345 | 6 |
17 | 15 | 8 | 6 | 2 | 1490361 | 153719 | -13 |
18 | 16 | 4 | 13 | 1 | 2143295 | 221064 | 1 |
19 | 17 | 9 | 1 | 18 | 40069671 | 4132871 | -13 |
連分数展開
sqrt(94)=9 [1, 2, 3, 1, 1, 5, 1, 8, 1, 5, 1, 1, 3, 2, 1, 18]
Pell方程式の初期解
x=2143295
y=221064
となる。
前頁 | 目次 | 次頁 |
---|