TETRA'S MATH

数学と数学教育

フィボナッチ数列を7でわったときの余り(3)

 二項定理から導かれる補助定理というのは、次のようなものです。



 これをp=7の場合で確かめます。



 緑の部分が7の倍数でばっさり消えるので、



となります。aとbはどちらもF7の元なので6乗で1になり、7乗でもとにもどります。よって、a^7=a、b^7=b

 また、(√5)^7=125√5=6√5=−√5と考えてよさそうなので、



がいえそうです。となると、フィボナッチ数列の一般項に出てくる(1+√5)^k はk=7で(1−√5)になることが計算しなくてもわかって便利です。

 でも、p=7のときには具体的に計算して+が−に変わることを確認できたけど、pのままだとどう考えるのだろう?

 テキストにおいては、(√5)^p も x^2=5の根であり、√5か−√5でなければならないが、√5だと(・・・中略・・・)√5がFpの中に入ってしまって仮定に反するので、−√5であることがわかる、と結論づけられています。半分納得、半分「?」状態。

 フィボナッチ数列を奇素数でわったときの余りの循環節について考えてきました。まだまだいろいろな疑問点(法3における√5をどう考えるのか、法5の場合をどうするのか等)はありますが、いちばん気になるのは、そもそもなぜ1と9(mod 10)の場合は√5が存在して、3と7(mod 10)の場合は√5が存在しないのか?ということ。ここを考えたいのなら「平方剰余の相互法則」というものを知る必要がありそうです。

 平方剰余の相互法則は、初等代数学というより数論の話らしいです。というわけで、数論のテキストをぼちぼち開いております。

初等代数学 | permalink

フィボナッチ数列を7でわったときの余り(2)

 フィボナッチ数列を7でわったときの余りが何桁ごとに循環するのかを、一般項を手がかりに調べていきます。

 まず、法7で考えた場合の第k項が0、第(k+1)項が1であれば、そのあとは順にたされていくだけなので、k桁ごとに循環していくことがわかります(現在、第0項を0として考えています)。よって、



となるようなkを求めます。上の式を満たすような条件の1つとして、



ということが考えられるので、



とおくと、下の式から



がいえそうです。これが必要十分条件かどうかわからないけど、少なくとも必要条件ではあると思う。そうなると、(1+√5)/2のほうを手がかりに、



と変形できるのではないかと考えました。右辺は、原始根のところで調べたように()、2の位数は3で、2、4、1が繰り返されます。

 一方、左辺の場合はどのように変化していくのだろう?ということで調べてみると、次のようになっています。



 8乗で初めて整数となるので、左辺が整数となる場合は、



という感じになりそうです。一方、右辺は、k=(3の倍数)+1のときに2、k=(3の倍数)+2のときに4、k=(3の倍数)のときに1だから、上の指数と見比べてみると見事に一致します。というか、最初に一致するのはk=16で、そのあとのkは16の倍数になっています。したがって、求める最小のkは16であり、法7の場合は16桁ごとに循環する。

 ・・・というのじゃだめかな??

 もしOKだとして、これを一般的なところで語ろうとするには、やはり二項定理から導かれる補助定理は必要になってくると感じました。

(つづく)

初等代数学 | permalink

フィボナッチ数列を7でわったときの余り(1)

 フィボナッチ数列を7でわった余りは、16桁ごとに循環します。

   

 地道に調べればすぐにわかる循環節の長さを、一般項で確かめてみたいというのがいまの願い。

 11や19を法として考えたときには、2乗して5になる数が存在するので、それをそのまま√5と考えてフィボナッチ数列の一般項にあてはめると、循環の桁数を求めることができました。

 じゃあ、2乗して5になる数が存在しない法の場合はどうすればいいか?ということで、F7に√5をとりいれ、F7^2をつくりました()。

 そんなふうにとりいれた√5をふつうの√5と同じに扱って大丈夫なのかという半信半疑な気持ちで作業をしましたが、いくつかの項について法を7として計算してみたら、確かに一致します。なんか不思議だ〜という思いもあるし、そもそもふつうの計算ってなんだ?という素朴な疑問もわいてきます。

 一般項を導くときの手がかりは漸化式だった、つまり、隣り合う2項の和が次の項になるというフィボナッチ数列の仕組みをもとにしているのでそこは問題ないと思うのですが、途中で使ったいろいろな計算はそもそも何を根拠に進めてきたのか?という根本的なところから不安になってきます。が、とりあえずその疑問はおいといて、いまは法7にとりいれた√5を信用することにします。

 砧文夫『初等代数学』ではどういうことになっているかというと、いつかの法について循環節を調べたあと、mod 10 で1か9の法pについては(p−1)桁で循環することが予想できるし、mod 10 で3か7の場合は(2n+2)桁で循環することが予想できる、というふうに話が始まります。そして、後者については二項定理から導かれる補助定理を使って証明がなされています。

 私の希望としては、(2n+2)桁で循環するらしいという予想がついていない前提で、かつ、直接、補助定理を使うことなく循環節の長さをnで表すプロセスの理由づけをしてみたいのですが、法7だけの場合ならなんとかこじつけられるけど、それを一般的なところまで引き上げるのはなかなかむずかしいです。

