- ベストアンサー
平方根の連分数展開の周期
- 平方根の連分数展開の周期について
- 平方根の連分数展開の周期の判定方法について
- D=n^2-2と素因数分解したときの連分数展開の周期について
- みんなの回答 （9）
- 専門家の回答
質問者が選んだベストアンサー
本題に戻りましょう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あまる素数」という推論は正しいのです。
その他の回答 (8)
- yoikagari
- ベストアンサー率50% (87/171)
ごちゃごちゃしてすみません 私の解答の読み方としてはNo.4→No.8→No.7→No.5→No.6 と言った具合にお読みください。
- yoikagari
- ベストアンサー率50% (87/171)
話が前後しましたが、「連分数展開の周期が奇数になる数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」と書けるものがあるのは、決して偶然ではないのです。 かなりわき道にそれてしまったのですが。
- yoikagari
- ベストアンサー率50% (87/171)
そして、数論入門〈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章にあります。
- yoikagari
- ベストアンサー率50% (87/171)
ついでに言えば命題 「mを素因数分解したとき、2と『4で割ると1余る素数』以外出てこない⇒m=s^2+t^2(ただし、sとtは自然数)と書くことが出来る」・・・△ も正しいことが言えます。 証明は、シュプリンガー・フェアラーク東京のG.H. ハーディ, E.M. ライト共著の数論入門〈1〉と数論入門〈2〉のと6章(ちょっと)、20章(本質的)をご覧ください。 命題△の本質的な証明がある数論入門〈2〉へのリンクを張っておきます。
- yoikagari
- ベストアンサー率50% (87/171)
本題とは関係ありませんが、あなたの「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)となることがわかります。 以上より、命題○が正しいことが示されました。
- yoikagari
- ベストアンサー率50% (87/171)
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型であるという条件の方がさらに優先されるようです。大きいＤではいずれ反例が現れるのかも知れないという気もして、こうして質問させていただいたのですが、果たして．．．
- yoikagari
- ベストアンサー率50% (87/171)
√Dの連分数展開の周期の命題を勘違いしていたようです。 私が根本的に間違っていたようです。 私の↓↓の回答は忘れてください。
- yoikagari
- ベストアンサー率50% (87/171)
あなたの命題ですが、「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と合同でない」が言えます。 こんなとこです。 思いついたら、また書くかもしれません。
お礼
明快なご回答ありがとうございます。なるほど「√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の十分条件が知りたかったのですが、どうにも簡単には行きそうもありませんので、ひとまず締め切らせてもらうことにします。ありがとうございました。