• ベストアンサー
  • 暇なときにでも

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

何冊か数論の本を読んでみたのですが、見つけることができませんでした。 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と合同でない、ということと、連分数展開の周期が奇数であることは同値だと予想したのですが、これは正しいですか?実二次体がらみの話なので、どこかに書いてあるとは思うのですが・・・

共感・応援の気持ちを伝えよう!

  • 回答数9
  • 閲覧数746
  • ありがとう数3

質問者が選んだベストアンサー

  • ベストアンサー
  • 回答No.8

本題に戻りましょう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あまる素数」という推論は正しいのです。

共感・感謝の気持ちを伝えよう!

質問者からのお礼

明快なご回答ありがとうございます。なるほど「√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の十分条件が知りたかったのですが、どうにも簡単には行きそうもありませんので、ひとまず締め切らせてもらうことにします。ありがとうございました。

その他の回答 (8)

  • 回答No.9

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

共感・感謝の気持ちを伝えよう!

  • 回答No.7

話が前後しましたが、「連分数展開の周期が奇数になる数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

そして、数論入門〈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/4431708480/qid=1144242600/sr=8-1/ref=sr_8_xs_ap_i1_xgl/250-5202108-0801828

共感・感謝の気持ちを伝えよう!

  • 回答No.5

ついでに言えば命題 「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/443170924X/qid=1144242600/sr=8-2/ref=sr_8_xs_ap_i2_xgl14/250-5202108-0801828

共感・感謝の気持ちを伝えよう!

  • 回答No.4

本題とは関係ありませんが、あなたの「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

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と書けない」 という命題は正しくないようです。

共感・感謝の気持ちを伝えよう!

質問者からの補足

いろいろ問題に不備があったようなので、お詫びして下記のように訂正します。 「√Dの連分数展開の周期は奇数」は次と同値 「D=2」あるいは「D≠n^2-2 かつ Dの素因数には2がたかだか一つで、他は4で割って1あまる素数」 D=2だけ例外と思われるので、それを付け加えました。さらに別の本を参照したところ(確かタイトルに「√2」が入っていました)、素因数2は、あっても一つだけのようなので付け加えました。その本によるとガウス整数環Z[√-1]の理論を使えば示すことができる、とありましたが、証明は省略されていました。確かに mod 4 とZ[√-1]には関連があるので、そういう気もしないでもないですが。 連分数展開の周期が奇数になる数Dを以下に列挙します。 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余る素数です。 参照した本には「Dの素因数には2がたかだか一つで、他は4で割って1あまる素数」が周期が奇数のための必要十分条件とありました。この条件に合う素数Dは 2,5,13,17,29,37,41,53,61,73,… などです。したがってDとしては次の合成数 10,26,34,58,65,74,82,85,106,122,130,145,146,… も周期奇数の候補になるわけです。ところが、この中で34だけが唯一例外で周期は4で偶数です。他の例としては194=2×97も周期4の例外です。この例外として現れたDはいずれもn^2-2型の数でした(僕がD=400までで調べた限り)。n^2-2型の場合はいつでも周期が4となって、この場合はn^2-2であるという条件が優先されるようです。ただし2の場合はn^2+1型であるという条件の方がさらに優先されるようです。大きいDではいずれ反例が現れるのかも知れないという気もして、こうして質問させていただいたのですが、果たして...

  • 回答No.2

√Dの連分数展開の周期の命題を勘違いしていたようです。 私が根本的に間違っていたようです。 私の↓↓の回答は忘れてください。

共感・感謝の気持ちを伝えよう!

  • 回答No.1

あなたの命題ですが、「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と合同でない」が言えます。 こんなとこです。 思いついたら、また書くかもしれません。

共感・感謝の気持ちを伝えよう!

