Dùng cấp để tìm các số thỏa mãn bài toán

Đề bài: Tìm $p,q$ nguyên tố sao cho $2^{p}+2^{q}\vdots (pq).$

Lời giải:

Dễ thấy $(p,q)=(2,2),(3,2),(2,3)$.

Nếu $p,q \ge 3$. Dùng định lý Fermat nhỏ, ta có $2^{p} \equiv 2 \pmod{p}$. Vì thế $p|2^{q-1}+1$. Ta được $2^{q-1} \equiv -1 \pmod{p}$.

Đặt $q-1=2^x \cdot y$ với $x,y \in \mathbb{N}^*, \; \gcd(y,2)=1$ và đặt $2^y=k$, ta được $2^{q-1}=(2^y)^{2^x} \equiv -1 \pmod{p} \Rightarrow k^{2^{x+1}} \equiv 1 \pmod{p}$.

Ta có $\text{ord}_p(k) |2^{x+1}$.

Vì $k^{2^x} \equiv -1 \pmod{p}$ nên $p \nmid k^{2^x}$. Vì thế $\text{ord}_p(k) \nmid 2^x$. 

Vậy $\text{ord}_p(k)=2^{x+1}$. 

Ta cũng có $2^{p-1} \equiv 1 \pmod{p}$. Nên $2^{x+1}|p-1$. Đặt $p=2^{u} \cdot l+1$ với $u,l \in \mathbb{N}^*, \; \gcd (l,2)=1$ thì $u \ge x+1$.

Tương tự ta cũng được $x \ge u+1$, mâu thuẫn

Vậy câu trả lời là $\boxed{ (x,y)=(2,2),(3,2),(2,3) $

Bài tập tương tự: Tìm $p,q$ nguyên tố sao cho $5^p+5^q \vdots pq$ ( lưu ý là phải xét thêm $p,q =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$

Một số tính chất số học của dãy tuyến tính

Cho dãy $(x_n)$ sao cho:
$x_0=1, x_1=1$, $x_{n+2}=ax_{n+1}+bx_n (a,b \in Z)$

Khi đó ta có:

1)$x_{m+n}=bx_{n}x_{m-1}+x_{n+1}x_{m}$

2) $x_{kn} \vdots x_n$

Ứng dụng:

Mở rộng đề thi chọn đội tuyển Ninh Bình 2016: Giả sử $p,q$ là hai số nguyên tố , dãy $(u_n)$ được xây dựng như sau:

$$\left\{\begin{matrix} u_0=0 & & & \\ u_1=1 & & & \\ u_n=pu_{n-1}-qu_{n-2}\forall n\geq 2,n \in \mathbb{N} & & & \end{matrix}\right.$$

Tìm tất cả $p,q$ biết tồn tại số tự nhiên $k$ để $u_{3k}=-3$

áp dụng tính chất 2) suy ra $u_3 |3 $ hay  $p^2-q|3$. Kết hợp điều kiện p,q nguyên tố nên có thể dễ dàng tìm được p,q

Chứng minh đa thức bất khả quy bằng nghiệm của nó

Bài toán 1: Cho đa thức $f(x)=\sum_{i=0}^{n}a_ix^i$ là một đa thức có hệ số nguyên, sao cho $|a_0|$ là một số nguyên tố và:

$\left |a_o  \right |\geq \sum_{i=1}^{n}\left |a_i  \right |$
Chứng minh f(x) bất khả quy.

Lời giải:

Gọi $\alpha $ là nghiệm của $f(x)$, giả sử $|\alpha| \le 1$ thì:

$|a_0|=\left |\sum_{i=1}^{n}a_i\alpha ^i  \right | \leq \sum_{i=1}^{n}\left |a_i  \right |$ Mâu thuẫn.

Vậy mọi nghiệm $\alpha$ của f(x) phải có modulue >1

Giả sử đa thức f(x)=g(x).h(x) gọi $b_0, c_0$ lần lượt là hệ số tự do của g và h

Do: $a_0=b_0.c_0$ Do $a_0$ nguyên tố nên có thể giả sử $b_0=1$

Gọi hệ số cao nhất của g là b khi đó theo viet:
$\left |\prod_{i=1}^{k}\alpha _{i}  \right |=\left |\frac{1}{b}  \right |\leq 1$ (k là bậc của g, k>0)

Mà $|\alpha _{i}|$ đều lớn hơn 1 do đã chứng minh.
Vậy ta có điều mâu thuẫn.

Bài toán 2: (Tiêu chuẩn perron): Cho đa thức nguyên $f(x)=\sum_{i=0}^{n}a_ix^i$ Khi đó nếu:

$|a_{n-1}|>|a_0|+|a_1|+..+|a_n|$ thì đa thức này bất khả quy.

Chứng minh:

