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

[quockhanh12]

Bài toán này có nguồn từ Romania TST 1991

[nhungvienkimcuong]

Cho dãy số nguyên dương $(a_n)_{n\ge 1}$ thỏa mãn

$$\text{UCLN}(a_m,a_n)=a_{\text{UCLN}(m,n)},\quad \forall m,n\ge 1.$$

CMR tồn tại dãy số nguyên dương $(b_n)_{n\ge 1}$ sao cho $a_n=\prod_{d\mid n}b_d$ với mọi $n\ge 1$.

Trong bài này mình sẽ kí hiệu $(u,v)$ thay cho $\text{UCLN}(u,v)$.

 

Đặt $b_1=a_1$, giả sử đã xác định được $b_k$ với mọi $k<n$. Như vậy cần xác định $b_n$, đặt

\[b_n:=\frac{a_n}{\prod_{d\mid n,d<n}b_d}.\]

Với cách xác định này thì $b_n$ thỏa mãn hệ thức đề cho, tuy nhiên chưa chắc vụ có phải số nguyên hay không, bước tiếp theo ta sẽ chứng minh $b_n$ nguyên. Giả sử $b_n\notin \mathbb{Z}$, khi đó tồn tại các số nguyên $A,B$ và số nguyên tố $p$ sao cho

\[b_n=\frac{A}{p\cdot B}\quad\text{và}\quad (A,p\cdot B)=1.\]

Nhận xét. Với $i<j<n$ sao cho $(b_i,b_j)>1$ thì $i\mid j$.

Giả sử $i\nmid j$ thì trong tích $\prod_{d\mid (i,j)}b_d$ không có sự xuất hiện của cả $b_i$ lẫn $b_j$. Dẫn đến

\[\frac{a_i}{(a_i,a_j)}=\frac{a_i}{a_{(i,j)}}=\frac{a_i}{\prod_{d\mid (i,j)}b_d}=b_i\cdot m\ \vdots\ (b_i,b_j)\]

Tương tự thì $\frac{a_j}{(a_i,a_j)}\ \vdots\ (b_i,b_j)$. Tới đây có được mâu thuẫn vì $\left(\frac{a_i}{(a_i,a_j)},\frac{a_j}{(a_i,a_j)} \right )=1$ và $(b_i,b_j)>1$.

Đặt tập hợp $I=\{i<n:i\mid n\ \text{và}\ p\mid b_i\}$, dựa vào nhận xét trên suy ra mọi phần tử của $I$ đều là ước của $i_m=\max_{i\in I}i$. Cuối cùng ta quan tâm đến $a_{i_m}$, vì $i_m\mid n$ nên $\frac{a_n}{a_{i_m}}\in \mathbb{Z}$. Mặt khác

\[\frac{a_n}{a_{i_m}}=b_n\prod_{\substack{d\mid n\\d\nmid i_m}}b_d=\frac{A\cdot\prod_{d\mid n,d\nmid i_m}b_d}{p\cdot B}\]

không thể là số nguyên vì tử số không chia hết cho $p$.

 

Ghi chú: Hình dáng bài này cũng từng xuất hiện trong hai kì thi là Iran 2001 và chọn đội tuyển Trung Quốc 2009.

Bài viết đã được chỉnh sửa nội dung bởi nhungvienkimcuong: 03-12-2022 - 16:16