Chủ đề này có 1 trả lời

[nguyenthehoan]

Bài toán. Cho $p$ là một số nguyên tố cho trước. Xét dãy số $(a_n)$ thỏa mãn điều kiện.

i) $a_k=k, \forall k=0,1,...,p-1$

ii) $a_n=a_{n-1}+a_{n-p},\forall n\geq p$

Tìm số dư trong phép chia $a_{p^{2014}+1}$ cho $p$.

[WhjteShadow]

Bài toán. Cho $p$ là một số nguyên tố cho trước. Xét dãy số $(a_n)$ thỏa mãn điều kiện.

i) $a_k=k, \forall k=0,1,...,p-1$

ii) $a_n=a_{n-1}+a_{n-p},\forall n\geq p$

Tìm số dư trong phép chia $a_{p^{2014}+1}$ cho $p$.

Hê hê bài này t làm hơi bị bựa, Hoàn có cách khác tự nhiên hơn không (Cách này hơi mò mẫm)

Ta có $a_n=a_{n-1}+a_{n-p}=a_{n-2}+2a_{n-p-1}+a_{n-2p}\\=a_{n-3}+3a_{n-p-2}+3a_{n-2p-1}+a_{n-3p}\\=a_{n-4}+4a_{n-p-3}+6a_{n-2p-2}+4a_{n-3p-1}+a_{n-4p}\\=.....=\sum_{i=0}^t C_t^i .a_{n-ip+i-t} \text{ với n>tp}$

Phân tích đến $t=p$ với $n>p^2$, và để ý $C^{i}_{p}\vdots p\forall i=\overline{1;p-1}$ ta có :

$$a_{n}\equiv a_{n-p}+a_{n-p^2-1}\pmod{p}$$

$$\Leftrightarrow a_{n-1}\equiv a_{n-p^2-1}\pmod{p}$$

Vậy dãy có số dư tuần hoàn chu kì $p^2-1$ theo mod $p$, để ý thêm $p^{2014}+1$ chia $p^2-1$ dư 2 nên $a_{p^{2014}+1}\equiv a_{2}\equiv 2\pmod{p} \,\square$

Bài viết đã được chỉnh sửa nội dung bởi WhjteShadow: 24-12-2013 - 19:44