Không mất tính tổng quát có thể giả sử $a_n=1$ (vì P(x) bất khả quy khi và chỉ khi P(x)/$a_n$ bất khả quy ). Ta có $|a_{n-1}|>|a_0|+|a_1|+..+|a_n|$ ta sẽ chứng minh tổng tại đúng 1 nghiệm thực hoặc phức của P(x) có module lớn hơn 1.

Giả sử đa thức P(x) có nghiệm z sao cho |z|=1. thì:

$|a_{n-1}|=|a_{n-1}z^{n-1}=|a_0+a_1z+..+z^n \ge |1|+|a_0|+|a_1|+..|a_{n-2}|$

Mâu thuẫn. Ngoài ra còn $f(0)$ khác 0 nên tích các module các nghiệm >1 nên tồn tại một nghiệm $x_1$ sao cho $|x_1|>1$. Đặt
$g(x)=x^{n-1}+b_{n-2}x^{n-2}..+b_1x+b_o=f(x)/(x-x_1)$

Rõ ràng nghiệm của g(x) chỉ có module nhỏ hơn 1 vì nếu không dng nhất hệ số , và kết hợp giả thiết suy ra:

$\left | b_{n-2} \right |+|x_1| >1+|b_{n-3}|-..+|b_0||x_1| \Leftrightarrow (\left |x_1  \right |-1)>(\left |x_1  \right |-1)(\sum_{k=0}^{n-2}\left | b_k \right |)\\\Rightarrow \sum_{k=0}^{n-2}\left | b_k \right | < 1\\\sum_{i=0}^{n-2}b_i.z^{i-n}=0 \Rightarrow \sum_{k=0}^{n-2}\left | b_k \right | \geq \left | \sum_{i=0}^{n-2}b_i.z^{i-n} \right |=1$
Điều mâu thuẫn này cho thấy f(x) chỉ có đúng một nghiệm có mod lớn hơn 1.

Như vậy nếu đa thức p=f.g thì 1 trong hai đa thức f và g phải có tất cả các nghiệm nhỏ hơn 1 dẫn đến hệ số tự do bé hơn 1 điều này mâu thuẫn với f,g là đa thức hệ số nguyên.

Bài toán về sự phân bố số chính phương và số nguyên tố

Bài toán: Xét tất cả các số nguyên tố $p_1 < p_2 <..p_n<..$ Đặt $a_n=p_1+p_2+..+p_n$. Chứng minh rằng với mọi n nguyên dương, nằm giữa $a_n$ và $a_{n+1}$ có ít nhất một số chính phương.

Giải:
Bổ đề: Với $n \ge 4$ thì $p_{n+1} > 2\sqrt{p_1+p_2+..+p_n}+1$
Chứng minh:
Với n=4, đúng.

Giả sử đúng với n=k tức là:
$p_{k+1} > 2\sqrt{p_1+p_2+..+p_k}+1$

Hay là $(p_{k+1}-1)^2 >4 (p_1+p_2+..+p_k)$

Ta cần chứng minh: $(p_{k+2}-1)^2 >4 (p_1+p_2+..+p_{k+1})$

Hay chỉ cần chứng minh: $(p_{k+2}-1)^2 \ge (p_{k+1}-1)^2 +4p_{k+1}$

Điều này tương đương $(p_{k+2}-p_{k+1})(p_{k+2}+p_{k+1}-2) \ge 4p_{k+1}$

Điều này là hiển do khoảng cách 2 số nguyên tố liên tiếp bé nhất là 2. Vậy ta có đpcm

Quay lại bài toán
Với n=1, thì giữa 2 và 5 tồn tại 4 là số chính phương.
Tương tự cho n=2,3,4

Giả sử đúng với n=k tức là giữa $a_k$ và $a_{k-1}$ tồn tại ít nhất một số chính phương, ta gọi $a^2$ là số chính phương lớn nhất trong các số chính phương đó.

$(a+1)^2 > a_{k}$

Áp dụng bổ đề thì $p_{k+1}>2a+1$ nên $a_{k+1} >(a+1)^2$.

Bất đẳng thức Bonse

Cho $p_1=2, p_2=3,..$ là dãy tăng các số nguyên tố. Chứng minh rằng:

$p_1p_2..p_n >p_{n+1}^2$

Giải.

Đặt $A_k=p_1p_2...p_k$ và $a_k=k.p_1p_2..p_{n-1}-p_n$ với $1 \le k \le p_n -1$. Ta thấy rằng $a_k$ không chia hết cho $p_i$ (với i=1,..n) suy ra $a_k \ge p_{n+k}$ (Do là dãy tăng). Chọn k=$p_n-1$ ta được $a_k=A_n-A_{n-1}-p_n>p_{p_n+n-1}>p_{3n-1}$ ( có thể chứng minh $p_n \ge 2n$ bằng quy nạp). Từ đây ta nhận thấy với $n \ge 6$ thì

$p_1..p_n>(p_1..p_{[n/2]})^2>p_{3[n/2]-1}^2>p_{n+1}^2$