如何解答這道關於數論的題目？

01-01

The American Mathematical Monthly

Vol. 107, No. 3 (Mar., 2000), pp. 281-282

附：

這個題還真有點難度……

把原來的遞推式寫成 $a_n = a_{n-4} + a_{n-3}$ ，再把這兩項分別展開，一直展開到變成 $a_0, a_1, a_2, a_3$ 中的一項為止，這其中只有 $a_0$ 和 $a_3$ 兩項不為0，這兩項各自累積了多少次，取決於有多少種不同的序列 ${c_k}$ 使得 $c_k in {3, 4}, 1 le k le K$ 且 $sum_k c_k = n$ ，其中 $c_1 = 4$ 的是 $a_0$ 的累加次數， $c_1 = 3$ 的是 $a_3$ 的累加次數。

我們列出一個不定方程 $4A + 3B = n$ ，其中 $A ge 1, B ge 1, A,B in {old N}$ ，則 $a_n$ 可以表示為

$a_n = sum_{A,B}a_3C_{A+B-1}^A+a_0C_{A+B-1}^{A-1}= sum_{A,B}3C_{A+B-1}^A+4C_{A+B-1}^{A-1}$

當n與3,4互質時，改寫成同餘方程：

$4A + 3B equiv n (mod 12)$

這個方程的解可以表示為A = n - 3u， B = 3n - 4v，代回原來的方程當中有

$13n - 12(u+v) = n$

$u + v = n$

$frac{n}{4} le u le frac{n}{3}, frac{2n}{3} le v le frac{3n}{4}$

$A + B = 4n - 3u - 4v = u$

於是有

$a_n = sum_{frac{n}{4} le u le frac{n}{3}}3C_{u-1}^{n-3u}+4C_{u-1}^{n-3u-1}$

$=sum_{frac{n}{4} le u le frac{n}{3}}3C_{u}^{n-3u}+C_{u-1}^{n-3u-1}$

下面證明當n為質數時， $3C_{u}^{n-3u}+C_{u-1}^{n-3u-1}$ 都是n的倍數，從而 $a_n$ 是n的倍數。

由於 $C_{u}^{n-3u}$ 是整數，也就是

$frac{u!}{(n-3u)!(4u-n)!}$ 是整數

又由於 $C_{u-1}^{n-3u-1}$ 是整數，也就是

$frac{(u-1)!}{(n-3u-1)!(4u-n)!}$ 是整數

由於n是質數，所以n與u互質，所以n-3u與u互質，而

$C_{u}^{n-3u} = frac{uC_{u-1}^{n-3u-1}}{n-3u}$ 是整數，所以 $frac{C_{u-1}^{n-3u-1}}{n-3u}$ 是整數。

所以

$3C_{u}^{n-3u}+C_{u-1}^{n-3u-1} = frac{C_{u-1}^{n-3u-1}}{n-3u}(3u + n-3u) = frac{C_{u-1}^{n-3u-1}}{n-3u} n$

所以

$3C_{u}^{n-3u}+C_{u-1}^{n-3u-1}$ 是n的倍數。因此n是質數時， $a_n$ 是n的倍數。

之前看錯題了。不過用原來的方法還是很容易證明題目。

注意到這個遞推數列的特徵方程沒有重根。所以通項是根的n次冪的線性組合。容易看出前四項恰好是A^n的trace. 所以對任何n， a_n=tr(A^n). 對任何p, 由Frobenus我們有 a_p mod p=tr(A)^p mod p=0 mod p.

----------------

這個是顯然的。考慮Z^4-&>Z^4 的線性映射A: (x_0,x_1,x_2,x_3) -&>(x_1,x_2,x_3,x_1+x+2). 那麼(a_n,a_{n+1},a_{n+2},a_{n+3})=A^n((4,0,0,3)), 且 A屬於 GL_4(Z). 對任何素數p， A mod p 屬於 GL_4(F_P) 是有限群。所以存在N，有A^N mod p= id. 所以

(a_N,a_{N+1},a_{N+2},a_{N+3}) mod p=A^N((4,0,0,3)) mod p= (4,0,0,3) mod p. 所以a_{N+1}=0 mod p.