Chứng minh tồn tại số tự nhiên thỏa mãn yêu cầu bài toán

Bài toán:

Cho trước $ k\in \mathbb{Z}^+$ và $ m$ lẻ .

Chứng minh rằng tồn tại $ n\in \mathbb{Z}^+$ sao cho $ 2^k| n^n-m$

Lời giải:

Ta sẽ chứng minh quy nạp theo $ k$.

Trường hợp $ k=1$ là hiển nhiên, chọn $ n=1$.

Giả sử rằng tồn tại $ n$ sao cho $ 2^k|n^n-m$,Đặt $ n=n_0$ hay $ 2^k|n_0^{n_0}-m$ hiển nhiên $ n_0$ lẻ

Tiếp theo xét 2 trường hợp

$ 1)$ Nếu $ 2^{k+1} | n_0^{n_0}-m$

Rõ ràng chỉ cần chọn $ n=n_0$.

$ 2)$ Nếu $ 2^{k+1}$ Không là ước của $ n_0^{n_0}-m$.

Đặt $ n_0^{n_0}-m=u\cdot 2^k$ Với $ u$ lẻ và theo định lý Euler,Cho mọi số lẻ $ a$ ta có $ a^{2^{k}}\equiv 1\pmod{2^{k+1}}$,Vì thế

$ (2^k+n_0)^{2^k+n_0}-m=(2^k+n_0)^{2^k}\cdot (2^k+n_0)^{n_0}-m\equiv (2^k+n_0)^{n_0}-m\\\equiv n_0^{n_0}+n_0\cdot n_0^{n_0-1}\cdot 2^k-m=(u+n_0^{n_0})2^k\equiv 0\pmod{2^{k+1}}$ Vì cả $ u$ và $ n_0$ đều lẻ.

Vì thế $ n=2^k+n_0$ thỏa mãn, nên ta có đpcm

Dùng bậc và hệ số cao nhất trong bài toán đa thức.

Bài toán (Hà Nam 2016):

Cho $P,Q,R$ là $3$ đa thức hệ số thực thỏa mãn: $P(Q(x))+P(R(x))=c$ $\forall x\in\mathbb{R}$ với $c=const\in\mathbb{R}$

CMR: $P(x)\equiv const$ hoặc $[Q(x)+R(x)]\equiv const$


Lời giải:


Đặt $deg P(x)=p$ và không mất tính tổng quát giả sử $deg Q(x)=q \ge r=degR(x)$. Nếu $P(x)\equiv const$ hoặc $Q(x)\equiv const$ thì khi đó $R(x)\equiv const$ nên hai trường hợp này là hiển nhiên. Ta xét $ p,q >0$, $r \ge 0$

Đặt $C_k (f(x))$ là hệ số của $x^k$ trong đa thức $f(x)$, vì thế $C_{\deg f(x)} (f(x)) \neq 0$ là hệ số cao nhất của $f(x)$. Đặt $a = C_{\deg P(x)} (P(x))$, $b = C_{\deg Q(x)} (Q(x))$, $c = C_{\deg R(x)} (R(x))$.
Nếu $q>r$, Khi đó $C_{pq} (P(Q(x)) + P(R(x))) = ab^p \neq 0$, Vô lí. Vì thế ta phải có $q=r=m$, $\Rightarrow$ $C_{pm} (P(Q(x)) + P(R(x))) = a(b^p +c^p)\neq 0$, Theo điều kiện giả thiết thì $b^p + c^p = 0$, dẫn tới $p$ lẻ và $c=-b$.


Xét $a(Q(x)^p + R(x)^p) = a(Q(x)+R(x)) S(x)$, Trong đó $ S(x) = Q(x)^{p-1} - Q(x)^{p-2}R(x) + \cdots - Q(x)R(x)^{p-2} + R(x)^{p-1}$. Ta có $C_{(p-1)m}(S(x)) = b^{p-1} - b^{p-2}(-b) + \cdots - b(-b)^{p-2} + (-b)^{p-1} = pb^{p-1} \neq 0$, nên $\deg S(x) \geq (p-1)m$ (Thực ra là bằng luôn).


Mặt khác nếu đặt $T(x) = P(Q(x)) + P(R(x)) - a(Q(x)^p + R(x)^p)$ ta có $\deg T(x) \leq (p-1)m$. Giả sử ngược lại $Q(x)+R(x)$ không là hằng số, $\Rightarrow$ $\deg(Q(x)+R(x)) \geq 1$, Ta phải có $\deg(a(Q(x)^p + R(x)^p)) = \deg(a(Q(x)+R(x)) S(x)) \geq 1 + (p-1)m$, và vì thế $\deg(P(Q(x)) + P(R(x))) = \deg(a(Q(x)^p + R(x)^p) + T(x)) \geq 1+(p-1)m >0$, Mâu thuẫn.


