Bổ đề bất đẳng thức số học và đề USA MO 1995

Ta có một bổ đề bất đẳng thức số học dùng để đánh giá bội chung nhỏ nhất như sau:
Với mọi số nguyên dương n tồn tại một số $c_n >0$ sao cho:

$lcm(m,m+1,m+2,..m+n)>c_nm(m+1)(m+2)..(m+n)$ (ký hiệu lcm, gcd lần lượt là bội chung nhỏ nhỏ và ước chung lớn nhất)

Chứng minh:

Ta có:

$lcm(m,m+1,m+2,..m+n)=lcm(lcm(m,m+1,..m+n-1),m+n)\\=\frac{lcm(m,m+1,..m+n-1)(m+n)}{gcd(lcm(m,m+1,..m+n-1),m+n)} \\ \ge \frac{lcm(m,m+1,..m+n-1)(m+n)}{gcd(m(m+1)(m+2)..(m+n-1),m+n)}\\ \geq \frac{lcm(m,m+1,..m+n-1)(m+n)}{n!}$

Bằng quy nạp ta chứng minh được:
$lcm(m,m+1,m+2,..m+n)\ge\frac{m(m+1)(m+2)..(m+n)}{n!(n-1)!..1!}$

Như vậy bổ đề được chứng minh.
Ta xét bài toán sau:

(USA MO 1995) Cho dãy số nguyên $(a_n)_{n \ge 0}$ thỏa mãn điều kiện sau:

i) $m-n | a_m -a_n$

ii) tồn tại đa thức f(x) sao cho |a_n| \le $f(n)$ với mọi $n \ge 0$

Chứng minh rằng tồn tại đa thức g(n) sao cho $g(n)=a_n$ với mọi $n \ge 0$

Lời giải:



Giả sử $P$ có bậc $d$. Đặt $Q$ là đa thức bậc cao nhất $d$ với $Q(x)=q_x$ cho $0\leq x\leq d$. Vì $q_x$ là những số nguyên, $Q$ là đa thức hệ số hữu tỉ và tồn tại $k$ để $kQ$ có hệ số nguyên. Vì thế $m-n|kQ(m)-kQ(n)$ với mọi $m,n\in \mathbb N_0$.




Ta sẽ chứng minh rằng $Q$ là đa thức cần tìm


Cho $x>n$ Ta có

$ kq_x \equiv kq_m\pmod{x-m}\text{với mọi }m\in[0,d]$

Vì $kQ(x)$ thỏa mãn điều kiện nên $kq_m=kQ(m)$,

$kq_x\equiv kQ(x)\pmod{x-m}\text{ với mọi }m\in [0,d] $
( lưu ý kQ(x) -kQ(m) chia hết x-m)
và vì thế

$ kq_x\equiv kQ(x)\pmod{\text{lcm}(x,x-1,\ldots, x-d)}. \;(1) $

Vì $P(x), Q(x)$ có bậc là $d$, Vì thế với $x$ đủ lớn ( $x>L$) Ta có $\left|Q(x)\pm\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}\right|>P(x)$. Vì (1) $kq_x$ phải lớn hơn một bội của $\text{lcm}(x,x-1,\ldots, x-d)$ so với $kQ(x)$; vì thế $q_x$ phải lớn hơn một bội của $\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}$ với $Q(x)$, với $x>L$ Ta phải có $q_x=Q(x)$.




Bây giờ với mọi $y$ ta có $kQ(y)\equiv kQ(x)\equiv kq_x \equiv kq_y\pmod{x-y}$ với $x>L$. Vì $x-y$ có thể lớn tùy ý nên ta phải có $Q(y)=q_y$, đpcm

Đa thức hệ số hữu tỉ

Đề bài: Tìm tất cả đa thức hệ số hữu tỷ $P(n)$ thoả $P(n)\mid 2^{n} - 1$ với mọi số tự nhiên $n$.

Lời giải:

Các kết quả cơ bản dùng cho lời giải
i) $n = \pm 1$ là số nguyên duy nhất thoả mãn $\pm n\mid 2^{|n|} - 1$
ii) $P(n) \mid P(P(n) + n)$
Lưu ý là ta chỉ quan tâm các đa thức nhận giá trị nguyên với $n$ tự nhiên nên ii) vẫn đúng.
Theo đó, ta có $P(n) \mid P(P(n) + n) \mid 2^{P(n) + n} - 1$. Mặt khác, $P(n)\mid 2^{n} - 1$
Tóm lại ta thu được $P(n) \mid 2^{P(n)}$. Suy ra $P(n) = 1$ hoặc $P(n) = -1$ có vô hạn nghiệm, đến đây dễ suy ra rằng $P(x) = 1$ với mọi $x$ hay $P(x) = -1$ với mọi $x$

Chứng minh i)

Giả sử p là ước nguyên tố nhỏ nhất của $n$ theo Định lý Fermat nhỏ:

 

$2^{p-1} \equiv 1 (mod p)$

mà $(p-1, n)=1$ Suy ra $ord_p(2)=1$ hoặc bằng $p-1$ trường hợp bằng 1 là đơn giản.

Xét trường hợp $ord_p(2)=p-1$ Khi đó: $n=(p-1)k+r( 0<r<p-1)$

Suy ra: $2^n \equiv 2^r \equiv 1 (mod p)$ vô lí do $ord_p(2)=p-1 >r$

Vậy ta có đpcm.

ii) Ta dùng bổ đề đơn giản sau: $P(a)-P(b) \vdots a-b$