Chu kỳ cơ sở của dãy Fibonacci modulo m là một số chẵn


Chúng ta đã biết là với mỗi số nguyên dương m, dãy Fibonacci modulo m là một dãy tuần hoàn. Với mọi số nguyên dương m, gọi \pi (m) là chu kỳ cơ sở của dãy đó. Trong bài này tôi sẽ giới thiệu một chứng minh cho kết quả sau:

Định lí (D. D. Wall, 1960). Với mọi số nguyên m>2, \pi (m) là một số chẵn.

Chứng minh. Với mỗi số nguyên dương m, cố định nó. Gọi k là số nguyên dương bé nhất sao cho F_k chia hết cho m,\varphi là tỷ số vàng.

F_k\equiv 0\pmod{m} nên F_{k+1}\equiv F_{k-1}\pmod{m}, do đó F_{k+i}\equiv F_{k+1}F_i\pmod{m},\quad\forall i\in\mathbb{N}^*.

Từ kết quả trên ta có F_{k\text{ord}_m(F_{k+1})+1}\equiv F_{k\text{ord}_m(F_{k+1})+2}\equiv F_{k+1}^{\text{ord}_m(F_{k+1})}\equiv 1\pmod{m}, suy ra \pi (m)=k\text{ord}_m(F_{k+1}).\quad (*)

Bây giờ trong \mathbb{Z}[\varphi], ta có \varphi^k\equiv (1-\varphi)^k\pmod{m}, suy ra F_{k+1}\equiv \varphi^k\pmod{m}, nhưng ta biết \varphi^{4k}\equiv 1\pmod{m}, do đó \pi (m)\in \{k,2k,4k\}. Nếu \pi (m) không phải là số chẵn thì \pi (m)=kk là số lẻ. Khi đó từ (*) ta được \text{ord}_m(F_{k+1})=1, suy ra 1\equiv \varphi^k\pmod{m}. Kết hợp điều này với \varphi^{2k}\equiv (-1)^k\pmod{m} ta thu được m\mid 2, vô lý.


Một chứng minh khác có trong bài của Wall ở AMM, Vol 67, trang 525.