---------------

 しっかしあれです、砧文夫『初等代数学』を買ったばかりのころ、「でもまあ、こうやってあっちこっち読んでいくうちに、いつかは1冊読み終わることでしょう。」と思いましたが、実際、そうなりつつあります。有限体を学ぶとフィボナッチ数列のあらたな一面が見られるよ、という感じで書かれた最終章なのでしょうが、私としては逆に最終章のおかげで、フィボナッチ数列というなじみがあるものを手がかりに有限体の勉強ができている感じがします。「テキストはうしろから読むとよい」とどこかで読んだ記憶がありますが、なるほど確かにそうかもしれません。

(つづく)
初等代数学 | permalink

法7の世界に√5をとりいれる

 法7においては、√5に該当する数値を見つけることができませんでした。7を法として考えると、2乗して5になるような数が見つけられないからなのですが、ならばつくってしまおうじゃないかということで、法7において2乗すると5になるような数を√5としてとりいれてしまうことにします。

 つまり、有限体F7に新たに√5という元を導入し、

    a+√5b (a、bはF7の元) 

という形で表せる元全体の集合Sを考えます。集合Sには次の49個の元があります。



 この集合Sは体となるのかどうか?を考えたときに、わり算(かけ算に対する逆元が存在するかどうか)がちょっとあやうい感じです。そこで、

     (a+√5b)×(c+√5d)=1  

となるSの元 c+√5d が存在するかどうかを調べます。

 テキストでは、法3における x^2=−1 の解の導入について書かれてあるので、これを参考にすればいいと思ったものの、どうもよくわかりません。で、地道にがんばってみることにしました。まず、上の式の左辺を展開すると、

 (a+√5b)×(c+√5d)=ac+√5ad+√5bc+5bd
                  =(ac+5bd)+(ad+bc)√5

となり、これが1になるためには、ac+5bd=1、ad+bc=0 になればいいと考えました。こんなふうにa、b、c、dが入り混じった式を見ると行列を思い出すので、行列で表せないか考えてみたところ、次のような式ができました。

     

 法7においては a^2−5b^2=0 となることはないことを確認したうえで、左から逆行列をかけると、

   

 なので、たとえば 2+3√5 の逆元が知りたいときには、a=2、b=3だから、



 で、c=2、d=4より、2+√5 となります。これでどうだろうか。

 (2+3√5)(2+4√5)=64+14√5=1

 とりあえず望みの形にはなりました。こんなふうにふつーに計算していっていいのかどうか不安いっぱいですが、a、bが決まればそれに対応するc、dが決まるので、逆元は存在しそうな感じです。

 というわけで、7を法とする有限体F7に√5を加えて新しく集合S、つまり有限体F7^2をつくることができました。(たぶん)

(つづく)
初等代数学 | permalink

原始根から有限体の√5を考える(3)

 11を法としたとき、原始根は  2、6、7、8
 5になる場合は、2^4=5、6^6=5、7^2=5、8^8=5

 上記のように法11の場合は、5となる累乗の指数はすべて偶数ですが、他の法を考えたときに、指数に偶奇が入り混じるということがありうるのだろうか?というのがいま現在の疑問点です。

 考えてみれば、原始根のありがたいところは法11における元をすべて累乗で表せること。なので、上の4つの原始根を使った√5を、すべて1つの原始根で表せるのではなかろうか?と考えてみました。

 たとえば原始根2を選ぶと、他の原始根6、7、8は、順に 2^9、2^7、2^3 と表せます。これを使ってすべてを2の累乗で表すと、



 2は原始根なので位数は10。つまり、2の累乗をずっと考えていくと、10個ずつ同じ数が繰り返されることになる。だから、上記の指数は10を法として合同になっているはず。



 おお。確かにそうなっている。ということは、1つの原始根の累乗で表現したときの指数は、どれも (10の倍数)+α になっており、αの値は決まっているので、偶奇が入り混じることはないのではなかろうか。ということは、どれか1つの原始根について調べれば十分ということになるのではなかろうか。

 とりあえず最小の原始根で調べていくと、

  法13の場合、最小の原始根は2
  5となるのは9乗のとき(2^9=5)
  →9は奇数なので、法13における√5は存在しない。

  法17の場合、最小の原始根は3
  5となるのは5乗のとき(3^5=5)
  →5は奇数なので、法17における√5は存在しない。

  法19の場合、最小の原始根は2
  5となるのは16乗のとき(2^16=5)
  →16は偶数なので、法19における√5は存在する。

   そして、2^16=(2^8)^2=9^2 より、√5=9
   それ以外にも、2^(18の倍数+16)となる解があるか?
   2^34=(2^17)^2=10^2 → よって、√5=10
   2^52=(2^26)^2=(2^8)^2 
   2^70=(2^35)^2=(2^17)^2  
   2^88=(2^44)^2=(2^8)^2 
   なるほど、これから先は2つの値の繰り返しのようです。

 そんなこんなで、√5に該当する数、つまり x^2=5 のxにあてはまる数があるかどうかを見分ける方法についてはだいぶわかってきました。

 さらに、直接√5を見つけることができなくても、√5をつくりだしてしまうことができるらしいのです。

 実数の世界で x^2=−1 が解けなかったので、虚数をつくったように。
