Đến nội dung

Hình ảnh

Ứng dụng một mệnh đề vào giải các bài toán số học


  • Please log in to reply
Chủ đề này có 4 trả lời

#1
Ban Biên Tập

Ban Biên Tập

    Ban Biên Tập

  • Thành viên
  • 70 Bài viết

Ứ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


#2
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết
Xin nêu thêm rằng ở bài 6 đã có một chứng minh của Euler.
Bài 6. Chừng minh rằng phương trình $$4xt-x-y=z^2$$ không có nghiệm nguyên.

Giải. Giả sử phương trình có nghiệm $(x,y,z)=(m,n,c)$ và giả sử $c$ là giá trị nhỏ nhất của $z$.
$$\begin{array}{l} \Rightarrow 4mn-m-n=c^2 \\ \Rightarrow (4m-1)(4n-1)-1=c^2. \text{ } (1) \end{array}$$
Cộng vào hai vế $4(4n-1)^2-8a(4n-1)$ vào hai vế của $(1)$ ta có
$$[4m-1-8c+4(4n-1)](4n-1)-1=4(c-4n+1)^2. \text{ } (2)$$
Như vậy phương trình có nghiệm $z=|c-4n+1|$.

Vì $c$ là giá trị nhỏ nhất của $z$ nên
$$\begin{array}{l} \Rightarrow |c-4n+1|>c \\ \Rightarrow (c-4n+1)^2>c^2 \\ \Rightarrow [4m-1-8a+4(4n-1)](4n-1)>(4n-1)(4m-1) \\ \Rightarrow 4n-1>2c. \end{array}$$
Chứng minh tương tự ta cũng có $4m-1>2c. $

Đặt $4m-2=p,4n-1=2a+q$ với $p,q$ nguyên.
Như vậy $$(4m-1)(4n-1)=4c^2+2c(p+q)+pq \text{ } (3)$$
Do đó từ $(1)$ và $(3)$ suy ra $2c=(p+q)+pq.$ Điều này vô lí. Vậy phương trình không có nghiệm nguyên. $\blacksquare$

Nhận xét. Rõ ràng cách chứng minh bằng mệnh đề trên nhanh và tiện lợi hơn cách chứng minh của Euler

Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.

 

Grothendieck, Récoltes et Semailles (“Crops and Seeds”). 


#3
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết
Tìm trong một số tạp chí Toán học Tuổi trẻ cũ cũng có nói về vấn đề này, xin đưa lên cho mọi người xem.

Thực chất bài toán 5 và bài toán 6 cũng được áp dụng mệnh đề sau:

Với mọi số nguyên $a$, số $a^2+1$ không có ước nguyên tố dạng $4k+3$.

Chứng minh. Giả sử tồn tại số nguyên $a$ sao cho $a^2+1$ có ước nguyên tố $p$ dạng $4k+3$.
Từ $a^2+1 \vdots p \Rightarrow a^{4k+2}+1 \vdots p \text{ } (1)$.
Mặt khác, theo định lý Fermat nhỏ thì
$$a^{4k+2} \equiv 1 \pmod{p} \text{ }$$
Từ $(1)$ và $(2)$ suy ra $2 \vdots p \Rightarrow p=2$, mâu thuẫn với việc $p$ có dạng $4k+3$.
Vậy giả thiết phản chứng sai. $\blacksquare$

Bây giờ xin đưa thêm tiếp một số bài toán ứng dụng mệnh đề mà bài viết đang nói đến.

Bài 9. Tìm các số nguyên dương $x,y,z,t$ thỏa mãn hệ phương trình
$$\left\{\begin{matrix} x^2+13y^2=z^2 & & \\ 13x^2+y^2=t^2 & & \end{matrix}\right.$$

Giải Đặt $(x,y)=d \Rightarrow z \vdots d$.
Đặt $\begin{array}{l} x=d_1 \\ y=dy_1 \\ z=dz_1 \end{array}$.
($x_1,y_1,z_1$ nguyên dương, $(x_1,y_1)=1$)

Từ hệ trên dễ dàng suy ra $$14(x^2+y^2)=z^2+t^2$$
$$\Rightarrow 14(x_1^2+y_1^2)=z_1^2+t_1^2 \Rightarrow z_1^2+t_1^2 \vdots 7.$$
Áp dụng mệnh đề ta có $x_1 \vdots 7, y_1 \vdots 7$
Mâu thuẫn với giả thiết $(x_1,y_1)=1$.
Vậy phương trình không có nghiệm nguyên dương.

Bài 10. Giả sử $x$ và $y$ là các số nguyên khác $0$ sao cho $\frac{x^2+y^2}{x+y}$ là số nguyên và là ước của $1978$. Chứng minh $x=y$

(Chọn đội tuyển Quốc gia CHLB Đức 1979)

Bài 11. Tìm các nghiệm nguyên dương của phương trình
a) $x^2+y^2=585$
b) $x^2+y^2=2010$
c) $19x^2+18y^2=729$
d) $x^2+y^2=3z^2$

Bài viết đã được chỉnh sửa nội dung bởi Phạm Quang Toàn: 21-01-2012 - 10:49

Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.

 

Grothendieck, Récoltes et Semailles (“Crops and Seeds”). 


#4
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết
Từ bài toán ở phần 1 (mở đầu), ngoài mệnh đề mà ta rút ra thì xin bổ sung thêm 2 mệnh đề nữa suy ra từ kết quả

1) Áp dụng bài toán mở đầu với $t=2$ ta có:
Nếu $ \left(a^4+b^4 \right) \vdots p$ với $p$ là số nguyên tố dạng $4k+1$ thì $a \vdots p, \ b \vdots p$.

2) Giả sử $a,b$ là hai số tự nhiên khác $0$ và nguyên tố cùng nhau. Khi đó các ước nguyên tố lẻ của $a^2+b^2$ chỉ có thể có dạng $4m+1$ (không có dạng $4m+3$ với mọi $m$ nguyên).
Thật vậy giả sử tồn tại số nguyên tố $p=4m+3$ mà $ \left(a^2+b^2 \right) \vdots p$. Theo mệnh đề thì ta có $a \vdots p, \ b \vdots p$. Như vậy $(a,b)=p>1$, mâu thuẫn.
Ta có đpcm. $\blacksquare$

Dễ nhận thấy bài 5 áp dụng tính chất 2 này. Xin đưa thêm một số bài toán áp dụng nữa.

Bài 12. Tìm tất cả các cặp số nguyên dương $(x,y)$ sao cho $\frac{x^2+y^2}{x-y}$ là số nguyên dương và là ước số của $1995.$

Bài 13. Tìm số nhỏ nhất trong tập hợp các số chính phương dạng $15a+16b$ và $16a-15b$ với $a,b$ là các số nguyên dương nào đó.

Bài viết đã được chỉnh sửa nội dung bởi Phạm Quang Toàn: 21-01-2012 - 10:50

Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.

 

Grothendieck, Récoltes et Semailles (“Crops and Seeds”). 


#5
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết
Đây là file đầy đủ cho chuyên đề này (có bổ sung thêm những gì mình viết ở trên). Mong mọi người góp ý:
Tải file tại: http://www.mediafire...gcfo940bw2fw6g5 .

Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.

 

Grothendieck, Récoltes et Semailles (“Crops and Seeds”). 





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh