平方根の連分数展開の周期

何冊か数論の本を読んでみたのですが、見つけることができませんでした。

Dを平方数でない自然数とするとき、√Dの連分数展開は周期を持つ無限連分数になります。もちろんこの周期自体は実際に連分数展開してみないことにはわかりませんが、周期が偶数になるか奇数になるかは簡単に判定できるのではないか、と思いました。このことはx^2-Dy^2=-1が整数解を持つかどうかと同値で、また判別式が-1になることとも同値だと思います。しかしいずれにしても連分数展開を実行してみない以上わからないので不便です。

D=n^2-2と書けないこと、かつD=p_1^{r_1}…p_k^{r_k}と素因数分解したとき、p_iたちすべてがmod 4で3と合同でない、ということと、連分数展開の周期が奇数であることは同値だと予想したのですが、これは正しいですか？実二次体がらみの話なので、どこかに書いてあるとは思うのですが・・・

No.8 ベストアンサー 回答者： yoikagari 回答日時： 2006/04/06 00:18

本題に戻りましょうw

No1.の解答の繰り返しになりますが
「Dの素因数pにp≡3　(mod　4)となるようなものが存在する⇒x^2-Dy^2=-1は整数解を持たない」ことを示しましょう。

x^2-Dy^2=-1となる整数xとyが存在すると仮定する。
x^2+1^2=Dy^2≡0　(mod　p)となります。
このときxと1は互いに素になります。
しかし、このことはNo4.私が示した命題
「aとbを互いに素な自然数とします。
a^2+b^2の素因数pはp=2あるいはp≡1　(mod　4)となる。また、a^2+b^2は4で割り切れない。」・・・○
に反します。

よって、Dの素因数は2あるいは、4で割って1あまる素数であることがわかる。

「Dが4で割り切れる⇒x^2-Dy^2=-1は整数解を持たない」を示しましょう。

x^2-Dy^2=-1となる整数xとyが存在すると仮定する。
x^2=Dy^2-1≡-1　(mod　4)となります。
x^2≡0or1　(mod　4)だから、これは不合理

よって「Dが4、あるいは4で割ると3余る素数pで割り切れる」⇒「√Dの連分数展開の周期は偶数」が言えます。

要するに「√Dの連分数展開の周期は奇数」⇒「Dの素因数には2がたかだか一つで、他は4で割って1あまる素数」という推論は正しいのです。

この回答への補足

もう一度数表を眺めていたら、いくつか見落としがあったことがわかりました。

√(n^2+1)=[n;2n]で、この場合、周期1の奇数であるのはよくて、
√{(2n+1)^2+2^2}=[2n+1;n,1,1,n,4n+2]で、この場合、周期5の奇数になることもわかりました。
問題はn^2+3^2型の数の場合で、ここでたくさんの例外が出てきました。nが3の倍数の場合は明らかに周期が偶数になるので、それ以外を考えます。
4^2+3^2⇒平方数で例外
5^2+3^2⇒n^2-2型なので周期4の例外
7^2+3^2⇒周期7
8^2+3^2⇒周期7
10^2+3^2⇒周期15
11^2+3^2⇒周期3
13^2+3^2⇒今まで考察していなかった例外（周期6）
14^2+3^2⇒今まで考察していなかった例外（周期8）
16^2+3^2⇒周期9
17^2+3^2⇒今まで考察していなかった例外（周期10）
19^2+3^2⇒周期21
20^2+3^2⇒周期21
22^2+3^2⇒周期9
23^2+3^2⇒周期7
25^2+3^2⇒周期23
26^2+3^2⇒周期15
28^2+3^2⇒今まで考察していなかった例外（周期4）
29^2+3^2⇒今まで考察していなかった例外（周期4）
31^2+3^2⇒周期9
32^2+3^2⇒周期33
以降も規則性がまったくないように思えます。また他にもたくさんの例外がありました。よって逆は正しくないようです。本当はx^2-Dy^2=-1が解を持つためのDの十分条件が知りたかったのですが、どうにも簡単には行きそうもありませんので、ひとまず締め切らせてもらうことにします。ありがとうございました。

補足日時：2006/04/06 02:10

この回答へのお礼

