一個鴿籠原理的簡單應用：模n的斐波那契數列是循環數列

    好久沒寫部落格文章了，前幾天被幾個學生嫌，她們覺得我「墮落了」，那就寫一篇關於最近在準備數論培訓課程裡用到的一個小小題目和有趣的延伸！

    我們校內的培訓講義裡有一道題：

    求證：對任意整數n，存在n的一個倍數，它是僅由數字2與0組成的。

    要解答這問題並不太難，只要考慮集合{2, 22, 222, 2222, ...}，在mod n的時候，至少會有兩個元素同餘，把這兩個數相減的差，就是由2和0所構成，且會被n整除。

    前幾天跟一個科裡的老師在聊，斐波那契數列(Fibonacci sequence: Fn+1 = Fn + Fn-1，F1 = F2 = 1)在mod n (這裡n > 2)的時候的表現，其中有一個直覺上存在的性質，就它會循環。當然我們這裡定義的循環指的是：存在一個正整數p，使得對於任意正整數i，都滿足Fp+i ≡ Fi (mod n)，而滿足這個同餘式最小的p，稱為斐波那契數列在模n時的最小週期。

    要證明「斐波那契數列在模n時會循環」的這個性質，基本上跟上面這培訓講義裡的題目用的方法差不多：

    數列的遞迴關係已經告訴我們，只要知道數列中相鄰的兩數，就能決定下一數為何，而這相鄰兩數在mod n時頂多只有n²種可能，所以考慮集合{(Fi, Fi+1) ∣ 1 ≦ i ≦ n²+1}的元素，在mod n時，必至少有兩組同餘，即Fi ≡ Fj，Fi+1 ≡ Fj+1 (mod n)，因此Fi+2 ≡ Fj+2 (mod n)，以此類推，可得Fi+3 ≡ Fj+3，Fi+4 ≡ Fj+4，…(mod n)，而且遞迴式也可以逆推回去，得Fi-1 ≡ Fj-1，Fi-2 ≡ Fj-2，…(mod n)，一直推回到斐波那契數列的首項，因此若i < j，則j – i就是其循環週期(但不一定是最小循環週期)。故斐波那契數列在模n時從第一項就開始循環，而且最小循環週期必小於n²。

    其實，上面這個證明，並不只適用在斐波那契數列，用同樣的方法，也可以得到任意的二階遞迴關係式，甚至三階、四階、…遞迴關係式，在模n時都會循環，只是並不能保證是否都是由首項就開始循環。