ỨNG DỤNG CỦA MỘT MỆNH ĐỀ VÀO GIẢI
CÁC BÀI TOÁN SỐ HỌC
Trần Quốc Nhật Hân (THPT chuyên Lê Quý Đôn, Đà Nẵng.)
Phạm Quang Toàn (THCS Đặng Thai Mai, Tp Vinh, Nghệ An)
Ban Biên Tập: Phạm Quang Toàn và perfectstrong (Trần Quốc Nhật Hân) là các ĐHV có năng lực và nhiệt tình của VMF. Đây là bài viết của các em dành tặng diễn đàn tròn 8 tuổi.
1. Mở đầu
Trước hết ta đến với bài toán nhỏ sau.
Bài toán. Giả sử $p=k.2^t+1$ là số nguyên tố lẻ, $t$ là số nguyên dương và $k$ là số tự nhiên lẻ. Giả thiết $x$ và $y$ là các số tự nhiên mà $\left( x^{2^t}+y^{2^t} \right) \vdots \ p$. Chứng minh rằng khi đó $x$ và $y$ đồng thời chia hết cho $p$.
Giải. Giả sử trái lại $x \not\vdots p$, suy ra $y \not\vdots p$.
Do $p$ là số nguyên tố nên theo định lý Fermat nhỏ ta có $$\left\{\begin{matrix}
x^{p-1} \equiv 1 \pmod{p} & & \\
y^{p-1} \equiv 1 \pmod{p} & &
\end{matrix}\right.$$
Theo giả thiết thì $p-1=k.2^t$, do đó $$\left\{\begin{matrix}
x^{k.2^t} \equiv 1 \pmod{p} & & \\
y^{k.2^t} \equiv 1 \pmod{p} & &
\end{matrix}\right.$$
Từ đó ta có $$x^{k.2^t}+y^{k.2^t} \equiv 2 \pmod{p}. \qquad (1)$$
Theo giả thiết thì $$x^{2^t}+y^{2^t} \equiv 0 \pmod{p}.$$
Do $k$ lẻ nên $$
x^{k.2^t}+y^{k.2^t} = \left( x^{2^t} \right)^k+ \left( y^{2^t} \right)^k \ \vdots \left( x^{2^t}+y^{2^t} \right) \Rightarrow \left( x^{k.2^t}+y^{k.2^t} \right) \equiv 0 \pmod{p} \qquad (2)$$
Từ $(1)$ và $(2)$ suy ra điều mâu thuẫn. Vậy giả thiết phản chứng sai. Do đó $x,y$ đồng thời chia hết cho $p$.
Từ bài toán trên, áp dụng với $t=1$ là có kết quả:
Cho $p$ là số nguyên tố dạng $4k+3$. Khi đó nếu $x^2+y^2$ chia hết cho $p$ thì $x$ và $y$ đều chia hết cho $p$.
Lời giải. Ta dùng phản chứng. Giả sử $a$ và $b$ không đồng thời chia hết cho $p$. Ta có các trường hợp sau:
Trường hợp 1. Nếu $a \vdots p, \ b \not \vdots p.$
$$\Rightarrow a^2 \vdots p; b^2 \not \vdots p \Rightarrow a^2+b^2 \not \vdots p.$$
Mâu thuẫn với giả thiết ban đầu.
Trường hợp 2. Nếu $a \not \vdots p, \ b \vdots p.$
Tương tự trường hợp 1, trường hợp này cũng mâu thuẫn với giả thiết.
Trường hợp 3. Nếu $a \not\vdots p, \ b \not\vdots p.$
Vì $p$ nguyên tố nên theo định lý Fermat nhỏ ta có:
$$\begin{array}{l}
a^{p-1} \equiv 1 \pmod{p} &
b^{p-1} \equiv 1 \pmod{p}
\end{array}$$
$$\begin{array}{l}
\Leftrightarrow a^{4k+2} \equiv 1 \pmod{p}, \ b^{4k+2} \equiv 1\pmod{p} & \Leftrightarrow (a^2)^{2k+1} \equiv 1 \pmod{p}, \ (b^2)^{2k+1} \equiv 1 \pmod{p} & \Rightarrow (a^2)^{2k+1}+(b^2)^{2k+1} \equiv 2 \pmod{p}
\end{array}$$
Do $p$ là số nguyên tố có dạng $4k+3$ nên $p \ge 3$, nên \begin{equation}
(a^2)^{2k+1}+(b^2)^{2k+1} \not\vdots p
\end{equation}
Lại có $$(a^2)^{2k+1}+(b^2)^{2k+1} \vdots a^2+b^2 \vdots p$$
Điều này mâu thuẫn với $(1)$. Vậy giả thiết phản chứng sai.
Đây cũng chính là mệnh đề mà bài viết muốn nói đến.
2. Một số ứng dụng
Ta xét đến bài toán tổng quát cho mệnh đề trên;
Bài 1. Tìm tất cả các số nguyên tố $p$ sao cho với mọi $a,b$ nguyên thì $ \left( a+b \right) \vdots p$ khi và chỉ khi $a$ và $b$ đồng thời chia hết cho $p$.
Giải
Xét các khả năng sau:
* Nếu $p=2$. Rõ ràng với mọi $a,b$ lẻ thì $\left( a+b \right) \vdots 2$, mà $a,b$ đều không chia hết cho $2$. Vậy $p=2$ không thỏa mãn.
* Nếu $p \ge 3$ thì $p$ lẻ, nên $p$ có dạng $4k+1$ hoặc $4k+3, \ k \in \mathbb{N}.$
Xét tiếp hai trường hợp sau:
+) Nếu $p$ có dạng $4k+1$. Theo định lý Willson, ta có: $ \begin{equation}
(p-1)!+1 \equiv 0 \pmod{p} \Rightarrow (4k)!+1 \equiv 0 \pmod{p}.\end{equation}$
Do $p=4k+1$ nên suy ra: $$4k \equiv -1 \pmod{p} \Rightarrow 4k-1 \equiv -2 \pmod{p} \Rightarrow \cdots \Rightarrow 2k+1 \equiv -2k \pmod{p}.$$
Ta suy ra $\begin{equation}\left( (4k)!+1 \right) \equiv \left[ (2k!)^2+1 \right] \pmod{p}.\end{equation}$
Từ $(1)$ và $(2)$ ta có:$\begin{equation}\left[ (2k!)^2+1^2 \right] \equiv 0 \pmod{p}.\end{equation}$
Rõ ràng khi $p=4k+1$, thì không thể có kết luận trên. Thật vậy, nếu kết luân ấy đúng thì từ $(3)$ suy ra $1 \vdots p$, vô lí vì $p=4k+1 \ge 3$.
Vậy với mọi số nguyên tố lớn hơn $3$ có dạng $4k+1$ không thỏa mãn yêu cầu đề bài.
+) Nếu $p$ có dạng $4k+3$. Giả sử bài toán không đúng với $p=4k+3$, điều đó có nghĩa là tồn tại cặp số nguyên $a,b$ sao cho $\left( a+b \right) \vdots p$ nhưng $a \not\vdots p, \ b \not\vdots p$.
Theo định lý Fermat nhỏ, ta có: $$ a^{p-1}-1 \equiv 0 \pmod{p}.$$
Tương tự ta có $$b^{p-1}-1 \equiv 0 \pmod{p}.$$
Do đó
$$\begin{align}
a^{p-1}+b^{p-1}-2 \equiv 0 \pmod{p} & \Rightarrow a^{4k+2}+b^{4k+2}-2 \equiv 0 \pmod{p} \\ & \Rightarrow (a^2)^{2k+1}+(b^2)^{2k+1}-2 \equiv 0 \pmod{p}.
\end{align}$$
Áp dụng hằng đẳng thức suy ra: $$(a^2)^{2k+1}+(b^2)^{2k+1}=(a^2+b^2)q, \ q \in \mathbb{N}^*$$
Do $(a^2+b^2) \vdots p$, nên từ $(5)$ đi đến: $$-2 \equiv 0 \pmod{p} \Rightarrow 2 \vdots p.$$
Điều này vô lí vì $p \ge 3$. Vậy giả thiết ban đầu là sai.
Bài toán được chứng minh.
Một số bài toán dưới đây đòi hỏi phải ứng dụng mệnh đề.
Bài 2. (Đấu trường VMF - Trận thứ 4 vòng bảng Alpha,Gama - Câu 1 đội Alpha)
Tìm nghiệm nguyên của phương trình:
$$\begin{equation}
x^{1994}+y^{1994}=4691^{4691} \left(x+y \right)\end{equation}$$
Giải
(perfectstrong) Nhận thấy $4691$ là số nguyên tố dạng $4k+3$. \\
$$(7) \Leftrightarrow \left( x^{997} \right) ^2+ \left( y^{997} \right)^2=4691^{4691} \left( x+y \right).$$
Áp dụng mệnh đề ta có:
$$\left\{\begin{matrix}
x^{997} \ \vdots \ 4691 & & \\
y^{997} \ \vdots \ 4691 & &
\end{matrix}\right. \Rightarrow \left\{\begin{matrix}
x=4691x_1 & & \\
y=4691y_1 & &
\end{matrix}\right.$$
với $x_1,y_1 \in \mathbb{N}^*$. Thay vào $(7)$ ta có:
$$\begin{equation}x_1^{4691}+y_1^{4691}=4691^{2698} \left( x_1+y_1 \right).\end{equation}$$
Áp dụng mệnh đề lần nữa ta có:
$$\left\{\begin{matrix}
x_1=4691x_2 & & \\
y_1=4691y_1 & &
\end{matrix}\right.$$
với $x_2,y_2 \in \mathbb{N}^*$. Thay vào $(8)$ ta có:
$$\begin{equation}
x_2^{4691}+y_1^{4691}=4691^{705} \left(x_2+y_2 \right)
\end{equation}$$
Tiếp tục áp dụng mệnh đề lần nữa, ta có:
$$\left\{\begin{matrix}
x_2=4691x_3 & & \\
y_2=4691y_3 & &
\end{matrix}\right.$$
với $x_3,y_3 \in \mathbb{N}^*$. Thay vào $(9)$ ta có
$$\begin{equation}4691^{1228} \left( x_3^{1994}+y_3^{1994} \right)=x_3+y_3\end{equation}$$
Rõ ràng phương trình $(10)$ không có nghiệm nguyên dương vì hiển nhiên $VT>VP$.
Vậy phương trình $(7)$ không có nghiệm nguyên dương.
Ta có bài toán tương tự sau:
Bài 3. Cho $k$ là số nguyên dương cho trước. Tìm nghiệm nguyên dương của phương trình $$x^2+y^2=2011^{2003^k+1} \left( 10-z \right).$$
Tiếp tục đến với bài toán sau:
Bài 4.
Cho $m,n$ là các số nguyên dương thỏa $$m^2+9 \ \vdots 2^n-1.$$Chứng minh rằng $n$ là lũy thừa của 2.
Giải
Đặt $n=2^k.l$ với $k,l \in \mathbb{N}$ và $l$ lẻ.
Nếu $l \geq 3$ thì
\[\begin{array}{l}
{m^2} + 9 \ \vdots 2^n-1 \\
{2^n} - 1 = {2^{{2^k}.l}} - 1 = {\left( {{2^l}} \right)^{{2^k}}} - {1^{{2^k}}} \ \vdots {2^l} - 1 \Rightarrow {m^2} + 9 \ \vdots 2^l-1 \\
\end{array}\]
Mà $l \ge 3 \Rightarrow {2^l} \vdots 4 \Rightarrow {2^l} - 1 \equiv 3\left( {\bmod 4} \right)$ nên $2^l-1$ có 1 ước nguyên tố $p$ dạng $4k+3$.
\[\begin{array}{l}
l \ge 3 \Rightarrow {2^l} \vdots 4 \Rightarrow {2^l} - 1 \equiv 3\left( {\bmod 4} \right) \\
\left. \begin{array}{l}
\Rightarrow {m^2} + 9 \ \vdots p \Rightarrow 3 \vdots p \Rightarrow p = 3 \\
{2^l} - 1 = {\left( {3 - 1} \right)^l} - 1 \equiv - 2\left( {\bmod 3} \right) \\
\end{array} \right\} \text{vô lí} \\
\end{array}\]
Do đó $l=1 \Rightarrow n=2^k.$
Bài 5 (Bài toán Lebesgue)
Chứng minh rằng phương trình $$x^2-y^3=7$$ không có nghiệm nguyên.
Giải
Gỉa sử trái lại, tồn tại số nguyên $x,y$ thỏa mãn
$$\begin{equation}x^2-y^3=7\end{equation}$$
Chỉ có hai khả năng sau:
*) Nếu $y$ chẵn, tức $y=2k$. Thay vào $(11)$ ta có
$$\begin{equation}x^2=8k^3+7\end{equation}$$
Nhận thấy một số chính phương chia $8$ dư $0,1,4$. Điều này mâu thuẫn với $(11)$, vậy $y$ không thể chẵn.
*) Nếu $y$ lẻ. Viết lại $(11)$ dưới dạng
$$x^2+1=y^3+8 \Leftrightarrow x^2+1^2=(y+2)(y^2-2y+4).$$
Do $y$ lẻ, nên lại có các khả năng sau:
+) Nếu $y$ chia $4$ dư $1$. Khi đó $$y+2=4k+3$$
+) Nếu $y$ chia $4$ dư $3$. Khi đó $$y^2-2y+4=(4m+3)^2-2(4m+3)+4=4t+3.$$
Vậy trong mọi trường hợp $x^2+1$ đều có ước dạng $4k+3$, vì thế nó phải có ước nguyên tố dạng $4k+3$. Rõ ràng điều này mâu thuẫn với mệnh đề đã nêu.
Ta suy ra giả thiết phản chứng sai.
Bài 6. Chứng minh rằng phương trình
$$\begin{equation} 4xy-x-y=z^2\end{equation}$$
vô nghiệm nguyên.
Giải
Viết phương trình đã cho dưới dạng
$$\begin{equation}
\begin{align} 16xy-4x-4y=4z^2 & \Leftrightarrow 16xy-4x-4y+1=4z^2+1 \\ & \Leftrightarrow (4x-1)(4y-1)=(2z)^2+1.
\end{align}\end{equation}$$
Giả sử $(14)$ có nghiệm nguyên $(x,y)$ thì từ $(14)$ ta có:
$$(4x-1)(4y-1)=(2z)^2+1 \Leftrightarrow \left[ 4(x-1)+3 \right] \left[ 4(y-1)+3 \right]=(2z)^2+1^2.$$
Lập luận như bài 5 ta suy ra $(2z)^2+1$ có ước nguyên tố dạng $4k+3$. Điều này mâu thuẫn với mệnh đề. Vậy phương trình $4xy-x-y=z^2$ không có nghiệm nguyên.
3. Bài tập
Một số bài cho mọi người luyện tập thêm về việc sử dụng mệnh đề này trong giải toán số học.
Bài 7. Cho $n$ là số nguyên dương thỏa mãn:
(i) $3|2^n-1$
(ii)$\exists m \in \mathbb{N}:4m^2+1 \ \vdots \dfrac{2^n-1}{3}$
Chứng minh rằng $n$ là lũy thừa của 2.
Bài 8. Giải phương trình nghiệm nguyên sau:
$$x^2+5=y^3$$
Bài viết đã được chỉnh sửa nội dung bởi Jinbe: 14-05-2013 - 12:10