明快なご回答ありがとうございます。なるほど「√Dの連分数展開の周期は奇数」⇒「Dの素因数には2がたかだか一つで、他は4で割って1あまる素数」は正しいのですね。

お礼日時：2006/04/06 01:43

No.9 回答者： yoikagari 回答日時： 2006/04/06 00:55

ごちゃごちゃしてすみません

私の解答の読み方としてはNo.4→No.8→No.7→No.5→No.6
と言った具合にお読みください。

No.7 回答者： yoikagari 回答日時： 2006/04/05 23:27

話が前後しましたが、「連分数展開の周期が奇数になる数D」を見て下さい。

x^2+y^2と書けるものばかりですよね。
(ex.17=1^2+4^2,29=5^2+2^2,41=5^4+4^2,50=7^2+1^2,58=72^+3^2,65=8^2+1^2,73=8^2+3^2,74=7^2+5^2,etc.)

連分数展開の周期が奇数になる数Dの中に、「x^2+1」と書けるものがあるのは、決して偶然ではないのです。

かなりわき道にそれてしまったのですが。

No.6 回答者： yoikagari 回答日時： 2006/04/05 22:37

そして、数論入門〈2〉の基礎的内容を証明してある数論入門〈1〉へのリンクも張っておきます。

(数論入門〈2〉は数論入門〈1〉の結果をバンバン使っていますので、数論入門〈2〉だけでは読むのはきついと思います)

P.S.
私がNo.4で証明した命題
「aとbを互いに素な自然数とします。
a^2+b^2の素因数pはp=2あるいはp≡1　(mod　4)となる。また、a^2+b^2は4で割り切れない。」・・・○
の別証明(本質的には同じかもしれませんが)が数論入門〈2〉の20章にあります。

参考URL：http://www.amazon.co.jp/exec/obidos/ASIN/4431708 …

No.5 回答者： yoikagari 回答日時： 2006/04/05 22:28

ついでに言えば命題

「mを素因数分解したとき、2と『4で割ると1余る素数』以外出てこない⇒m=s^2+t^2(ただし、sとtは自然数)と書くことが出来る」・・・△
も正しいことが言えます。

証明は、シュプリンガー・フェアラーク東京のG.H. ハーディ, E.M. ライト共著の数論入門〈1〉と数論入門〈2〉のと6章(ちょっと)、20章(本質的)をご覧ください。

命題△の本質的な証明がある数論入門〈2〉へのリンクを張っておきます。

参考URL：http://www.amazon.co.jp/exec/obidos/ASIN/4431709 …

No.4 回答者： yoikagari 回答日時： 2006/04/05 21:55

本題とは関係ありませんが、あなたの「n^2+1を素因数分解すると2と4で割って1余る素数・・・」云々の「予想」は正しいです。

あなたの「予想」を一般化した次の命題を示したいと思います。
「aとbを互いに素な自然数とします。
a^2+b^2の素因数pはp=2あるいはp≡1　(mod　4)となる。また、a^2+b^2は4で割り切れない。」・・・○
あなたの予想は、a=n,b=1の特別な場合です。

証明
aとbが奇数のとき
a^2+b^2≡2　(mod　4)
a,bの一方が奇数、他方が偶数のとき
a^2+b^2≡1　(mod　4)
aとbは互いに素だから、aとbが偶数になる事はありえない。

よってa^2+b^2は2で割り切れることはあるが、4では割り切れない。

a^2+b^2がp≡3　(mod　4)となる素数pで割り切れると仮定する。・・・※
a^2+b^2≡0　(mod　p)
よって
a^(p-1)+b^(p-1)≡(a^2+b^2)(a^{(p-3)/2}-a^{(p-5)/2}b^2+・・・+b^{(p-3)/2})≡0　(mod　p)

aとbがpで割り切れないとき
フェルマーの小定理より
0≡a^(p-1)+b^(p-1)≡2　(mod　p)となって不合理
a,bの一方がpで割り切れ、他方がpで割り切れないとき
フェルマーの小定理より
0≡a^(p-1)+b^(p-1)≡1　(mod　p)となって不合理
aとbは互いに素だから、aとbがpで割り切れる事はありえない。

よって※の仮定は誤りで、a^2+b^2が奇素数pを因数に持つとき、p≡1　(mod　4)となることがわかります。