関連するQ&A

  • フェルマーの最終定理(n=4)

    p,qは互いに素な自然数とする。以下の問いに答えよ。 (1)p,qがともに奇数であるとき、p^4+q^4は自然数の2乗にならないことをするせ。 これは、平方数を4で割った余りは、0または1で、条件よりp^2,q^2も奇数で p^4+q^4≡1+1=2(mod 4) mod 4で0または1でないので、平方数ではない。と書かれています。 (2)qは奇数とする。つぎの手順に従って、(2p)^4+q^4が自然数の2乗にならないことを背理法を用いてしるせ。 [1]次の仮定(H)が成り立つものとして、以下の問(A)~(D)に答えよ。 仮定(H):(2p)^4+q^4=r^2となる自然数rが存在する。 (A)2pとrは互いに素になることをしるせ。  仮定(H)より2pが偶数で、qが奇数なので、rは奇数です。ここからがわからないところです。2pとrの最大公約数をdとおくと、dは奇数です。  自分は、偶数を 2*奇数、2*偶数、奇数を2*奇数+1、2*偶数+1、として、最大公約数が奇数なら、偶数も奇数も奇数で割って、自然数になるのか確かめようとしましたが、失敗しました。  どなたか偶数と奇数の最大公約数は奇数になることを証明してください。お願いします。 

  • √2が無理数であることの証明について

    √2が無理数であることの証明について 一つ疑問が生じまじた。 背理法を用いて、√2が有理数であると仮定すると、 √2=q/p (p,qは自然数)とおけるから 両辺二乗して 2=q^2/p^2 ⇒2*p^2=q^2 ・・・A ここから無限降下法を用いて矛盾を導くのが一般的な解法であると思うのですが、 Aの段階で明らかに(明らかでなくとも、証明すれば)右辺は平方数で左辺は平方数ではありません。 これは矛盾ではないのでしょうか? 例えば、平方数の約数の個数は奇数、非平方数の約数の個数は偶数ということをまず示せば、素因数分解の一意性に矛盾することは言えますが、そのような補題なしに「非平方数=平方数」は矛盾と考えてはいけないのでしょうか? 矛盾と考えていいのであれば一般の非平方数nに対して√nが無理数であることの証明がすごく簡単になるのですが・・・ 解説お願いします。

  • modを使用した平方根の求め方

    解き方が解からない問題があります。 どれだけ考えても解き方がわからないので、どなたかわかる方教えてください。 【解き方が解からない問題】 大きな素数の積n=pqが与えられた時、nを素因数分解するのは非常に難しい。 整数mと整数y(<m)が与えられた時y=x2(xの二乗) mod mなる整数解xが存在すれば、yは mod mで平方剰余であるという。 xを mod mでのyの平方根という。 mが素数7の時、 12(1の二乗の事です。二乗の書き方がわからなくて・・・)≡1 (mod 7) 、 22(2の二乗) ≡ 4 (mod 7) 32(3の二乗)≡2 (mod 7) 、 42(4の二乗) ≡ 2 (mod 7) 52(5の二乗)≡4 (mod 7) 、 62(6の二乗) ≡ 1 (mod 7) となるので、1、2、4が平方剰余で、各平方剰余には2個の平方根がある。 mが二つの素数の積の場合、4個の平方根がある。 ここまでが参考書に載ってる説明です。 ここから私がわからない問題です。 102(10の二乗) mod 77=23 n = 77 の素因数7と11から素因数の知識を利用してZのmod nでの平方根Sを計算する。 S2(Sの二乗) ≡ 23 mod 7 S2(Sの二乗) ≡ 23 mod 11 上の2つを解いて、mod 77での4つの平方根10、32、45、67を得る。 この2つの式から、何をどうやって計算して、4つの平方根10、32、45、67が導き出せたのかわかりません。 二乗の表記の仕方がわからず、とても見難くなってしまいました。すみません。 乱文になってしまいましたが、どなたかわかる方教えてください。 よろしくお願いします。

  • ゼロ知識証明の勉強をしているのですが…

    ゼロ知識証明の勉強をしているのですが… 途中で 1.m が合成数の時、m を素因数分解できれば任意の y の mod m での平方根を簡単に求めることができる。逆に任意の y に対する mod m での平方根が求まるならば、m を簡単に素因数分解できる。 2.m を素因数分解できれば、任意の y に対し mod m での平方剰余性を簡単に判定できる。 とあったのですが、計算方法が解らないので、納得が出来ません。 具体的な計算方法が解る方がいらっしゃいましたら、ご教授願います。

  • ペル方程式x^2-py^2=-1は常に整数解を持つか?

    先日、 http://okwave.jp/kotaeru.php3?q=2069583 で、√Dの連分数展開の周期がいつ奇数になるか?という問題を質問させていただきました。平方剰余の相互法則の第一補充則と簡単な議論から、Dは4で割り切れないこと、さらにDの素因数に4で割って3余る素数を含まないことが必要条件となります。連分数展開の周期が奇数になることと、ペル方程式 x^2-Dy^2=-1 が整数解を持つことは同値です。したがってこのためのDの必要条件が求められたことになります。しかし、上の条件が満たされるDでもペル方程式が整数解を持たないものがたくさんあります。たとえば34,146,178,194,205,221,…などなどです。他方、合成数であっても解をもつDもたくさんあります。いったいこれらの性質の違いがどこから来るのか知りたいものです。ですが、難しい問題なのかも知れません。 で、本題です。このDが特に素数pのとき、解を持たないような反例が600以下の4で割って1余る素数で見つからなかったので、これなら正しいのではないか?と思ったので、そのことを証明する方法、あるいは反例があるのであれば知りたいと思いました。 きちんと書くと、「pを4で割って1余る素数とするとき、x^2-py^2=-1は常に整数解を持つか?」ということです。4で割って1余る素数pはある互いに素な自然数s,tを用いてp=s^2+t^2と表されることが知られています。しかし、こう表されることがペル方程式が整数解を持つための十分条件になるかというとそうではありません。たとえば34=5^2+3^2は合成数で平方和分解を持つ数ですが、上記のペル方程式の整数解を持たないもので、58=7^2+3^2は合成数で平方和分解をやはり持ちますが、こちらはペル方程式が整数解を持ちます。ですから、もし僕の書いた主張が正しいのであれば、素数性が大事なのであって、平方和分解とは本質的に異なる問題だと思います。

  • 4n+1型の素数について

    4n+1型素数の無限性を示せ。 次のように考えた。行き詰まったのでアドバイスをお願いします。 4n+1の素数は有限で最大をpとする。 k=4(5×13×・・×p)+1 とおく。 kは合成数のとき、kは4n+3型の素数の偶数個の積に素因数分解できるから、  k=(4x+1)(4y+1) x,y自然数   =16xy+4x+4y+1  となる。  このあとの矛盾の導き方が見えないので、この流れの証明とすると このあとどうなるのか、よろしくお願いします。

  • 中3の数学。平方について

    数学の問題についての質問です。 Q. 216/a (a分の216) がある自然数の平方になるとき、aにあてはまる自然数をすべて答えなさい。 という問題です。 答えは、6,24,54,216なのですが、なぜこの答えが出るのかわかりません。 でも、素因数分解をして2の3乗と3の3乗になることまではわかります。 しかし、ここからどうすればこれらの答えになるのかわかりません。 教えてください。 できるだけ詳しく、わかりやすく、教えてください。 また、こうすればもっと簡単に答えが出るよ という解説があるならば、教えて頂けると助かります。 この問題は、中3の問題なので、高校などで習うような難しいことは使いません。 よろしくお願いします。

  • ペル方程式の自然数解と有理数解

    Dを平方数でない自然数とするとき、ペル方程式 x^2-Dy^2=1 は非自明な整数解(x,y)∈Z^2、特に自然数解(x,y)∈N^2を持つことは有名な事実です。Dirichlet原理(無理数の整数周期性の非存在)を用いた抽象論的証明や、二次無理数の(正則)連分数展開の周期性を用いた構成的証明が知られていると思いますが、非自明な有理数解でよいのなら、 (x,y)=((D+n^2)/(D-n^2),2n/(D-n^2))が確かに解を与えることは直ちにわかります。必要というわけではないですが、n^2<D<(n+1)^2としておきます。 もちろん(D+n^2)/(D-n^2)と2n/(D-n^2)が自然数になるようなD、たとえば、D=2,3,5,6,8,10,…などは非自明な自然数解の存在も同時にわかるわけですが、たとえばD=7などでは自然数解の存在まではこれだけではわかりません。そこで、有理数解の存在を既知とした場合、それから自然数解の存在を導く証明はないのか、と考えたのですが、思いつきませんでした。もし何かよい方法があればご教授いただけませんか?

  • (-1)^nでnを無限大にとばしたとき

    大学受験用の参考書にて、 (-1)^n はn→∞において、 nが偶数のとき1 nが奇数のとき-1 となっています。 さらに、 2n乗では1 2n±1乗では-1 となっています。 そこで質問なのですが、以前に無限大というのは数ではなく量だと聞きました。それなのになぜ偶数や奇数があるのでしょうか。また2nや2n±1でわかれるということは、無限大というのは自然数なのですか?

  • 無限級数の掛け算のやり方

    添付画像の数式の右辺を展開する方法が分かりません。 同じ質問を以前にこちらに投稿しましたが、 どなたもどのような手順で数式展開をすることが可能であるかについては 回答を避けて通っておられたため この数式が本当に正確であるかを確認することができずにいます。 一意的に素因数分解がなされる、という意見が前回ありましたが 素因数分解が可能であるのならば どのような素因数が登場するのかを教えていただきたいと思います。 無限級数を無限回数の掛け算するということは 常識では到底、行なうことが不可能ですので 数学の専門家からのご指導をお願いします。