Dùng thặng dư bậc hai để giải phương trình nghiệm nguyên

Các kiến thức cần nhớ:
$$-1 \equiv a^2 (mod p) \Leftrightarrow p \equiv 1 (mod 4)\\
2 \equiv a^2 (mod p) \Leftrightarrow p\equiv 1,7 (mod 8)\\
-2 \equiv a^2 (mod p) \Leftrightarrow p \equiv 1,3 (mod 8)$$

Ta sẽ xét các ví dụ dùng thặng dư bậc hai để chứng minh một số trường hợp vô nghiệm của phương trình Mordell:

Vd 1: Giải phương trình $y^2=x^3+7$ trên tập số tự nhiên.

Giải:

Giả sử tồn tại $(x,y)$ thỏa mãn.
Nếu $x$ chẵn thì $y^2 \equiv 7 (mod 8)$ ( Loại)
Nên $x$ lẻ và $y^2+1=(x+1)(x^2-2x+4)$

Vì $x$ lẻ nên $x^2-2x+4=(x-1)^2+3 \equiv 3 (mod 4)$ vì thế $x^2-2x+4$ phải có một ước nguyên tố $p \equiv 3 (mod 4)$ (nếu không thì $x^2-2x+4 \equiv 1 (mod 4)$)

Ta suy ra $p| y^2+1$ nên $-1 \equiv y^2 (mod p)$ không được do $p \equiv 3 (mod 4)$

Vd 2: Chứng minh phương trình $y^2=x^3-5$ vô nghiệm tự nhiên.

Giải:

Giả sử tồn tại, xét mod 4: $y^2\equiv x^3-1 (mod 4)$
Xét $y \equiv 0,1,2,3 (mod 4), x \equiv 0,1,2,3 (mod 4)$  nhận thấy chỉ có giá trị chung của $y^2 (mod 4)$ và $x^3-1 (mod 4)$ là $0$ vì thế $y$ chẵn và $x \equiv 1 (mod 4)$
vậy:
$y^2+4=x^3-1=(x-1)(x^2+x+1)$, $x^2+x+1 \ge 3 \equiv 3 (mod 4)$ nên $-4$ là số chính phương mod $p$ hay $-1$ là số chính phương mod $p$ suy ra $p \equiv 1 (mod 4)$ mâu thuẫn với $p \equiv 3 (mod 4)$

Vd3: Chứng minh rằng phương trình $y^2=x^3-6$ không có nghiệm tự nhiên.
Giải:

Giả sử ngược lại. Nếu $x$ chẵn thì $y^2 \equiv -6 \equiv 2 (mod 8)$ ( vô lí với số chính phương )
Nên $x$ lẻ, $y$ lẻ và $x^3=y^2+6 \equiv 7 (mod 8)$ Ta cũng có: $x^3 \equiv x (mod 8 ) \forall x$ lẻ, nên $x \equiv 7 (mod 8)$
Viết lại:
$y^2-2=(x-2)(x^2+2x+4)$ với $x^2+2x+4 \equiv 7^2+2.7+4 \equiv 3 (mod 8)$. Vì thế phải có ước $p \equiv \pm 3 (mod 8)$ vì nếu không $x^2+2x+4 \equiv \pm 1 (mod 8)$. Ta có $2 \equiv y^2 (mod p) \Rightarrow p \equiv \pm 1 (mod 8)$ ( Mâu thuẫn)

Phép nghịch đảo trong đề thi Canada

Đề bài: (Canada 2007): Cho tam giác ABC có đường tròn nội tiếp (I) tiếp xúc các cạnh BC, CA, AB tại D, E, F tương ứng.  Gọi $ \omega,\,\omega_{1},\,\omega_{2}$ và $ \omega_{3}$ là lượt là đường tròn ngoại tiếp $ ABC,\, AEF,\, BDF$ và $ CDE$

Gọi $ \omega$ và $ \omega_{1}$ cắt tại $ A$ và $ P,\,\omega$ và $ \omega_{2}$cắt nhau tại $ B$ và $ Q,\,\omega$ và $ \omega_{3}$cắt nhau tại $ C$ and $ R.$

 CMR:  a) $ \omega_{1},\,\omega_{2}$ và $ \omega_{3}$ đồng quy

b) $ PD,\, QE$ và $ RF$ đồng quy

Giải:

a) Dễ thấy $ \omega_{1},\,\omega_{2}$ và $ \omega_{3}$ cùng đi qua I

b) Qua phép nghịch đảo tâm I ta đưa về bài toán. Cho tam giác DEF có A, B, C là trung điểm của EF, DF, DE. (ABC) cắt EF tại A', DF tại B', DE tại C'. CMR (IDA'), (IEB'), (IFC') đồng quy tại một điểm khác I