以上より、命題○が正しいことが示されました。

No.3 回答者： yoikagari 回答日時： 2006/04/05 01:55

D=2のときx^2-Dy^2=-1は自然数解x=1,y=1を持ちます

(よって、√Dの連分数展開の周期は奇数)が、
D=2=2^2-2と書けます。

どうやら
「√Dの連分数展開の周期は奇数」⇒「D=p_1^(r_1)…p_k^(r_k)と
素因数分解したとき、p_iたちすべてがmod 4で3と合同でない」
かつ「D=n^2-2と書けない」
という命題は正しくないようです。

この回答への補足

いろいろ問題に不備があったようなので、お詫びして下記のように訂正します。

「√Ｄの連分数展開の周期は奇数」は次と同値
「Ｄ=2」あるいは「Ｄ≠n^2-2 かつ Ｄの素因数には2がたかだか一つで、他は4で割って1あまる素数」

D=2だけ例外と思われるので、それを付け加えました。さらに別の本を参照したところ（確かタイトルに「√2」が入っていました）、素因数2は、あっても一つだけのようなので付け加えました。その本によるとガウス整数環Ｚ[√-1]の理論を使えば示すことができる、とありましたが、証明は省略されていました。確かに mod 4 とＺ[√-1]には関連があるので、そういう気もしないでもないですが。

連分数展開の周期が奇数になる数Ｄを以下に列挙します。
2
5
10
13,17
26,29
37,41
50,53,58,61
65,73,74
などです。一番左に並べたのは、いずれもn^2+1型の数で、このとき周期は1の奇数で、特にn^2-(n^2+1)・1^2=-1と簡単に解がかけます。僕には証明が出来なかったですが、n^2+1を素因数分解すると、素因数には2が一つあるかないか(これは自明)、また4で割って1余る素数しかでてきません(予想ですが)。n^2+1型以外では、17,29,41,53,58,61,73,74,…などと続きますが、58,74以外は4で割って1余る素数、58=2×29,74=2×37も素因数に2は高々一つ、他の素因数は4で割って1余る素数です。

参照した本には「Ｄの素因数には2がたかだか一つで、他は4で割って1あまる素数」が周期が奇数のための必要十分条件とありました。この条件に合う素数Ｄは
2,5,13,17,29,37,41,53,61,73,…
などです。したがってＤとしては次の合成数
10,26,34,58,65,74,82,85,106,122,130,145,146,…
も周期奇数の候補になるわけです。ところが、この中で34だけが唯一例外で周期は4で偶数です。他の例としては194=2×97も周期4の例外です。この例外として現れたＤはいずれもn^2-2型の数でした（僕がＤ=400までで調べた限り）。n^2-2型の場合はいつでも周期が4となって、この場合はn^2-2であるという条件が優先されるようです。ただし2の場合はn^2+1型であるという条件の方がさらに優先されるようです。大きいＤではいずれ反例が現れるのかも知れないという気もして、こうして質問させていただいたのですが、果たして．．．

補足日時：2006/04/05 13:34

No.2 回答者： yoikagari 回答日時： 2006/04/04 02:07

√Dの連分数展開の周期の命題を勘違いしていたようです。

私が根本的に間違っていたようです。
私の↓↓の回答は忘れてください。

No.1 回答者： yoikagari 回答日時： 2006/04/04 01:45

あなたの命題ですが、「D=n^2-2と書けないこと、かつD=p_1^(r_1)…p_k^(r_k)と素因数分解したとき、

p_iたちすべてがmod 4で3と合同でない」
⇔「√Dの連分数展開の周期が偶数であること」
の誤りではないかと思います

こう判断した理由を以下に書きます。

「Dの素因数pにp≡3　(mod　4)となるようなものが存在する⇒x^2-Dy^2=-1は整数解を持たないはいいですよね。
(もし存在すればx^2≡-1　(mod　p)となって、平方剰余の第一補充法則に反しますから!)
よって、
「√Dの連分数展開の周期が偶数であること」
⇒「D=p_1^(r_1)…p_k^(r_k)と素因数分解したとき、p_iたちすべてがmod 4で3と合同でない」が言えます。
こんなとこです。

思いついたら、また書くかもしれません。