これは私はだいぶ前（2013年頃）に知った事実で
知恵ノートのどこかに書いた気がするけど消えてしまっていた。
自分の中での「数学感動秘話」の1つだと思っている。

数列 a[n+2]=u*a[n+1]+v*a[n] を素数pで割った余りについて考える。
1つの興味はその周期である。
もう1つの興味は、a[0]=0のとき、a[N]=0となるようなNである。
（これをニセ周期と呼ぶことにしておく。周期はニセ周期でもある。）

特にu=v=1で初項をa[0]=0,a[1]=1とすればフィボナッチ数列である。

【結論】
[1] a[n]をpで割った余りについて、特性方程式 x^2=ux+v の判別式をDとすると
[◇] Dがpの倍数のとき 周期 p(p-1) を持つ。
[△1] Dがmod pで平方剰余のとき周期 (p-1) を持つ。
[△2] Dがmod pで平方非剰余のときニセ周期 (p+1) を持つ。周期としては(p^2-1)を持つ。

[2] k≧1とする。a[n]をp^kで割った余りが周期Rを持つなら、
　a[n]をp^(k+1)で割った余りは周期pRを持つ。

【指摘】
・[1]で書いた周期は最短周期とは限らない。（数値によってはもっと短い周期がある。）
・[2]では、pが奇素数のときは、Rがmod p^kの最短周期ならば、pRはmod p^(k+1)の最短周期となる。
（p=2の場合は特殊な事情がある）
・Dが平方剰余かどうかは、x^2≡ux+v (mod p) が整数解を持つかどうかと同値である。
・縦ベクトル [a[n+1],a[n]] を [a[n+2],a[n+1]] に変換する2次正方行列：
[u v],
[1 0]
の位数を考えるとラグランジュの定理より周期(p-1)p(p+1)を持つことが言える。
しかし上記の場合ごとの詳しい結果を得るためには下記の整数論的な考察が必要になる。

【ネットでの言及】
ネットではあまり見当たらなかった。
以前に比べてどう説明すれば良いのかもだいぶ分かってきたし改めて書いておこうと思ったのである。

特にフィボナッチ数の場合の言及はいくつか出会った：
・nf1...さんが「本で読んだ結果からすぐに出る」と書いた回答がある
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q10187647915
・もちもちモチーフの最初のpdfにも詳しく取り上げられている
https://asuka-math.amebaownd.com/posts/2851257
----------------
【説明】

一般項を使う視点が一番良いと思う。

＜一般項＞

[事実]
a[n+2]=u*a[n+1]+v*a[n] の一般項は
[◇] 特性方程式が重解αを持つとき a[n] = (An+B)*α^n
[△] 特性方程式が解α≠βを持つとき a[n] = A*α^n+B*β^n
の形をしている

[根拠]
答えを知っていればどのように変形すれば証明できるか分かるだろう
[◇] a[n]/α^n = b[n]とおく
　さらに b[n+1]-b[n]=c[n]とおくと c[n+1]=c[n] を得る
[△] a[n+1]-α*a[n] = b[n] とおくと b[n+1]=βb[n] を得る

----
＜有限体での一般項＞

上記を有限体で行うのである。
具体例を使って説明するほうが伝わりやすいと期待する。

a[n+2]=3a[n+1]+a[n] (特性方程式の判別式は13、解は(3±√13)/2)の場合
（この題材はhttps://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q11205665376を使った）

[事実]
[◇] p=13 のとき a[n] ≡ (An+B)*α^n (mod p)
[△] p≠13 のとき a[n] ≡ A*α^n+B*β^n (mod p)
の形をしている。ここでA,Bは整数で、α,βについては：