初等代数学 | permalink

原始根から有限体の√5を考える(2)

 フィボナッチ数列を11でわった余りは10桁で循環することがわかったので、そのことと法11での原始根との関わりを考えます。

 まず、法11での原始根を求めると、



 2、6、7、8とわかりました。言い換えると、2の累乗、6の累乗、7の累乗、8の累乗を11でわったときの余りには1〜10がすべて現れてくれます。ということは、その中に5も含まれているはず。実際、2^4、6^6、7^2、8^8 は5になっています。ってことは、こんなふうに↓考えてもいいんじゃなかろうか?



 そうすれば、4^2=5、7^2=5に帰着できるので、法11における√5は4、7と求まるぞ。(この場合は原始根を使わなくても、すでに上の表に現れているのですが…)

 だから、(ある原始根)^(偶数)=5 となっている場合をさがせば√5が見つかりそうです。でも、そのためにはすべての原始根を調べなくてはいけないのだろうか? 5になる場合が原始根によって奇数乗だったり偶数乗だったりすることがあるのだろうか?

(つづく)
初等代数学 | permalink

原始根から有限体の√5を考える(1)

 原始根といえば、Tetra's剰余グラフが懐かしいです。

 さて、原始根の定義を砧文夫『初等代数学』から抜き出すと、
 Fpの元aが原始根であるとは、aの位数が p−1 に等しいことをいう.
となっています。また、これを言い換えた定義も載っています。
 pと互いに素な整数aが法pでの原始根であるとは、aが(p−1)乗してはじめて、法pで1と合同になることをいう.

 たとえば法pを7として考えると、



 (7−1=)6乗してはじめて1となるのは3と5だから、法7での原始根は3と5ということになります。6乗してはじめて1が出るうえに(出るから)1乗から6乗の間に1〜6の数がすべて出てきてくれます。ここが原始根の便利さにつながっているのだろうと想像しています。

 砧文夫『初等代数学』(1993)によると、原始根を具体的に求める一般的な方法はないとのこと、ふつうはプログラムを書いて求めるのでしょう。そういえば剰余グラフのプログラムもそのひとつだったな〜!

 ちなみに、原始根の表を検索しているときに、数学者の密室さん>原始根原始根の表のページをみつけて「?」となってしまいました。7の原始根が3と4になっているけど、表の見方が間違っているのかな? 原始根のページに「aが原始根のとき、p−aも原始根となる(これは少し考えればわかる)。 」と書いてあるのですが、少し考えてもわからなかった私・・・。

 とりあえず50以下の奇素数の原始根についてはUN日記所さんの「原始根の一覧」と「最小の原始根とその累乗」を参考にさせていただきながら考えています。

(つづく)
初等代数学 | permalink

フィボナッチ数列を11でわったときの余り(2)

 フィボナッチ数列を11でわったときのあまりは10桁ごとに循環することがわかりました。8の累乗と4の累乗をもう一度みてみると、

   

 赤丸のところで1が出てくるので、このあとは同じ繰り返しになり、10桁ごとの循環がわかるわけですが、これってあれです、フェルマーの小定理

 pを素数とし、aをpの倍数でない整数とするとき

          

          「a^(p−1)をpでわると1余る」

 いまはp=11で素数、8も4も11の倍数ではないので、8^10≡1(mod 11)、4^10≡1(mod 11)が成り立ちます。そもそも8、4の部分が11の倍数となることはないわけで(11を法として考えており、0にもならない)、ここがほかのどんな数でも、その数の10乗を11でわると余りが1になります。それはつまり、10桁ごとの繰り返しになる(2桁、5桁で循環しないとも限らないけれど)、ということか。

 ということは、n=10のとき、8^n も 4^n も1になるので、その差は0、つまり第10項は mod 11 で0 → 11の倍数になっているはず。第10項は55で、確かに11の倍数。第20項はどうだろう? 第20項は7381で、7381÷11=671 あ、ほんとだ、わりきれる!

 11でなくても、19、29、31のように、一の位が1か9である素数pでわると、(p−1)桁ごとに巡回するのだそうです。一の位が1か9であるとき、√5の値が存在し、一般項の式にあてはめればそのことが確認できます。そして、7や13のように√5が存在しない場合でも、循環に規則性があるのだそうです。

 というようなことが、砧文夫『初等代数学』の第15章(最終章)に書いてあります。上記の規則性を理解するためには「第13章 有限体Fp^2」の勉強が必要だし、そのためには「第12章 2項方程式」と「第11章 指数」も勉強しなくちゃいけなさそう(つまり読んでいなかった)。そのためには第10章をおさえておくことが必須ということがわかりました。

 第10章は「原始根」です。