Dễ thấy trực tâm H của tam giác DEF có cùng phương tích với 3 đường tròn này và ta có I là điểm chung của 3 đường tròn, suy ra IH là trục đẳng phương chung của 3 đường tròn. Giả sử đường tròn thứ nhất giao với đường tròn thứ 2 và thứ 3 tại hai điểm U, V khác nhau khi đó U, V, I thẳng hàng và đường thẳng UV cắt đường tròn tại 3 điểm (vô lí) Vậy ta có đpcm

Hai tiêu chuẩn Eisentein mở rộng

Tiêu chuẩn mở rộng 1: Cho đa thức $P(x)=\sum_{i=0}^{n}a_ix^i$ là một đa thức hệ số nguyên. Nếu tồn tại số nguyên tố p thỏa mãn những điều kiện sau:
i) $ a_n$ không chia hết cho p
ii)  Các hệ số $a_0, a_1, .. a_{n-k}$ chia hết cho p
iii) $a_0$ không chia hết $p^2$.

Chứng minh rằng đa thức $P(x)$ không có ước là $G(x)$ mà bậc của G lớn hơn hoặc bằng k.

Chứng minh:

Giả sử ngược lại: $P(x)=f(x)g(x)$ với: $f(x)=\sum_{i=0}^{r}b_ix^i, g(x)=\sum_{i=0}^{s}c_ix^i, r+s=n, r,s \ge k$. Và do $r+s=n$ và $r,s \ge k$ suy ra $r, s \le n-k$
Dễ thấy rằng $a_0=b_0c_0$ mà $a_0 \vdots p$ và $a_0 \not \vdots p^2$ nên trong hai số $b_0$ và $c_0$ có đúng một số chia hết cho p, giả sử là $b_0$. Ngoài ra do $a_n=b_rc_s$ không chia hết cho $p$ nên $b_r$ không chia hết cho $p$. Suy ra, tồn tại k là số nhỏ nhất mà $0<k \le r \le n-k$ sao cho $b_k$ không chia hết cho p. Khi đó $b_0, b_1,..b_{k-1}$ đều chia hết cho $p$. Ta cũng có:
$a_k=b_kc_0+b_{k-1}c_1+..+b_0c_k$ là hệ số chia hết cho p. Tuy nhiên, do $b_kc_0 \not \vdots p$ và $b_0, b_1,..b_{k-1} \vdots p$ nên đây là điều mâu thuẫn. Vậy điều giả sử là sai và ta có đpcm.

Tiêu chuẩn mở rộng 2  (Tham khảo từ bài viết của STEVEN H. WEINTRAUB ): Cho $f(x)=a_nx^n+..+a_0$ là đa thức hệ số nguyên. Và giả sử có một số nguyên tố p sao cho $p$ không là ước $a_n$, $p$ là ước $a_i, (i=0,1,..n-1)$) và với một số số k nào đó $p^2$ không là ước của $a_k$. Gọi $k_0$ là giá trị nhỏ nhất của $k$ Khi đó nếu $f(x)=g(x)h(x)$ thì $min( deg g(x), deg h(x)) \le k_0$.

Chứng minh:
Gọi $deg g(x)=d_0$, $deg h(x)=e_0$. Gọi $d$ là số mũ nhỏ nhất của $x$ trong đa thức g(x) mà hệ số của nó không chia hết cho $p$, định nghĩa tương tự cho $e$. Khi đó:
$g(x)=x^dg_1(x)+pg_2(x)$,$h(x)=x^eh_1(x)+h_2(x)$. với các đa thức $g_1, g_2, h_1, h_2$ là các đa thức hệ số nguyên và các hệ số của $g_1, h_1$ không chia hết cho $p$. Khi đó:
$f(x)=g(x)h(x)=x^{d+e}g_1(x)h_1(x)+p(x^eh_1(x)g_2(x)+x^dh_2(x)g_1(x))+p^2g_2(x)h_2(x)$

mà theo giả thiết thì tất cả hệ số của $f(x)$ trừ $a_n$ đều chia hết cho $p$. Điều này dẫn đến $d+e=n$ vì nếu không ($x^{d+e}$ nhân với hệ số tự do trong $g_1(x)$ và $h_1(x)$ sẽ có được điều mâu thuẫn). và $ d \le d_0, e \le e_0$ $d_0+e_0=n$ nên $d=d_0, e=e_0$.

Vì thế $g(x)=b_{d_0}x^{d_0}+pg_2(x), h(x)=c_{e_0}x^{e_0}+ph_2(x)$ Trong trường hợp này ta có:

