mod pのフィボナッチ数列part2

  • 公開日時: 2016/12/05 16:33
  • 閲覧数: 222
  • コメント数: 1
  • カテゴリ: 研究・考察

 

是非僕の「mod pのフィボナッチ数列」というタイトルの投稿をご覧になってから読んでください

 

今回は5n±1型の素数を法としたときのループについて考えてみる

 

p=5のときは、長さが20のループ,4のループ,1のループがあったので、5n±1型の素数を法としたときのループを考えれば、すべての素数を法としたものを制覇できます

 

 

 

mod 11のときは、長さが10のループが11個、長さが5のループが2個、長さが1のループが1個できます

 

具体的に書くと

 

(0,1,1,2,3,5,8,2,10,1)

 

(0,2,2,4,6,10,5,4,9,2)

 

(0,3,3,6,9,4,2,6,8,3)

 

(0,4,4,8,1,9,10,8,7,4)

 

(0,5,5,10,4,3,7,10,6,5)

 

(0,6,6,1,7,8,4,1,5,6)

 

(0,7,7,3,10,2,1,3,4,7)

 

(0,8,8,5,2,7,9,5,3,8)

 

(0,9,9,7,5,1,6,7,2,9)

 

(0,10,10,9,8,6,3,9,1,10)

 

(1,8,9,6,4,10,3,2,5,7)

 

という長さが10のループが11個でき、

 

(1,4,5,9,3)

 

(2,8,10,7,6)

 

という長さが5のループが2個でき

 

(0,0)

 

という長さが1のループが1個できる

 

 

 

長さが10のループを円形に配置して、五角形状に足すと0になる

 

(0,1,1,2,3,5,8,2,10,1)を円形に配置すると

 

 

 

0

 

1      1

 

10              1

 

2                 2

 

8        3

 

5

 

こうなる

 

(0,1,1,2,3,5,8,2,10,1)というループの数を、ひとつ飛ばしに足せば0になる、と言い換えることもできる

 

実際にひとつ飛ばしに足すと、0+1+3+8+10=0(mod 11)となるし、1+2+5+2+1=0(mod 11)となる

 

 

 

では向かい合う数を足すとどうなるか

 

時計回りに足していくと、0+5=5,1+8=9,1+2=3,2+10=1,3+1=4となり、

 

(5,9,3,1,4)という数の並びが出る。長さが5のループ(前のふたつの数を足して次の数を作るループ)が出るのだ

 

 

 

(1,8,9,6,4,10,3,2,5,7)は向かい合う数を足すとすべて0になり、(0,0)というループが出る

 

 

 

 

 

■向かい合う数を足すとループが出ることをこれから証明する

 

 

 

今回は長さが10のループの場合を考え、並んでいる数を順番にa[1],a[2],……,a[10]と置く

 

前のふたつの数を足して次の数を作るので、a[n]+a[n+1]=a[n+2]となる

 

 

 

時計回りに向かい合う数を足すと

 

(a[1]+a[6],a[2]+a[7],a[3]+a[8],a[4]+a[9],a[5]+a[10])

 

となり、

 

a[n]+a[n+1]=a[n+2]なので、a[1]+a[2]=a[3],a[6]+a[7]=a[8]となり

 

(a[1]+a[6])+( a[2]+a[7])= a[1]+a[2]+ a[6]+a[7]= (a[3]+ a[8])

 

となっているからである。これは5n±1型の素数を法にしたときに限らず、一般の自然数を法としたループに対して言える

 

また、mod n(nは自然数)において、三角形状に足したり五角形状に足したりしたときもループが出ることは、同様にして証明できる

よって、mod nのどんなループも、ループ内の数の和が0になることが示せた。m角形状に足してできたループに、更にk角形状に足してループを作り、と続けると、最終的に(0,0)というループが出るからである


 

公序良俗に反する不適切な投稿を発見された方はこちらよりご報告ください

この投稿にフォローする

コメントをつけるにはログインが必要です。

最新10件表示

No メッセージ 投稿者 日時    
1
また、pが5n±1型の素数のとき、
mod pにおいてフィボナッチ数列のループの長さがいくつになるのか、をこうすれば知れるのではないか、という予想を立てました

(1±√5)/2を満たす数のうち、位数が大きいほうの位数がxのとき、フィボナッチ数列のループの長さもxになるという予想です
こう予想した理由は、modpで1に(1+√5)/2、あるいは(1-√5)/2を掛けていくと乗法群になり、また前の二つの数を足したものが次の数になるからです

また、2通りの長さのループのうち、短いループは必ず乗法群になっていそうに思いますが、これも予想に過ぎないです
あ・あっくん さん 2017/04/04 15:21:04 報告