初等代数学 | permalink

フィボナッチ数列を11でわったときの余り(1)

 フィボナッチ数列を11でわったときの余りは、10ケタごとに循環するのだそうです。ほんとかしらん!?

   

 確かにそうなっていそう。このことを一般項で確認できるだろうか?

 まずは乗積表作成。

   

 次にフィボナッチ数列の一般項を確認。

   

 √5をどうにかしないといけないので、x^2=5の解と考えて、同じ数を2回かけたときに5となるような値を乗積表からさがすと、4×4=5、7×7=5より、11を法とした場合は√5=4、7と考えることができそうです。

 √5=4として考えることにして、先に一部計算しておくと、



 よって、11を法としたときのフィボナッチ数列の一般項は



 √5=7で計算しても同じ形になりました。8の累乗と4の累乗の循環を調べてみると、



 8の累乗は10項ごとに循環するし、4の累乗は5項ごとに循環するので、全体としては10項ごとに循環することになりそうです。

 なるほど、イメージがつかめてきました。

(つづく)
初等代数学 | permalink

P≠NP予想

 「P≠NP予想」というのは、ミレニアム懸賞問題のうちの1つで、ウィキペディアによると「計算量理論の未解決問題 P-NP問題 の答えが否であるという予想」だそうです。ちなみに、ミレニアム懸賞問題のうち、この問題だけが情報科学と重なる分野からの出題で、否定的に解決しても肯定的に解決しても、賞金が与えられるとか。

 P-NP問題というのは、「クラスP(多項式時間で計算可能な問題のクラス)とクラスNP(提出された答えが多項式時間で検算可能なクラス)が等しくないことを証明する問題」であり、端的な言い方をすると「検算可能な問題は全て計算可能であるか、可能でないか。」ということになるんだそうです。なんのことやら。

 なお、P≠NP予想は暗号理論(特に共通鍵暗号方式)と深く関わっており、P≠NPだからこそ共通鍵暗号は安全だ、ということになっているらしいです。いまのこの時代で数論方面の話題に興味をもつと、必ずといっていいほど暗号の話につながっていきます。というより、コンピュータの出現で暗号というものが出てきたから、数論がいきなり実用的になった、ということなのでしょう。

 ああ、でも確かに、少し意味がわかってきたRSA暗号のことを考えると、「検算可能な問題は全て計算可能であるか、可能でないか。」という問題の意味するところもなんとなくつかめるような気がしてきます。

 どっちにしろ、2変数、3変数の1次の問題としての「油分け算」からはかなり隔たったところにある話題かなぁ、そろそろ「油分け算」からはなれようかなぁ、と思い始めていたとき。

 ヒルベルトの第10問題について参考にさせていただいている以下のページを最後まで読んでいたら・・・

 (東北大学?) 仙台ロジック倶楽部ヒルベルトの第10問題

2変数2次の不定方程式についてその可解性が判定できることは上に述べたが,この問題は NP-完全であることも知られている(文献 [6]).とくに,ax2 + by = c (a,b,c > 0) の形の方程式の可解性だけで NP-完全であり,従ってそれを効率よく多項式時間で判定することが P = NP と同値である.この種の不定方程式については和算の成果もたくさんあるし,数論に強い我が国で P = NP 問題が解決されることを大いに期待したい.

 え、和算の成果!? ax2+by=c の式で表される和算って何だろう・・・!? 「油分け算」だけにハマっている場合ではないのだろうか。それとも、“この種の不定方程式”というのは ax+by=c を含めた話で、「油分け算」をさしているのだろうか? いや、「油分け算」は“不定方程式についての和算の成果”というような類のものではないと思うし・・・。(それから、「数論に強い我が国」だって! やっぱりそうなのかぁ〜>「数論と日本人」)

 ともかくも、もう少し和算について調べてみようと思い、「和算 不定方程式」で検索をしていたら、とても面白そうなページに行き当たりました。

日本数学史・天文学史日中不定方程式の系譜

 なるほど、「油分け算」だけにはまっている場合ではなかった!
初等代数学 | permalink
  

| 1/2PAGES | >>
サイト内検索