[◇]のαは整数をとることができる。
[△1] 13がmod pで平方剰余のときはα,βは整数をとることができる。
[△2] 13がmod pで平方非剰余のときはα,βは整数をとることができない。
次のような視点が必要になる
・Q(√13)の整数環でのイデアル(p)を法とする合同式として解釈する視点
・有限体 F_p^2 の元に関する等式として解釈する視点
1つ目の視点の方が具体的であるのでここでは主にこちらを使うことにする。
（2つ目の視点の方が、代数体に依らない記述ができるという利点はある）
（しかしQ(√13)の整数環での合同式の定義についての説明は省略する)
13がmod pで平方非剰余という条件によって(p)が素イデアルとなる状況である（＊あとで補足）


[根拠（最初に提示した結論までも一緒に示す）]

先と同じように変形するのである。
[◇] p=13 の場合 x^2≡3x+1 (mod 13) は x≡3/2≡8 (mod 13) を重解に持つ
　a[n]/8^n≡b[n] とおく。5^n*a[n]≡b[n] とも書ける。
　a[n]の漸化式の両辺に5^(n+2)を掛けてb[n]の漸化式を作ると
　b[n+2] ≡ 15b[n+1]+25b[n] ≡ 2b[n+1]-b[n]
　従って確かに b[n+2]-b[n-1] ≡ b[n+1]-b[n] であるので b[n]≡An+B とおけて
　a[n]=(An+B)*α^nとなる
　An+Bは周期pを持ち、α^nは周期(p-1)を持つので、a[n]は周期p(p-1)を持つ。

[△1] p=17 の場合 13は平方剰余であり、x^2≡3x+1 (mod 17) は解 x≡(3±9)/2≡-3,6 (mod 17)を解に持つ
　a[n+1]+3a[n]≡b[n] とおくと b[n+1]≡6b[n] が成り立つような操作によって、
　a[n] ≡ A*(-3)^n + B*(6)^n を得るはずである。
　(-3)^n, (6)^n は周期(p-1)を持つので、a[n]は周期(p-1)を持つ。

[△2] p=7 の場合 13は平方非剰余であり、x^2≡3x+1 (mod 13)は整数解を持たない
　Q(√13)の整数環での合同というものを考えるとα,β=(3±√13)/2 を使って
　a[n] ≡ A*α^n + B*β^n (mod p) と書ける。
　これの周期の考察には「フロベニウス写像の性質」を使う（＊あとで補足）。
　それは「α,βをQ上共役なQ(√13)の整数環の元とする。
　正の有理素数pが生成するQ(√13)のイデアルが素イデアルならば
　α^p≡β (mod p), β^p≡α (mod p) が成り立つ」という性質である。
　（α＝βが有理数の場合は通常のフェルマーの小定理の内容となる）
　よって a[p+1+k] ≡A*α^pαα^k + B*β^pββ^k ≡ A*βαα^k + B*αββ^k≡ αβ*a[k]
　このことからニセ周期(p+1)を持つことが分かる。
　また(αβ)^n の周期をsとすると a[n] は周期s(p+1)を持つことが分かる。
　一般には sは(p-1)の約数であるので a[n]は周期 (p^2-1)を持つことが分かる。
　今回の具体例の場合ではαβ=-1 なので、周期としては2(p+1)を持つことまで言える。

---
＜補足１：代数体の整数環での合同と、剰余体の言葉＞

Q(√13)の整数環でのイデアル(p)が素イデアルとなるという事実は、次の内容を述べている
(a+b√13)(c+d√13)≡0 (mod p) ならば (a+b√13)≡p または (c+d√13)≡p が成り立つ。

これは(a^2-13b^2)(c^2-13d^2)≡0 なので (a^2-13b^2)と(c^2-13d^2)のどちらかはpの倍数で
(a^2-13b^2)がpの倍数ならばa,bはともにpの倍数というふうにして説明できる。
後半で、13がpを法として平方非剰余であるという条件を使う。

