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

[supermember]

Bài toán :

Cho dãy $ \( a _n \)$ được xác đinh như sau :

$a_1 \ = \ 2$ và

$a_{n \ + \ 1 } \ = \ 2^{a_n} \ \forall n$ thuộc $N^{*}$

Chứng minh rằng với mọi số nguyên dương $m$

thì dãy số dư trong phép chia các phần tử của dãy

$\( a_n \)$ cho $m$ là dãy hằng kể từ $1$ chỉ số nào đó

Bài này là 1 trong những tác phẩm rất tuyệt vời của thầy Hero TVƠ

Xin chia sẻ với các bạn


Hero TVƠ Y An forever

[Mashimaru]

Dãy số mà từ một số hạng nào đó trở đi là hằng số gọi là dãy dừng. Hằng số ấy gọi là hằng số dừng và số hạng mà từ đó trở đi dãy trở nên hằng gọi là điểm dừng của dãy. Đó là các khái niệm sẽ được sử dụng trong lời giải sau ^^'

Ta chứng minh bài toán bằng qui nạp theo $m$.

Thật vậy, tại $m=1$, dãy luôn nhận giá trị bằng $0$.

Giả sử kết luận đúng với mọi $k<m$ tùy ý, ta sẽ chứng minh nó cũng đúng với $m$. Lúc này, ta xét 2 trường hợp:

1. Số $m$ ở dạng biểu tích của các thừa số nguyên tố là $m=p_1^{s_1}p_2^{s_2}...p_k^{s_k},s\geq 2$ (nghĩa là $m$ không là lũy thừa của bất kì một số nguyên tố nào).

Theo giả thiết qui nạp, $\forall i=\overline{1,k}$, dãy $\(a_n\) \(mod p_i^{s_i}\)$ là dãy dừng.

Gọi điểm dừng của các dãy trên tương ứng là $n_1,n_2,...n_k$ và đặt $N=\max{\{n_1,n_2,...n_k\}}$ thì $\forall n\geq N$, dãy $\(a_n\) \(mod m\)$ không đổi.

Vậy trong trường hợp đang xét, dãy $\(a_n\) \(mod m\)$ là dãy dừng.

2. Số $m$ là lũy thừa của một số nguyên tố, đặt dạng khai triển của $m$ là $m=p^{\alpha}$.

2a. Nếu $p=2$ thì $a_n\equiv 0\(mod m\)$ nên dãy $\(a_n\) \(mod m\)$ hiển nhiên là dãy dừng.

2b. Nếu $p>2$ thì từ $\varphi\(m\)<m$ theo giả thiết qui nạp, dãy $\(a_n\)\(mod\varphi\(m\)\)$ là dãy dừng. Ta đặt:

$a_n\equiv r\(mod \varphi\(m\)\),\forall n\geq k$ hay $a_n=q_n\varphi\(m\)+r$

Khi đó, $\forall n\geq k$, theo định lý Euler, ta đều có:

$a_{n+1}=2^{a_n}=2^r.\(2^{\varphi\(m\)}\)^{q_n}\equiv 2^r\(mod m\)$

Do vậy, dãy $\(a_n\) \(mod m\)$ cũng là dãy dừng với hằng số dừng là $2^r \(mod m\)$.

Từ 2 trường hợp trên ta suy ra kết luận của bài toán.

Kết thúc chứng minh

Nhân tháng 8 có ngày sinh nhật của em, lời giải này...dành tặng cho em, người yêu của anh!

[DinhCuongTk14]

bài này có vẻ cũ rồi nhỉ có 1 bài khá là liên quan tới bài toán này như sau :
Cho 3 số nguyên cố định $a,b,c $.Cmr ta luôn tìm được$ x$ thỏa mãn $a^x +x \equiv b(mod c)$

[Mashimaru]

Bài này là thế nào hả anh??? Em chỉ giải được trong trường hợp $c$ nguyên tố thôi.

Trong trường hợp hạn hẹp đó, em xin làm như sau ạ:

Rõ ràng nếu $a|c$ thì chỉ cần chọn $x=b$ là bài toán đã được giải quyết.

Nếu $a\not\|c$ thì vì $c$ nguyên tố nên $\gcd{\(a;c\)}=1$.

Cũng vì $c$ nguyên tố nên $\gcd{\(c;\varphi\(c\)\)}=1$, do đó tập hợp $\{\varphi\(c\);2\varphi\(c\);...;c\varphi\(c\)\}$ lập thành một hệ thặng dư đầy đủ $\(modc\)$.

Xét dãy số sau: $u_n=a^{n\varphi\(c\)+m}+n\varphi\(c\)+m$ trong đó $m$ là các số nguyên dương tùy ý.

Theo định lý Euler, ta có $a^{n\varphi\(c\)+m}\equiv a^m\(modc\)$ nên $u_n\equiv \(a^m+m\)+n\varphi\(c\)$, trong đó $\(a^m+m\)$ là cố định và $n\varphi\(c\)$ thay đổi, nhưng vì $\gcd{\(c;\varphi\(c\)\)}=1$ nên $\(u_1;u_2;...;u_c\)$ cũng lập thành một hệ thặng dư đầy đủ $\(modc\)$.

Từ đây suy ra $\exists k\in\{1;2;...;c\},u_k\equiv b\(mod c\),\forall a,b,c$.