$f(x)=g(x)h(x)=a_nx^n+ph_2(x)b_{d_0}x^{d_0}+pg_2(x)c_{e_0}x^{e_0}+p^2g_2(x)h_2(x)$.

Vậy $k_0 \le min( deg g(x), deg h(x)) $ (điều phải chứng minh)
Lưu ý:
Với k=0 ta có tiêu chuẩn Eisentein f(x) bất khả quy còn $k=1$ nếu f(x) không có nghiệm hữu tỉ thì f(x) cũng bất khả quy.

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$

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.

Đồ thị lưỡng phân

Định nghĩa:

Đồ thị lưỡng phân là đồ thị G=(V; E) mà tập đỉnh V có thể phân hoạch thành hai tập hợp X, Y sao cho tập cạnh E chỉ gồm các cạnh nối hai đỉnh không cùng một tập hợp. Ta còn kí hiệu đồ thị lưỡng phân này là G=(X,Y;E)

Một tính chất cơ bản để nhận biết đồ thị lưỡng phân là định lý sau đây

Định lý: Một đồ thị G là đồ thị lưỡng phân khi và chỉ khi mọi chu trình của nó có độ dài chẵn.

Chứng minh. Giả sử G=(X,Y; E) là một đồ thị lưỡng phân. Khi đó dọc theo chu trình bất kỳ của G các đỉnh thuộc tập X và tập Y lần lượt kế tiếp nhau. Do đó, khi trở về đỉnh xuất phát đầu tiên, ta phải đi qua một số chẵn các đỉnh, do đó số cạnh ( bằng số đỉnh) của chu trình là một số chẵn.

Đảo lại, giả sử rằng G là một đồ thị mà tất cả các chu trình của G đều có độ dài chẵn. Ta sẽ chứng minh rằng tất cả các thành phần liên thông của G đều là các đồ thị lưỡng phân, và do đố G cũng là đồ thị lưỡng phân.

Thật vậy, giả sử rằng $G_1$ là một thành phần liên thông của G và $P_0$ là một đỉnh của đồ thị $G_1$. Với mỗi đỉnh P của đồ thị $G_1$, ta chọn một đường đi W nối đỉnh $P_0$ với đỉnh P. Nếu đường đi W có độ dài chẵn thì đỉnh P thuộc tập X, còn nếu đường đi W có độ dài lẻ thì đỉnh P được lấy vào tập Y. Sự phân loại các đỉnh của đồ thị $G_1$ không phụ thuộc vào cách chọn đường đi W. thật vậy, nếu có đường đi W với độ dài chẵn và đường đi W' với độ dài lẻ nối đỉnh $P_0$ với đỉnh P thì đồ thị $G_1$ sẽ có chu trình với độ dài lẻ, mâu thuẫn với giả thiết ban đầu.

Với các thiết lập tập hợp X và Y này, các đỉnh của đồ thị $G_1$ hoặc thuộc tập hợp X hoặc thuộc tập hợp Y. Bây giờ ta chuwgns minh rằng $G_1$ chỉ có các cạnh nối các đỉnh không cùng mọt tập hợp với nhau mà thôi. Thật vậy, giả sử rằng có hai đỉnh P và Q kề nhau trong đồ thị $G_1$ thì chugns không thể cùng thuộc một tập hợp X hoặc Y, nếu không từ $P_0$ ta có thể đi đến đỉnh P rồi tới đỉnh Q bởi cạnh (P,Q) và trở về đỉnh $P_0$ với một đường đi lẻ cạnh, điều không thể xảy ra trong đồ thị G do G chỉ có chu trình với số chẵn cạnh mà thôi. Như vậy đồ thị G là đồ thị lưỡng phân với hai tập đỉnh X và Y.

Trường hợp nhỏ của định lý nổi tiếng của Erdos và Selfridge

Một định lý nổi tiếng của Erdos và Selfridge, một giả thuyết hơn 150 năm, nói rằng: Tích các số tự nhiên liên tiếp không thể là lũy thừa của một số nguyên.

Ta xét trường hợp tích 3 số tự nhiên liên tiếp.

Gọi n là số nguyên, và ta viết bài toán lại:

$n(n+1)(n+2)=x^z(x,z \in N, z \ge 2)$

Chú ý rằng: $n(n+2)=(n+1)^2-1$

Nên:

$\left\{\begin{matrix}
n+1=a^z & \\
(n+1)^2-1=b^z &
\end{matrix}\right.(a,b)=1\Rightarrow a^{2z}-b^z=1\Rightarrow (a^2-b)(..)=1\Rightarrow a^2=b+1\\\Rightarrow (b+1)^z-b^z=1 \Rightarrow z=1$

Vậy không tồn tại z thỏa mãn đề bài hay ta đã cm cho trường hợp $n=3$