Q(√13)の整数環を(p)で割った剰余環は、位数p^2の有限体であり、既約剰余類は(p^2-1)個ある。
従ってフェルマーの小定理と同様にして、α^49≡α (mod p)が成り立つことが言える。
ここからも（フロベニウス写像の性質を使わずに）a[n]が周期(p^2-1)を持つことが分かるが、
ニセ周期については、上記のフロベニウス写像の性質を使った議論が必要となると思う。

ちなみにpが平方剰余の場合でも、Q(√13)の整数環として議論しても良い。
その場合はpは2つの素イデアルに分解する。
例えば (17) は π=(17,9+√13) と π~=(17,9-√13) に分解する
この場合はそれぞれの剰余体は位数がpの有限体であり、
α^p≡α (mod π), α^p≡α (mod π~) が成り立つのでα^p≡α (mod p) も成り立つ状況である。

（ただしこの場合は(p)は素イデアルではないのでmod pの合同式の取り扱いに注意が必要かもしれない：
A=-3, B=6, C=(-3+√13)/2, D=(-3+√13)/2 とおくと
x^2-3x-1 ≡ (x-A)(x-B) ≡ (x-C)(x-D) (mod 17) という現象が起きるが、
これはQ(√13)の整数環を(17)で割った剰余環が整域でないので矛盾ではない。）

＜補足２：フロベニウス写像の性質の特殊な場合＞

以下の現象がある：
[△1] Dがmod pで平方剰余の時 (√D)^p≡√D (mod p)
[△2] Dがmod pで平方剰余の時 (√D)^p≡-√D (mod p)
なぜなら (√D)^p＝D^{(p-1)/2} √D であり、この挙動はいわゆる「オイラーの規準」で説明される。

これは、 (A+B)^p≡A^p+B^p (mod p) [二項定理による] を使えば次のように拡張される。
[△1] Dがmod pで平方剰余の時 (A+B√D)^p≡A+B√D (mod p)
[△2] Dがmod pで平方剰余の時 (A+B√D)^p≡A-B√D (mod p)

これで2次体の場合のフロベニウス写像の性質の説明がつく。
この説明は、このノートを書いたあとから思いついた。
ここから、(p)が2次体の整数環で素イデアルかどうか等考えなくても、
[△1][△2]両方について目的の結果を直接得られる。
（しかし敢えてうるさく書くと、理想的にはmod pの意味を適切に理解している必要はある）

---
＜指数のべきの場合＞
Q(√13)の整数環の元として、
α^n が mod p^kを法として周期 R を持つとき、α^n は mod p^(k+1)を法として周期 pR を持つ
という事実に由来する。これは「指数持ち上げの補題」として知られる現象（の代数体バージョン）で、
p進数のexpとlogによって乗法群の構造を観察するのが見通しが一番良いが
説明するのはちょっと大変なので、もちもちモチーフのpdfに書いてあることだけコメントしておく。

---
＜3項間以外の場合＞

通常の有理数範囲での一般項を求める手順と同様の手順で、mod pでの一般項を得ることができる。
例えば4項間の場合で、3次の特性方程式がmod pで重解を持たない場合は
a[n] ≡ A*α^n + B*β^n + C*γ^n (mod p) と書くことができる。

これを適切に解釈するにはやはり
・適当な代数体の整数環でのイデアル(p)を法とする合同式として解釈する視点
あるいは
・有限体 F_p^k の元に関する等式として解釈する視点のような視点
が必要になる。
今回のように代数体が具体的には分からない場合には、
有限体の拡大体の視点の方が記述がしやすいが、説明はさぼる。

大雑把にα,β,γが何次の無理数なのかというところが重要になってくる。
具体的には、
・特性方程式が、mod pで既約な場合はα,β,γはF_p^3の元として考える必要があり、a[n]は周期(p^3-1)を持つ。
・特性方程式が、mod pで1次式と2次式に分解する場合は、α∈F_p, β,γ∈F_p^2な状況で、a[n]は周期(p^2-1)を持つ
などのように考察できるとだけ紹介しておき、意図が伝わることを期待する。