關於Lucas數列的一個有趣的問題

09-11

關於Lucas數列的一個有趣的問題

來自專欄仔仔的數學小屋71 人贊了文章

昨天知友@私信問了我一個數論問題（2017中科大入學考試的壓軸題）

設數列 $(x_n)_{n=0}^infty$ 滿足 $x_{0}=0, x_1=1$ 和遞推關係 $x_{n+2}=ax_{n+1}+bx_n$ ，求所有正整數對 $(a, b)$ 使得對於所有 $m, ninmathbb{N}$ 都有 $gcd(x_m, x_n)=x_{gcd(m, n)}$

我覺得答案應當是所有互質的正整數對 $(a, b)$

我在搜索相關資料的時候，在外網的一篇論文上發現了對於這一類問題（Generalized Lucas數列的Strong Divisibility）一個利用了矩陣和行列式的巧妙技巧。原論文是英文而且篇幅很長，所以我整理了一下用這個技巧證明的主要過程。

首先介紹一下第一類Lucas數列（Lucas Sequence of the 1st Kind）

如果數列 $(U_n(p, q))_{n=0}^infty$ 滿足遞推關係 $U_{n+1}=pU_n-qU_{n-1}$ （其中 $p, q$ 為整數）以及初始條件 $U_0=0$ 和 $U_1=1$ ，那麼稱 $(U_n(p, q))_{n=0}^infty$ 為一個（第一類）Lucas數列。Lucas數列可以看成斐波那契數列的一個推廣。

然後需要了解一下什麼是（強）整除數列（Divisibility Sequence）

如果整數數列 $(a_n)$ 滿足如果 $mmid n$ 那麼 $a_mmid a_n$ ，那麼稱 $(a_n)$ 為一個整除數列。另外，如果 $(a_n)$ 滿足對於所有 $m, ninmathbb{N}$ 都有 $gcd(a_m, a_n)=a_{gcd(m, n)}$ ，那麼稱 $(a_n)$ 為一個強整除數列（Strong Divisibility Sequence）。顯然所有強整除數列都是整除數列。

所以我們要證明的就是：

當且僅當整數 $p, q$ 互質時，第一類Lucas數列 $(U_n(p, q))_{n=0}^infty$ 是強整除數列

和原題有一點不同的是Lucas數列的遞推關係是減號，但是並不影響

首先我們容易得到

$egin{pmatrix}p&-q\1&0end{pmatrix}^n=egin{pmatrix}U_{n+1} & -qU_{n}\U_n&-qU_{n-1}end{pmatrix}$

這隻需注意到

$egin{pmatrix}U_{n+1}\U_{n}end{pmatrix}=egin{pmatrix}p &-q \1&0end{pmatrix}egin{pmatrix}U_{n}\U_{n-1}end{pmatrix}$

用歸納法也很好證明，我們記 $M=egin{pmatrix}p&-q\1&0end{pmatrix}$ ，然後重點來了

因為在模 $U_n$ 意義下 $M^n$ 是對角矩陣，所以 $M^{nk}=(M^n)^k$ 在模 $U_n$ 意義下也是對角矩陣，這就說明了 $U_{n}$ 整除 $U_{kn}$ ，所以 $(U_n(p, q))_{n=0}^infty$ 是整除數列

驚了d(?д??)！居然還有這種證法。但是還沒完，只證明了 $(U_n(p, q))_{n=0}^infty$ 是整除數列，還沒證明 $p, q$ 互質時它是強整除數列

因為 $(U_n(p, q))_{n=0}^infty$ 是整除數列所以我們容易得到 $U_{gcd(m, n)}mid gcd(U_m, U_n)$ ，所以我們只需要證明當 $p, q$ 互質時 $gcd(U_m, U_n)mid U_{gcd(m, n)}$ 即可。當 $gcd(U_m, U_n)=1$ 直接就能整除，所以我們只用考慮 $gcd(U_m, U_n)>1$ 的情況，接下來重點又來了(??????) ?！

由裴蜀定理，存在整數 $a, b$ 使得 $am+bn=gcd(m, n)$ ，又因為在模 $gcd(U_m, U_n)$ 的意義下 $M^m$ 和 $M^n$ 都是對角矩陣，所以 $M^{gcd(m, n)}=(M^m)^a(M^n)^b$ 也是對角矩陣，這就說明了 $gcd(U_m, U_n)mid U_{gcd(m, n)}$

所以 $gcd(U_m, U_n)=U_{gcd(m, n)}$ 。這裡 $a, b$ 會有一個不是正的，但因為 $M$ 是可逆的（對角矩陣的逆矩陣也是對角矩陣）所以不影響。