Cho $(x_n)$ thỏa $x_0=0; x_1=45; x_{n+2}=3x_{n+1}+x_n$. Tìm số dư của $x_{2008}$ khi chia cho $2012$
Bài viết đã được chỉnh sửa nội dung bởi S dragon: 12-12-2016 - 20:50
Cho $(x_n)$ thỏa $x_0=0; x_1=45; x_{n+2}=3x_{n+1}+x_n$. Tìm số dư của $x_{2008}$ khi chia cho $2012$
Bài viết đã được chỉnh sửa nội dung bởi S dragon: 12-12-2016 - 20:50
Sống thì phải nỗ lực. Có nỗ lực mới thành công.
Cho $(x_n)$ thỏa $x_0=0; x_1=45; x_{n+2}=3x_{n+1}+x_n$. Tìm số dư của $x^{2008}$ khi chia cho $2012$
Hình như bạn chưa đề cập $x$ là gì thì phải.
Sự học như con thuyền ngược dòng nước, không tiến ắt phải lùi.
Hình như bạn chưa đề cập $x$ là gì thì phải.
xin lỗi bạn mình gõ nhầm
Sống thì phải nỗ lực. Có nỗ lực mới thành công.
Xét dãy $(y_{n}): y_{n+2}=3y_{n+1}+504y_{n}$ ( $y_{0}=1, y_{1}=45$ ). Dễ thấy $y_{n}\equiv x_{n} (mod 503)$ với mọi số tự nhiên n
Xét phương trình đặc trưng của $(y_{n})$ $y^{2}-3y-504=0 \Leftrightarrow y=24, y=-21$. Kết hợp với $y_{0}=0, y_{1}=45$, công thức số hạng tổng quát của dãy $(y_{n})$ là $y_{n}= 24^{n}-(-21)^{n}$. Vậy $y_{2008}= 24^{2008} -21^{2008}$
Vì 503 là số nguyên tố nên $24^{2008}\equiv (24^{502})^{4}\equiv 1^{4}\equiv 1 (mod 503)$ (định lý Fermat nhỏ). Tương tự $21^{2008}\equiv 1 (mod 503)$. Vậy $y_{2008}\equiv 0 (mod 503)$. Do đó, $x_{2008}\equiv y_{2008}\equiv 0 (mod 503)$.(1)
Xét dãy $(x_{n})$ ta có $x_{k+6}= 3x_{k+5}+x_{k+4}=...= 360x_{k+1}+109x_{k} \Rightarrow x_{k+6}\equiv x_{k} (mod4)$. Vì $2008\equiv 2 (mod 6)$ nên $x_{2008}\equiv x_{2}\equiv 3 (mod4)$ (Do $x_{2}= 3.45$ ) (2). Từ (1) và (2) ta có hệ :
$\left\{\begin{matrix} x_{2008}\equiv 0 (mod 503) & \\ x_{2008}\equiv 3 (mod 4) & \end{matrix}\right.$
Giải hệ trên ta được $x_{2008}\equiv 503 (mod 2012)$.
Bài viết đã được chỉnh sửa nội dung bởi VoHungHuu: 14-12-2016 - 18:29
"intelligent and condition makes first tiny advantages, is hard-working the key of all successes" - Vo Hung Huu :v
0 thành viên, 0 khách, 0 thành viên ẩn danh