Vậy ta có đpcm.
Ps: Nếu tồn tại $Q,R$ mà $Q(x) + R(x) = C$ là hằng số, ta vẫn có thể tìm đa thức $P$ khác hằng bậc$ p$ lẻ bất kì, để $P(Q(x)) + P(R(x)) $ là hằng số. Chỉ cần lấy $P(x) = (2x-C)^p + k/2$

Tính chất của số nguyên tố có dạng $3k+2$

Cho $p$ là số nguyên tố thỏa mãn $3 | p-2$ khi đó $p | x^3 -y^3$ khi và chỉ khi $p | x-y$

Chứng minh:

Ta xét $ x,y $ không chia hết cho $p$ vì nếu chia hết cho p là hiển nhiên.
Nếu $ x \equiv y (mod p)$ thì $ x^3 \equiv y^3 (mod p)$
Ta chứng minh Nếu $ x^3 \equiv y^3 (mod p)$ thì $ x \equiv y (mod p)$

$x^{3} \equiv y^3 (mod p)  \Rightarrow x^{p-2}\equiv y^{p-2}(mod p)$

Theo định lý Fermat nhỏ:

$x^{p-1}\equiv y^{p-1} \equiv 1(mod p) \Rightarrow x^{p-2}(x-y) \equiv 0 (mod p) \Rightarrow x \equiv y (mod p)$

Xét ứng dụng của bổ đề trên:

Bài toán ( Chọn đội tuyển QG tỉnh Lạng Sơn 2016): Cho đa thức $P(x)=4x^3-18x^2+27x+m$. CMR: Với mỗi $m\in\mathbb{Z}$, $\exists n\in\mathbb{Z}$ sao cho $P(n)\vdots 107$

Lời giải:
Do (2, 107)=1 nên:
$P(n)\vdots 107 \Leftrightarrow  2P(n)\vdots 107$

Xét $G(x)=2P(x)=(2x-3)^2+27+2m$

Với mỗi $m$ ta có $G(0), G(1), . G(106)$ lập thành một hệ thặng dư đầy đủ mod 107. Thật vậy:

Nếu có $i ,j $ mà $  0\ge i, j \le 106$ mà $G(i) \equiv G(j) (mod 107)$ Thì khi đó theo bổ đề trên:
 $i \equiv j (mod 107)$ hay $ i=j$.

Vậy luôn tồn tại $n$ sao cho $P(n)\vdots 107$

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

Chứng minh tồn tại vô số số $n$ thỏa mãn: $n^2+2^n$ chia hết cho 1994

Lời giải:

Để $n^2+2^n$ chia hết cho 1994 thì trước hết n phải chẵn.

Ta chỉ cần chứng minh tồn tại số n sao cho $n^2+2^n$ chia hết cho 997.

Mà theo tiêu chuẩn Euler thì ta có:

$\left ( \frac{-1}{997} \right )=(-1)^{\frac{997-1}{2}}=1 (mod 997)$

Nên 997 có một bội dạng $a^2+1$. Do (996,997)=1 nên tồn tại hệ thặng dư thư gọn có dạng {996.1;996.2,...;996.996} mod 7

Suy ra tồn tại t để $(996t)^2+1$ chia hết  997

Mặt khác $2^{996t} \equiv 1 (mod 997)$

Vậy tồn tại vô số số n sao cho $n^2+2^n \vdots 1994$ 

Xây dựng tập hợp thỏa mãn đề bài

Đề: Chứng minh rằng tồn tại một tập A gồm vô hạn phần tử sao cho ta có thể trích tập hữu hạn B từ A, mà tổng các phần tử của B không phải là lũy thừa của một số nguyên

( Kvant)

Lời giải:

Xét tập hợp: A={$p^n.q^{n+1}: (p,q)=1, n \ge 1$}

Nếu B={$p^{n_1}.q^{n_1+1},...p^{n_k}.q^{n_k+1}$} là một tập hữu hạn trích từ A và $n_1<..n_k$

như vậy tổng các phần tử của B bằng: $p^{n_1}.q^{n_1+1}(1+p^{n_2-n_1}q^{n_2-n_1}+..)=p^{n_1}.q^{n_1+1}.N$

Mà $(N,p)=(N,q)=1$ nên ta có đpcm