Tag Archives: Sohoc

Phương trình nghiệm nguyên – Phương pháp sử dụng tính chất chia hết

1. Sử dụng tính chẵn, lẻ

Ví dụ 1: Tìm nghiệm nguyên của phương trình: $x^{2} - 2 y^{2} = 5$ $(1)$ .

Giải

Vì $x$ , $y$ nguyên nên từ phương trình $(1)$ suy ra $x$ là số lẻ.

Thay $x = 2 k + 1 (k \in Z)$ vào $(1)$ ta được

$4 k^{2} + 4 k + 1 - 2 y^{2} = 5 \Leftrightarrow 2 (k^{2} + k - 1) = y^{2} \Rightarrow y$ là số chẵn.

Đặt $y = 2 t (t \in Z)$ ta có $2 (k^{2} + k - 1) = 4 t^{2} \Leftrightarrow k (k + 1) = 2 t^{2} + 1$ $(*)$

Vì $k (k + 1)$ là số chẵn mà $2 t^{2} + 1$ là số lẻ nên phương trình $(*)$ vô nghiệm.

Vậy phương trình $(1)$ vô nghiệm

Ví dụ 2: Tìm nghiệm nguyên của phương trình $(2 x + 5 y + 1) (2^{| x |} + x^{2} + x + y) = 105$ $(2)$ .

(Trích đề thi HSG lớp 9 TP. Hà Tĩnh năm 2006 – 2007)

Giải

Ở bài này ta thấy vế trái là tích của hai số nguyên mà vế phải là số lẻ nên nó phải là tích của hai số nguyên lẻ nên ta có thể sử dụng tính chất chẵn lẻ như sau:

Vì $105$ là số lẻ nên $2 x + 5 y + 1$ , $2^{| x |} + x^{2} + x + y$ là các số lẻ. Suy ra $y$ là số chẵn , mà $x^{2} + x = x (x + 1)$ là số chẵn nên $2^{| x |}$ là số lẻ suy ra $x = 0$

Thay $x = 0$ vào $(2)$ ta được $(5 y + 1) (y + 1) = 105 \Leftrightarrow 5 y^{2} + 6 y - 104 = 0 \Leftrightarrow y = 4$ (vì $y$ là số chẵn). Do đó $y = 4$ . Vậy phương trình có nghiệm nguyên là $(0; 4)$ .

Ví dụ 3: Giải phương trình nghiệm nguyên $| 19 x + 15 y | + 1975 = | 19 y + 5 x | + 2016^{x}$ $(3)$ .

Giải

Biến đổi phương trình $(3)$ ta được:

$1975 - 2016^{x} = (| 19 y + 5 x | + 19 y + 5 x) - (| 19 x + 5 y | + 19 x + 5 y) + 14 (x - y)$ .

Vì $| a | + a$ là số chẵn với mọi giá trị nguyên của $a$ nên vế phải là số chẵn do đó $1975 - 2016^{x}$ phải là số chẵn suy ra $2016^{x}$ là số lẻ suy ra $x = 0$ .

Thay $x = 0$ vào phương trình $(3)$ ta được $| 5 y | + 1975 = | 19 y | + 1 \Leftrightarrow 14 | y | = 1974 \Leftrightarrow y = 141$ hoặc $y = - 141$ .

Vậy phương trình có hai nghiệm nguyên $(x; y)$ là $(0; 141)$ và $(0; - 141)$ .

Ví dụ 4: Tìm nghiệm nguyên của phương trình $x + x^{2} + x^{3} = 4 y^{2} + 4$ $(4)$ .

Giải

Ta có: $(4) \Leftrightarrow 1 + x + x^{2} + x^{3} = 4 y^{2} + 4 y + 1 \Leftrightarrow (x + 1) (x^{2} + 1) = (2 y + 1)^{2}$ $(*)$

Dễ thấy $(2 y + 1)^{2}$ lẻ suy ra $x + 1$ và $x^{2} + 1$ là hai số lẻ. Giả sử $(x + 1, x^{2} + 1) = d$ suy ra $d$ lẻ.

Mặt khác $x + 1 ⋮ d \Rightarrow 1 - x^{2} ⋮ d$ , kết hợp với $x^{2} + 1 ⋮ d$ ta có $1 - x^{2} + 1 + x^{2} ⋮ d \Rightarrow 2 ⋮ d \Rightarrow d = 1$ (vì $d$ lẻ)

Vì $(x + 1) (x^{2} + 1)$ là số chính phương (theo $(*)$ ) và $(x + 1, x^{2} + 1) = 1$ nên $x + 1$ và $x^{2} + 1$ đều là số chính phương.

Dễ thấy $x^{2}$ và $x^{2} + 1$ là 2 số tự nhiên liên tiếp mà đều là số chính phương nên $x = 0$ .

Khi đó theo $(4)$ thì $y = 0$ hoặc $y = - 1$ .

Vậy nghiệm của phương trình là $(0; 0)$ hoặc $(0; - 1)$

Ví dụ 5: Chứng tỏ phương trình: $x^{4} + y^{4} + z^{4} + t^{4} + k^{4} = 2015$ không có nghiệm nguyên.

Giải

Nếu $x$ là số chẵn thì $x^{4} ⋮ 16$ .

Nếu $x$ là số lẻ thì $x^{2} : 8$ dư $1$ nên $x^{4} = (8 k + 1)^{2} : 16$ dư $1$ .

Như vậy mỗi số $x^{4}$ , $y^{4}$ , $z^{4}$ , $t^{4}$ , $k^{4}$ chia cho $16$ dư $1$ hoặc $0$ nên $x^{4} + y^{4} + z^{4} + t^{4} + k^{4}$ chia cho $16$ có số dư không lớn hơn $5$ còn vế phải $2015$ chia cho $16$ dư $15$ .

Vậy phương trình không có nghiệm nguyên.

2. Sử dụng tính chất chia hết

Ví dụ 6: Chứng minh rằng không tồn tại các số nguyên $x$ ; $y$ ; $z$ thỏa mãn

$x^{3} + y^{3} + z^{3} = x + y + z + 2017 (6)$

Giải

$(6) \Leftrightarrow (x^{3} - x) + (y^{3} - y) + (z^{3} - z) = 2017$ . Vì $x^{3} - x = (x - 1) x (x + 1)$ là tích của $3$ số nguyên liên tiếp nên chia hết cho $6$ , tương tự $y^{3} - y$ , $z^{3} - z$ cũng chia hết cho $6$ nên vế trái chia hết cho $6$ mà $2017$ không chia hết cho $6$ nên phương trình $(6)$ vô nghiệm.

Vậy không tồn tại các số nguyên $x$ ; $y$ ; $z$ thỏa mãn $x^{3} + y^{3} + z^{3} = x + y + z + 2017$

Ví dụ 7: Tìm nghiệm nguyên của phương trình: $x^{2} y - 5 x^{2} - x y - x + y - 1 = 0$ $(7)$

(Trích đề thi HSG lớp $9$ huyện Can Lộc, Hà Tĩnh)

Giải

Đây là phương trình $2$ ẩn mà bậc đối với $y$ là bậc nhất nên ta dễ dàng biểu thị $y$ theo $x$ và ta có cách giải như sau:

$(7) \Leftrightarrow y = \frac{5 x^{2} + x + 1}{x^{2} - x + 1} (do x^{2} - x + 1 > 0) \Rightarrow y = 5 + \frac{6 x - 4}{x^{2} - x + 1}$

Ta có $y \in Z \Leftrightarrow (6 x - 4) ⋮ (x^{2} - x + 1)$

$\Leftrightarrow 2 (3 x - 2) ⋮ (x^{2} - x + 1)$

$\Leftrightarrow [\begin{array}{l} 2 ⋮ (x^{2} - x + 1) \\ 3 x - 2 ⋮ (x^{2} - x + 1) \end{array}$

(vì $x^{2} - x + 1 = x (x - 1) + 1$ là số lẻ).

TH1: $2 : (x^{2} - x + 1)$
$\Leftrightarrow x^{2} - x + 1 = \pm 1$ (vì $. x^{2} - x + 1$ lẻ)

$\Leftrightarrow x = 0; x = 1$ (thỏa mãn $x$ nguyên).

$+$ Với $x = 0 \Rightarrow y = 1$
$+$ Với $x = 1 \Rightarrow y = 7$

TH2: $(3 x - 2) : (x^{2} - x + 1) (*)$
$\Rightarrow x (3 x - 2) ⋮ (x^{2} - x + 1)$
$\Rightarrow (3 x^{2} - 2 x) ⋮ (x^{2} - x + 1)$
$\Rightarrow (3 x^{2} - 3 x + 3 + x - 3) ⋮ (x^{2} - x + 1)$
$\Rightarrow (x - 3) ⋮ (x^{2} - x + 1)$
$\Rightarrow (3 x - 9) ⋮ (x^{2} - x + 1) (* *)$

Từ $(*)$ và $(* *)$ ta được $7 ⋮ (x^{2} - x + 1) \Rightarrow x^{2} - x + 1$ bằng một trong các giá trị $- 7$ ; $7$ ; $1$ ; $- 1$ .

Từ đây ta được các nghiệm: $(3; 7)$ , $(0; 1)$ , $(1; 7)$ .

Thử lại ta thấy phương trình $(7)$ có các nghiệm nguyên $(x; y)$ là $(3; 7)$ , $(0; 1)$ , $(1; 7)$ .

Ví dụ 8: Tồn tại hay không một số nguyên $n$ thỏa mãn $n^{3} + 2015 n = 2014^{2016} + 1$ ?

Giải

Giả sử tồn tại số nguyên $n$ thỏa mãn phương trình $n^{3} + 2015 n = 2014^{2016} + 1$ , suy ra:

$n^{3} - n + 2016 n = 2014^{2016} + 1$

$\Leftrightarrow (n - 1) n (n + 1) + 2016 n = 2014^{2016} + 1$

Do $(n - 1) n (n + 1)$ là tích của ba số nguyên liên tiếp nên chia hết cho $3$ và $2016 ⋮ 3$ nên $n^{3} - n + 2016 n ⋮ 3$ hay $n^{3} + 2015 ⋮ 3$ .

Mặt khác $2014$ chia $3$ dư $1$ nên $2014^{2016}$ chia $3$ dư $1 \Rightarrow 2014^{2016}$ chia $3$ dư $1 \Rightarrow 2014^{2016} + 1$ chia $3$ dư $2$

Từ đó ta thấy điều mâu thuẫn. Vậy không tồn tại số nguyên $n$ thỏa mãn phương trình.

Ví dụ 9: Tồn tại hay không hai số nguyên dương $a$ và $b$ thỏa mãn $a^{3} + b^{3} = 2013$ ?

Giải

Giả sử tồn tại hai số nguyên dương $a$ và $b$ thỏa mãn $a^{3} + b^{3} = 2013$ .

Ta có: $(a + b)^{3} = a^{3} + b^{3} + 3 a b (a + b)$
Vì $a^{3} + b^{3} = 2013 ⋮ 3 \Rightarrow a^{3} + b^{3} + 3 a b (a + b) ⋮ 3$
$\Leftrightarrow (a + b)^{3} ⋮ 3 \Rightarrow a + b ⋮ 3 \Rightarrow (a + b)^{3} ⋮ 9$
$\Rightarrow 2013 = a^{3} + b^{3} = (a + b)^{3} - 3 a b (a + b) ⋮ 9$ (vô lý).
Vậy không tồn tại hai số nguyên dương $a$ và $b$ thỏa mãn $a^{3} + b^{3} = 2013$ ,

Ví dụ 10: Giải phương trình nghiệm nguyên $x^{2} (x - y) = 5 (y - 1)$ $(10)$

Giải

Ta có $(10) \Leftrightarrow x^{2} (x - y) = 5 (y - x) + 5 (x - 1) \Leftrightarrow (x^{2} + 5) (x - y) = 5 (x - 1) .$
Suy ra $5 (x - 1) ⋮ (x^{2} + 5) \Rightarrow 5 (x^{2} + 5) - 5 x (x - 1) - 5 (x - 1) ⋮ (x^{2} + 5)$ hay $30 ⋮ (x^{2} + 5)$
$\Rightarrow (x^{2} + 5) \in {5; 6; 10; 15; 30}$ và $x$ là số nguyên
$\Rightarrow x \in {0; \pm 1; \pm 5}$ .

Thử lại ta được nghiệm nguyên của phương trình là $(0; 1); (1; 1); (- 5; - 4)$ .

Ví dụ 11: Chứng minh phương trình: $x^{2} - 2^{y} = 2015$ $(11)$ không có nghiệm nguyên.

Giải

$(11) \Leftrightarrow x^{2} = 2015 + 2^{y}$ .
Ta sẽ chứng minh $A = 2015 + 2^{y}$ không phải là số chinh phương với mọi số nguyên $y$ .

Thật vậy thay $y$ bằng $0; 1; 2$ thì $A$ lần lượt nhận các giá trị là $2016; 2017; 2019$ đều không phải là số chính phương. Với $y \geq 3$ thi $2^{y}$ chia hết cho $8$ , còn $2015$ chia $8$ dư $7$ nên $A$ chia $8$ dư $7$ mà số chính phương lẻ chia $8$ chỉ có thể dư $1$ do đó $A$ không phải là số chính phương.

Vậy phương trình $(11)$ không có nghiệm nguyên.

Ví dụ 12: Tìm các số nguyên dương $a$ , $b$ sao cho

$\frac{4}{a} + \sqrt[3]{4 - b} = \sqrt[3]{4 + 4 \sqrt{b + b}} + \sqrt[3]{4 - 4 \sqrt{b} + b}$ $(12)$

Giải

Đặt $\sqrt[3]{2 + \sqrt{b}} = x; \sqrt[3]{2 - \sqrt{b}} = y$ .

Vì $b > 0$ nên $x > 0$ . Ta có $x y = \sqrt[3]{2 + \sqrt{b}} \cdot \sqrt[3]{2 - \sqrt{b}} = \sqrt[3]{4 - b}$ ; $x^{3} + y^{3} = 4$

Do đó phương trình $(12)$ trở thành:
$\frac{x^{3} + y^{3}}{a} + x y = x^{2} + y^{2} \Leftrightarrow \frac{x^{2} + y^{3}}{a} = x^{2} + y^{2} - x y$
$\Leftrightarrow \frac{(x + y) (x^{2} + y^{2} - x y)}{a} = x^{2} + y^{2} - x y$
mà $x^{2} + y^{2} - x y = \frac{3}{4} x^{2} + {(\frac{x}{2} - y)}^{2} > 0$

suy ra $x + y = a \Rightarrow \sqrt[3]{2 + \sqrt{b}} + \sqrt[3]{2 - \sqrt{b}} = a$ $(*)$
$\Rightarrow 4 + 3 \sqrt[3]{4 - b} \cdot a = a^{3}$ $(* *)$
$\Leftrightarrow 4 - b = {(\frac{a^{3} - 4}{3 a})}^{3}$
Vì $b$ là số nguyên nên $a^{3} - 4 ⋮ 3 a \Rightarrow a^{3} - 4 ⋮ a$ $\Rightarrow 4 ⋮ a \Rightarrow a \in {1; 2; 4}$
Với $a = 1 \Rightarrow b = 5$ .

Với $a = 2$ hoặc $a = 4$ thì $b$ không phải là số nguyên dưong.

Thử lại: Với $a = 1$ ; $b = 5$ ta có $(* *)$ đúng tức là
$x^{3} + y^{3} + 3 x y a = a^{3} \Leftrightarrow a^{3} - x^{3} - y^{3} - 3 x y a = 0$
$\Leftrightarrow (a - x - y) [(a + x)^{2} + (a + y)^{2} + (x - y)^{2}] = 0 .$
Do $x > 0; a > 0$ nên $x + a > 0 \Rightarrow (a + x)^{2} + (a + y)^{2} + (x - y)^{2} > 0 \Rightarrow a - x - y = 0$ hay $a = x + y$ ,
tức là $(*)$ đúng.

Vậy $(a, b) = (1; 5)$ là cặp số nguyên dương duy nhất thỏa mãn phương trình $(12)$ .

Ví dụ 13: Tìm số tự nhiên $n$ thỏa mãn $361 (n^{3} + 5 n + 1) = 85 (n^{4} + 6 n^{2} + n + 5)$ $(13)$

Giải

Ta có

(13) \Leftrightarrow \frac{n^{3} + 5 n + 1}{n^{4} + 6 n^{2} + n + 5} = \frac{85}{361}

.
Ta sẽ chứng minh

\frac{n^{3} + 5 n + 1}{n^{4} + 6 n^{2} + n + 5}

la phân số tối giản với mọi giá trị

n \in N

.
Thật vậy, đặt

d = (n^{3} + 5 n + 1; n^{4} + 6 n^{2} + n + 5)

.
Suy ra

n^{4} + 6 n^{2} + n + 5 - n (n^{3} + 5 n + 1) ⋮ d

hay

n^{2} + 5 ⋮ d

Từ đó $(n^{3} + 5 n + 1) - n (n^{2} + 5)$ \, \vdots \, d hay $1 ⋮ d \Rightarrow d = 1$ .

Vậy phân số $\frac{n^{3} + 5 n + 1}{n^{4} + 6 n^{2} + n + 5}$ là phân số tối giản.

Mặt khác phân số $\frac{85}{361}$ cũng là phân số tối giản mà dạng tối giản của một phân số là duy nhất nên ta có

${\begin{cases} n^{3} + 5 n + 1 = 85 \\ n^{4} + 6 n^{2} + n + 5 = 361 \end{cases}$
$\Rightarrow (n^{4} + 6 n^{2} + n + 5) - n (n^{3} + 5 n + 1) = 361 - 85 n$
$\Leftrightarrow n^{2} + 85 n - 356 = 0 \Leftrightarrow (n - 4) (n + 89) = 0$
Vi $n \in N$ nên $n = 4$ .

Vậy số tự nhiên cần tìm là $n = 4$ .

Ví dụ 14: Tìm tất cả các số nguyên dương $m$ , $n$ thỏa mãn $3^{m} = n^{2} + 2 n - 8$ $(14)$

Giải

Ta có

(14) \Leftrightarrow 3^{m} = (n + 4) (n - 2)

Đặt $n + 4 = 3^{x}; n - 2 = 3^{y}$ với $x, y$ là số tự nhiên và $x + y = m$ , khi đó $3^{x} - 3^{y} = 6$ hay $3^{y} (3^{x - y} - 1) = 6$ .

Vì $3^{y}$ chỉ có ước là lũy thừa của $3$ ; $3^{x - y} - 1$ không chia hết cho $3$ và $6 = 3.2$ nên $3^{y} = 3$ và $3^{x - y} - 1 = 2$ hay $y = 1$ và $x = 2$ .

Từ đó $m = x + y = 3$ và $n = 3^{y} + 2 = 5$ .

Ví dụ 15: Tìm các số nguyên dương $x$ , $y$ thỏa $x^{2} - y! = 2015$

Giải

Nếu

y > 5

thì

y! ⋮ 9 \Rightarrow y! + 2015

chia

9

dư

8

mà

x^{2}

chia

9

chi có thể nhận các số dư là

0; 1; 4; 7

nên trong trường hợp này không tồn tại nghiệm.

Xét $y$ lần lượt bằng $0; 1; 2; 3; 4; 5$ đều không có giá trị $x$ thỏa mãn.
Vậy phương trình $(15)$ vô nghiệm.

Ví dụ 16: Tìm tất cả các số tự nhiên $m; n$ để $P = 3^{3 m^{2} + 6 n - 61} + 4$ là số nguyên tố.
(Trích đề thi HSG TP. Hà Tĩnh, năm hoc $2015 - 2016$ )

Giải

Nhận xét: Để tìm các số tự nhiên

m, n

sao cho

P

là số nguyên tố thì ta có thể chứng minh

P

chia hết cho
một số nguyên tố

n

nào đó và khi đó

P = n

Đặt $3 m^{2} + 6 n - 61 = 3 k + 2 (k \in N)$ .

Ta có $P = 3^{3 k - 2} + 4 = {9.27}^{k} + 4$

Vì $27 \equiv 1 (mod 13)$ nên $27^{k} \equiv 1 (mod 13) \Rightarrow {9.27}^{k} \equiv 9 (mod 13) \Rightarrow {9.27}^{k} + 4 \equiv 13 (mod 13)$
hay $P ⋮ 13$ , mà $P$ là số nguyên tố nên $P = 13$ , điều này xảy ra khi và chỉ khi $k = 0 .$

Suy ra $3 m^{2} + 6 n - 61 = 2 \Leftrightarrow m^{2} + 2 n = 21$
Vì $m; n$ là các số tự nhiên nên chỉ có 2 cặp số $(m; n)$ thỏa mãn là $(1; 10)$ và $(3; 6)$ .

Ví dụ 17: Tìm nghiệm nguyên của phương trình $x^{11} + y^{11} = 11 z$ $(17)$

Giải

(17)

có nghiệm nguyên khi

x^{11} + y^{11} ⋮ 11

Vì $11$ là số nguyên tố, theo định lý nhỏ Fermat ta có: $x^{11} - x ⋮ 11$ và $y^{11} - y ⋮ 11 .$

Ta viết $(17)$ dưới dạng: $(x^{11} - x) + (y^{11} - y) + (x + y) = 11 z$ suy ra $x + y ⋮ 11$ .

Đặt $x + y = 11 k; x = t$ $(k, t \in Z) .$ Ta có công thức nghiệm: $x = t$ , $y = 11 k - t$ và $[t^{11} + (11 k - t)^{11}] ⋮ 11$ .

Bài tập rèn luyện.

Bài 1. Giải các phương trình sau trong tập nguyên dương:
a) $2 x^{2} + 3 x y - 2 y^{2} = 7$ .
b) $x^{3} - x y = 6 x - 5 y - 8$
c) $x^{3} - y^{3} = 91$ .

Bài 2. Tìm các số nguyên $x$ , $y$ sao cho:

a) $3^{x} - y^{3} = 1$ ;
b) $1 + x + x^{2} + x^{3} = 2^{y}$ ;
c) $1 + x + x^{2} + x^{3} = 2003^{y}$ .

Bài 3. Tìm các số nguyên tố $x$ , $y$ , $z$ thỏa mãn: $x^{y} + 1 = z$

Bài 4. Tìm các số nguyên dương $x, y, z$ thỏa $y$ nguyên tố và $y, 3$ không là ước của $z$ thỏa $x^{3} - y^{3} = z^{2}$ .

Bài 5. Chứng tỏ rằng các phương trình sau không có nghiệm nguyên

a) $2 x^{2} + y^{2} = 1999$ .

b) $7 x^{2} - 5 y^{2} = 3$ .

c) $x^{4} + y^{4} + (x + y)^{4} = 4004$ .

Bài 6. Tìm nghiệm nguyên của mỗi phương trình sau:

a) $17 x^{2} + 26 y^{2} = 846$ .

b) $3 x^{2} - 3 x y = 7 x - y - 21$ .

c) $x^{3} + 3367 = 2^{y}$ .

d) $2^{x} - 3^{y} = 7$ .

e) $x! + y! = 10 z + 9$ .

f) $| x - y | + | y - z | + | z - x | = 2017$ .

g) $x^{3} + y^{3} + z^{4} = 2003$ .

Bài 7. Tồn tại hay không $4$ số nguyên liên tiếp $a$ , $b$ , $c$ , $d$ thỏa mãn $a^{3} + b^{2} + c + d = 491$ .

Bài 8. Cho đa thức $f (x)$ có các hệ số nguyên. Biết rằng $f (1) \cdot f (2) = 45$ . Chứng tỏ đa thức $f (x)$ không có nghiệm nguyên.

Một số bài toán số học hay ôn thi vào 10 Chuyên Toán

Trong khi thì HSG TPHCM vừa qua có một điều đáng tiếc nhất là câu số học không có trong đề thi, làm nhiều thí sinh khá hụt hẫng nhưng cũng làm nhiều thí sinh vui mừng, vì số học luôn là câu hỏi hóc búa của mỗi kì thi. Có lẽ BTC cuộc thi muốn dành sự quan tâm cho các câu hỏi thực tế nên phần số học bị bỏ qua.

Khác với kì thi HSG, kì thi tuyển sinh vào 10 thì đề thi luôn có đủ cả các phần: đại số, số học, hình học và tổ hợp. Số học cũng như tổ hợp, luôn là phần khiến nhiều thí sinh gặp khó khăn, trong bài viết nhỏ này, tôi xin giới thiệu lại một số bài toán số học đã được cho trong các kì thi tuyển sinh của trường Phổ thông Năng khiếu, nơi tôi làm việc hơn 10 năm qua. Các bạn thí sinh chuẩn bị thi vào trường nên xem kĩ lời giải và cố gắng học thật tốt phần này, điều đó sẽ giúp rất nhiều cơ hội trúng tuyển vào lớp chuyên toán.

Số học THCS thì nội dung quay xung quanh các phép chia hết, phương trình nghiệm nguyên, số nguyên tố, số chính phương,…Việc đầu tiên là nắm chắc các tính chất của phép chia hết, tính chất cơ bản nhất của số nguyên tố hay số chính phương. Bài toán chia hết cũng xuất hiện nhiều lần trong đề thi, sau đây là một bài khá đơn giản nhưng hay:

Bài 1. (PTNK 2011 – Chuyên Toán) Cho các số nguyên $a, b, c$ sao cho $2 a + b, 2 b + c, 2 c + a$ đều là các số chính phương ().
a) Biết rằng có ít nhất một trong 3 số chính phương trên chia hết cho 3. Chứng minh rằng $(a - b) (b - c) (c - a)$ chia hết cho 27.
b) Tồn tại hay không các số $a, b, c$ thỏa điều kiện () mà $(a - b) (b - c) (c - a)$ không chia hết cho 27?

Nhận xét. Đây là một bài toán chia hết, liên quan đến các số chính phương, để ý thấy chủ yếu là chia hết cho 3. Ta phải nghĩ đến một số chính phương chia 3 xảy ra những trường hợp nào, từ đó thiết lập các tính chất đã biết:

Một số chính phương khi chia cho 3 dư 0 hoặc 1.
$a^{2} + b^{2}$ chia hết cho 3 khi và chỉ khi $a, b$ đồng thời chia hết cho 3.
Việc chứng minh tích chia hết cho 27, thì nghĩ đến việc ta cần chứng minh $a, b, c$ có cùng số dư khi chia cho 3, đó là trường hợp đơn giản nhất. Sau đây là lời giải

a) Giả sử $2 a + b = m^{2}, 2 b + c = n^{2}, 2 c + a = p^{2}$ .
Cộng ba đẳng thức lại, ta được $3 (a + b + c) = m^{2} + n^{2} + p^{2}$ . Suy ra $m^{2} + n^{2} + p^{2}$ chia hết cho 3.
Ta thấy bình phương của một số nguyên khi chia cho 3 dư 1 hoặc 0. Do đó nếu 1 trong 3 số, chẳng hạn $m$ chia hết cho 3 thì $n^{2} + p^{2}$ chia hết cho 3 và như thế $n^{2}$ và $p^{2}$ cũng chia hết cho 3.
Hơn nữa $2 a + b = 3 a + (b - a)$ chia hết cho 3, suy ra $a - b$ chia hết cho 3. Tương tự thì $b - c, c - a$ chia hết cho 3. Suy ra $(a - b) (b - c) (c - a)$ chia hết cho 27.
b) Tồn tại. Chẳng hạn có thể lấy $a = 2, b = 0, c = 1$ .

Sau đây cũng là bài toán chia hết, nhưng ở mức độ khó hơn hẳn, đòi hỏi học sinh phải có suy luận tốt và nắm chắc được nhiều kiến thức.
Bài 2. (PTNK 2016 – CT) Cho $x, y$ là hai số nguyên dương mà $x^{2} + y^{2} + 10$ chia hết cho $x y$ .

a) Chứng minh rằng $x, y$ là hai số lẻ và nguyên tố cùng nhau.
b) Chứng minh $k = \frac{x^{2} + y^{2} + 10}{x y}$ chia hết cho 4 và $k \geq 12$ .

Nhận xét. Bài toán này cũng giống bài toán trên, là liên quan đến các số chính phương $x^{2}, y^{2}$ . Việc chứng minh chẵn lẻ liên quan đến số dư khi chia cho 4 của một số chính phương.

Câu a) chỉ là bài toán xét trường hợp khá dễ nhìn, khi phản chứng là giả sử $x, y$ không cùng là số lẻ, từ đó khi xét tính chẵn lẻ của $x^{2} + y^{2} + 10$ và $x y$ sẽ giải quyết được vấn đề. \ Việc chứng minh nguyên tố cùng nhau thì cách tiếp cận quen thuộc nhất là gọi ước chung lớn nhất và chứng minh nó bằng 1.
Câu b) khó hơn khi có hai ý, ý đầu có thể áp dụng tiếp câu a, nhưng ý sau việc chứng minh $k \geq 12$ có thể đánh lừa nhiều học sinh trong khi việc đơn giản chỉ là chứng minh $k$ chia hết cho 3 là giải quyết được bài toán, mà chứng minh $k$ chia hết cho $3$ cũng là việc xét số dư của tử và mẫu thức khi chia cho 3. Sau đây là lời giải chi tiết.

Lời giải.
a) Giả sử trong hai số $x, y$ có một số chẵn, vì vai trò $x, y$ như nhau nên có thể giả sử $x$ chẵn. Suy ra $x^{2} + y^{2} + 10$ chia hết cho 2, suy ra $y$ chẵn. Khi đó $x^{2} + y^{2} + 10$ chia hết cho 4, suy ra 10 chia hết cho 4 vô lý.
Vậy trong hai số đều là số lẻ.
Đặt $d = (x, y)$ , $x = d . x^{'}, y = d . y^{'}$ ta có $x^{2} + y^{2} + 10 = d^{2} (x^{' 2} + y^{' 2}) + 10$ chia hết cho $d^{2} x^{'} y^{'}$ . Suy ra 10 chia hết cho $d^{2}$ . Suy ra $d = 1$ . Vậy $x, y$ nguyên tố cùng nhau.
b) Đặt $x = 2 m + 1, y = 2 n + 1$ , suy ra $k = \frac{4 (m^{2} + m + n^{2} + n + 3}{(2 m + 1) (2 n + 1)}$ .
Ta có $4, (2 m + 1) . (2 n + 1)$ nguyên tố cùng nhau. Suy ra $m^{2} + n^{2} + m + n + 3$ chia hết cho $(2 m + 1) (2 n + 1)$ . Từ đó ta có $k$ chia hết cho 4. Chứng minh $k \geq 12$ bằng hai cách.
Cách 1. Ta có $x^{2} + y^{2} + 10 = k x y$ .
Nếu trong hai số $x, y$ có một số chia hết cho 3, giả sử $x$ chia hết cho 3. Ta có $y^{2} + 10$ chia hết cho 3 vô lý vì $y^{2}$ chia 3 dư 0 hoặc dư 1.
Vậy $x, y$ không chia hết cho 3, suy ra $x^{2} + y^{2} + 10$ chia hết cho 3 và $3, x y$ nguyên tố cùng nhau. Do đó $k$ chia hết cho 3.
Do đó $k$ chia hết cho 12, vậy $k \geq 12$ .
Cách 2. Xét $k = 4$ ta có $x^{2} + y^{2} + 10 = 4 x y$ () $\Leftrightarrow (x - 2 y)^{2} = 3 y^{2} - 10$ .
Ta có $(x - 2 y)^{2}$ chia 3 dư 0 hoặc 1 mà $3 y^{2} - 10$ chia 3 dư 2, nên phương trình () không có nghiệm nguyên dương.
Xét $k = 8$ ta có $x^{2} + y^{2} + 10 = 8 x y (*) \Leftrightarrow (x - 4 y)^{2} = 15 y^{2} - 10$ .
Ta có $(x - 4 y)^{2}$ chia 3 dư 0 hoặc 1 mà $15 y^{2} - 10$ chia 3 dư 2 nên (**) không có nghiệm nguyên dương.
Vậy $k \geq 12$ .

Sau chia hết, các kiến thức về phương trình nghiệm nguyên cũng rất quan trọng, trong nhiều bài thi của PTNK kĩ năng giải phương trình nghiệm nguyên giúp mình được nhiều việc.\
Sau đây là bài toán số học, nhưng bản chất số học thì ít mà đại số thì nhiều, chỉ việc biến đổi đại số vài dòng là xong. Tuy vậy nhiều học sinh sau khi đọc đề lại phát hoảng, vì đề bài phát biểu nghe rất “kinh”, đánh lừa được các thí sinh yếu bóng vía. Bài toán sau chế tác từ bài thi của Bungari:
Bài 3. (PTNK 2012 – CT) Số nguyên dương $n$ được gọi là số điều hòa nếu như tổng các bình phương của các ước
của nó ( kể cả 1 và n ) đúng bằng $(n + 3)^{2}$ .

a) Chứng minh rằng số 287 là số điều hòa.
b) Chứng minh rằng số $n = p^{3}$ ( $p$ nguyên tố ) không phải là số điều hòa.
c) Chứng minh rằng nếu số $n = p q$ ( $p, q$ là các số nguyên tố khác nhau) là số điều hòa thì $n + 2$ là số chính phương.

Nhận xét. Bài toán đưa ra định nghĩa số điều hòa, nghe có vẻ ghê gớm nhưng không có ý nghĩa mấy, hoặc không phù hợp với từ điều hòa hay dùng. Nhiều thí sinh đọc đề mà thuộc dạng yếu bóng vía sẽ bỏ qua, ngay cả bỏ qua câu a rất dễ. Tuy nhiên nếu đã hiểu định nghĩa, việc giải quyết các câu hỏi là điều khá dễ, cũng liên

Lời giải.

a) Số $n = 287$ có các ước dương là 1, 7, 41, 287. Ta có $1^{2} + 7^{2} + 41^{2} + 287^{2} = (287 + 3)^{2}$ nên 287 là số điều hòa.
b) Các ước dương của $n = p^{3}$ là $1, p, p^{2}, p^{3}$ . Giả sử $n$ là số điều hòa, ta có $(n + 3)^{2} = 1^{2} + p^{2} + p^{4} + p^{6} \Leftrightarrow p^{4} + p^{2} = 6 p^{3} + 8$ . Suy ra $p | 8$ mà $p$ nguyên tố nên $p = 2$ . Thử lại thấy không thỏa, vậy $n = p^{3}$ không phải là số điều hòa với mọi số nguyên tố $p$ .
c) Các ước dương của $n = p q$ là $1, p, q, p q$ . Vì $n$ là số điều hòa nên ta có:
$1 + p^{2} + q^{2} + p^{2} q^{2} = (p q + 3)^{2} \Leftrightarrow p^{2} + q^{2} = 6 p q + 8 \Leftrightarrow (p + q)^{2} = 4 (p q + 2)$ . Do 4 là số chính phương nên $p q + 2$ cũng là số chính phương hay $n + 2$ là số chính phương

Sau đây là một bài khá đẹp, ý tưởng từ phương pháp lùi vô hạn trong giải phương trình nghiệm nguyên, tuy vậy các phải có suy luận một chút khác biệt.
Bài 4. (PTNK 2014 – CT)

a) Tìm các số nguyên $a, b, c$ sao cho $a + b + c = 0$ và $a b + b c + a c + 3 = 0$ .
b) Cho $m$ là số nguyên. Chứng minh rằng nếu tồn tại các số nguyên $a, b, c$ khác 0 sao cho $a + b + c = 0$ và $a b + b c + a c + 4 m = 0$ thì cũng tồn tại các số nguyên $a^{'}, b^{'}, c^{'}$ sao cho $a^{'} + b^{'} + c^{'} = 0$ và $a^{'} b^{'} + b^{'} c^{'} + a^{'} c^{'} + m = 0$ .
c) Với $k$ là số nguyên dương, chứng minh rằng không tồn tại các số nguyên $a, b, c$ khác 0 sao cho $a + b + c = 0$ và $a b + b c + a c + 2^{k} = 0$ .

Lời giải
a) Từ $a + b + c = 0, a b + b c + c a = - 3$ ta có $a^{2} + b^{2} + c^{2} = 6$ . Do $a, b, c$ vai trò như nhau nên ta có thể giả sử $| a | \geq | b | \geq | c |$ . Khi đó $1 < | a | < 3$ . Suy ra $| a | = 2$ , suy ra $a = 2$ hoặc $a = - 2$ .
Với $a = 2$ thì $b + c = - 2, b^{2} + c^{2} = 2$ giải ra được $b = c = - 1$ .Ta có có bộ $(2; - 1; - 1)$ và các hoán vị. \ Với $a = - 2$ thì $b + c = 2, b^{2} + c^{2} = 2$ , giải ra được $b = c = 1$ , ta có bộ $(- 2; 1; 1)$ và hoán vị.
b) Ta có $a + b + c = 0$ chẵn (1)và $a b + b c + a c = - 4 m$ chẵn.(2)
Nếu 3 số $a, b, c$ đều lẻ, không thỏa (1).
Nếu có 1 chẵn, 2 lẻ thì không thỏa (2).
Do đó 3 số $a, b, c$ đều chẵn. Khi đó đặt $a^{'} = \frac{a}{2}, b^{'} = \frac{b}{2}, c^{'} = \frac{c}{2}$ thì $a^{'}, b^{'}, c^{'}$ thỏa đề bài.
c) Với $k = 0$ ta có $a + b + c = 0, a b + b c + a c = - 1$ thì $a^{2} + b^{2} + c^{2} = 2$ (3) . Không có bộ 3 số nguyên $a, b, c$ khác 0 thỏa (3).
Với $k = 1$ thì $a + b + c = 0, a b + b c + a c = - 2$ khi đó $a^{2} + b^{2} + c^{2} = 4$ (4). Giả sử $| a |$ nhỏ nhất khi đó $1 \leq a^{2} < 2$ (không có $a$ thỏa). Không tồn tại $a, b, c$ nguyên khác 0 thỏa (4).
Với $k > 1$ .
Nếu $k$ chẵn, đặt $k = 2 n$ ta có $a + b + c = 0, a b + b c + a c + 4^{n} = 0$ , theo câu b), tồn tại $a_{1}, b_{1}, c_{1}$ nguyên thỏa $a_{1} + b_{1} + c_{1} = 0, a_{1} b_{1} + a_{1} c_{1} + b_{1} c_{1} + 4^{n - 1} = 0$ .

Tương tự ta sẽ được $a_{n}, b_{n}, c_{n}$ nguyên thỏa $a_{n} + b_{n} + c_{n} = 0, a_{n} b_{n} + b_{n} c_{n} + a_{n} c_{n} = - 1$ (vô nghiệm).
Nếu $k$ lẻ đặt $k = 2 n + 1$ ta có $a + b + c = 0, a b + b c + a c + {2.4}^{n} = 0$ , làm tương tự trên ta được $a_{n} + b_{n} + c_{n} = 0, a_{n} b_{n} + b_{n} c_{n} + a_{n} c_{n} = - 2$ (vô nghiệm).
Vậy không tồn tại các số $a, b, c$ khác 0 thỏa đề bài.

Ngoài ra việc sử dụng đồng dư cũng được khai thác qua các bài toán chia hết hoặc các bài toán phương trình nghiệm nguyên, nhiều khi được sử dụng một cách bất ngờ cũng gây khó khăn cho thí sinh và rất ít thí sinh làm trọn vẹn, sau đây là một ví dụ:
Bài 5. (PTNK 2018 – CT) Cho $A_{n} = 2018^{n} + 2032^{n} - 1964^{n} - 1984^{n}$ với $n$ là số tự nhiên.

a) Chứng minh với mọi số tự nhiên $n$ thì $A_{n}$ chia hết cho $51$ .
b) Tìm tất cả những số tự nhiên $n$ sao cho $A_{n}$ chia hết cho $45.$

Nhận xét. Đây là dạng toán khá quen thuộc với học sinh, chỉ là việc xét các trường hợp một cách khéo léo và cẩn thận để giải quyết bài toán.

a) Do $2018 \equiv 1964 (mod 3) \Rightarrow 2018^{n} \equiv 1964^{n} (mod 3) .$
$2032 \equiv 1984 (mod 3) \Rightarrow 2032^{n} \equiv 1984^{n} (mod 3)$ .
$\Rightarrow A_{n} ⋮ 3.$
Ta lại có $2018 \equiv 1984 (mod 17) \Rightarrow 2018^{n} \equiv 1984^{n} (mod 17)$ .
$2032 \equiv 1964 (mod 17) \Rightarrow 2032^{n} \equiv 1964^{n} (mod 17)$ .
$\Rightarrow A_{n} ⋮ 17.$
Do $(3; 17) = 1$ nên $A_{n} ⋮ 51 \forall n$
b) $A_{n} = 2018^{n} + 2032^{n} - 1964^{n} - 1984^{n} .$

Ta xét các trường hợp của $n$ để $A_{n} ⋮ 5.$
Ta có $A_{n} \equiv (- 2)^{n} + 2^{n} - 2 \cdot (- 1)^{n}$ (mod 5).
Do đó nếu $n$ lẻ $\Rightarrow A_{n} \equiv 2$ (mod 5) $(loại)$ .
Nếu $n = 4 k \Rightarrow A_{n} \equiv 2 \cdot 2^{4 k} - 2 \equiv 2 - 2 \equiv 0$ (mod 5) (nhận)
Nếu $n = 4 k + 2 \Rightarrow A_{n} \equiv 2 \cdot 2^{4 k + 2} - 2 \equiv 8 - 2 \equiv 6$ (mod 5) (loại).
Vậy $A_{n} ⋮ 5 \Leftrightarrow n ⋮ 4.$
Ta xét các trường hợp của $n$ để $A_{n} ⋮ 9.$
Ta có
$A_{n} \equiv 2^{n} + (- 2)^{n} - 2^{n} - 4^{n} (mod 9)$

$\equiv 2^{n} - 4^{n} (mod 9) \quad (Do n chẵn).$
$\equiv 2^{n} (1 - 2^{n}) (mod 9)$

Vì $(2; 9) = 1 \Rightarrow 2^{n} - 1 ⋮ 9$ .
Xét $n = 3 k$ với $k \in N$ . Ta có $A_{n} \equiv 2^{3 k} - 1 \equiv (- 1)^{k} - 1 (mod 9) \Rightarrow k$ chẵn
Xét $n = 3 k + 1$ với $k \in N$ . Ta có $A_{n} \equiv 2^{3 k + 1} - 1 \equiv 2 \cdot (- 1)^{k} - 1 (mod 9) \quad (loại) .$
Xét $n = 3 k + 2$ với $k \in N$ . Ta có $A_{n} \equiv 2^{3 k + 2} - 1 \equiv 4 \cdot (- 1)^{k} - 1 (mod 9) \quad (loại) .$

Vậy $A_{n} ⋮ 45 \Leftrightarrow n ⋮ 12.$

Tóm lại bài toán số học thi vào lớp 10 Chuyên Toán luôn là bài toán khó, nhưng không phải không kiếm được điểm, chỉ cần thí sinh bình tĩnh vận dụng được kiến thức đã học có thể giải quyết được các ý a, ý b thì phức tạp hơn đòi hỏi phải phân tích và xử lí khéo léo cẩn thận hơn, âu cũng hợp lí cho đề thi chọn học sinh có năng khiếu toán.\
Sau đây có một số bài tập cho các em rèn luyện trước kì thi cam go này.

Bài tập rèn luyện

Bài 1. (Tuyển sinh vào lớp 10 Chuyên Toán trường PTNK 1997)
a) Tìm tất cả các số nguyên dương $n$ sao cho $n 2^{n} + 3^{n}$ chia hết cho 5.
b) Tìm tất cả các số nguyên dương $n$ sao cho $n 2^{n} + 3^{n}$ chia hết cho 25.

Bài 2. (Tuyển sinh vào lớp 10 Chuyên Toán trường PTNK 1997)
a) Tìm tất cả các số nguyên dương sao cho $2^{n} - 1$ chia hết 7.
b) Cho số nguyên tố $p \geq 5$ . Đặt $A = 3^{p} - 2^{p} - 1$ . Chứng minh $A$ chia hết cho $42 p$ .

Bài 3. Cho $n$ là số tự nhiên. Chứng minh rằng $3^{n} n^{3} + 1$ chia hết cho 7 khi và chỉ khi $3^{n} + n^{3}$ chia hết cho 7.

Bài 4. Tìm tất cả các số tự nhiên x, y thỏa: $5^{x} = y^{4} + 4 y + 1$ .

Bài 5. Chứng minh rằng phương trình $y^{2} + y = x + x^{2} + x^{3}$ không có nghiệm nguyên dương.

Bổ đề về số mũ đúng

BỔ ĐỀ VỀ SỐ MŨ ĐÚNG

(Thầy Nguyễn Ngọc Duy giáo viên trường PTNK TP Hồ Chí Minh)

Bổ đề số mũ đúng của một số nguyên là một hướng tiếp cận khá mới đối với các bài toán sơ cấp. Nó cung cấp một công cụ khá hữu hiệu để giải các phương trình Diophante hoặc các bài toán chia hết liên quan đến số mũ. Trong bài viết này tôi sẽ cố gắng mang đến một cái nhìn thật sơ cấp và tự nhiên đến vấn đề, trang bị thêm kiến thức và kĩ năng cho các các em học sinh để giải quyết các bài toán số học. Đặc biệt, ta sẽ dùng bổ đề số mũ đúng để giải quyết một số trường hợp đặc biệt của định lí lớn Fermat.

1. Kiến thức cần nhớ

Định nghĩa 1.1: Cho $(a, n) = 1$ . Kí hiệu cấp của a theo modulo n là $o r d_{n} (a)$ , là số nguyên dương d nhỏ nhất thỏa $a^{d} \equiv 1 (mod n)$ .

Tính chất 1.1: Nếu $x$ là số nguyên dương thỏa mãn $a^{x} \equiv 1 (mod n)$ thì $o r d_{n} (a) | x$ .

Định nghĩa 1.2: Cho $p$ là số nguyên tố, $x$ là số nguyên bất kì, kí hiệu $v_{p} (x) = n$ nếu $x$ chia hết cho $p^{n}$ nhưng không chia hết cho $p^{n + 1}$ .

Tính chất 1.2: Với $a, b$ là các số nguyên và $n$ là số nguyên dương thì:

$v_{p} (a b) = v_{p} (a) + v_{p} (b)$ .
Nếu $p | a$ thì $v_{p} (a) > 0.$
$v_{p} (a^{n}) = n v_{p} (a)$ .
$v_{p} (a + b) \geq min {v_{p} (a), v_{p} (b)}$ . Đẳng thức xảy ra chẳng hạn khi $v_{p} (a) \neq v_{p} (b) .$
$v_{p} (gcd (a, b)) = min (v_{p} (a), v_{p} (b))$ và $v_{p} (lcm (a, b)) = max (v_{p} (a), v_{p} (b)) .$

Định lý 1.1: Bổ đề số mũ đúng. Cho $p$ là số nguyên tố lẻ; $a, b$ không chia hết cho $p$

$i)$ Nếu $a - b$ chia hết cho p thì $v_{p} (a^{n} - b^{n}) = v_{p} (a - b) + v_{p} (n)$ .

$i i)$ Nếu $a + b$ chia hết cho $p, n$ lẻ thì $v_{p} (a^{n} + b^{n}) = v_{p} (a + b) + v_{p} (n)$ .

$i i i)$ Nếu $a, b$ lẻ thì $v_{2} (a^{n} - b^{n}) = v_{2} (\frac{x^{2} - y^{2}}{2}) + v_{2} (n)$ .

Chứng minh

Trước tiên, ta chứng minh: $v_{p} (a^{p} - b^{p}) = v_{p} (a - b) + 1$ $(*)$ . Ta có:

$a^{p} - b^{p} = (a - b) (a^{p - 1} + a^{p - 2} b + \dots + a b^{p - 2} + b^{p - 1}) .$

Do $a \equiv b (mod p)$ nên $a^{p - 1} + a^{p - 2} b + \dots + a b^{p - 2} + b^{p - 1} \equiv p . a^{p - 1} \equiv 0 (mod p)$ .

Suy ra : $a^{p - 1} + a^{p - 2} b + \dots + a b^{p - 2} + b^{p - 1}$ chia hết cho $p$ $(1)$ .

Ta chứng minh tiếp $a^{p - 1} + a^{p - 2} b + \dots + a b^{p - 2} + b^{p - 1} không chia hết cho p^{2} .$

Thật vậy, do $a \equiv b (mod p)$ nên $a = b + k p$ . Sử dụng khai triển nhị thức Newton ta có

$a^{p - 1} + a^{p - 2} b + \dots + b^{p - 1}$

$\equiv [(p - 1) k p b^{p - 2} + b^{p - 1}] + [(p - 2) k p b^{p - 2} + b^{p - 1}] + \dots + [k p b^{p - 2} + b^{p - 1}] + b^{p - 1} (mod p^{2})$

$\equiv \frac{p (p - 1)}{2} k p b^{n - 2} + p . b^{p - 1}$

$\equiv p b^{p - 1} (mod p^{2})$

Theo giả thiết thì $b$ không chia hết cho $p$ nên $p b^{p - 1}$ không chia hết cho $p^{2}$ . Do đó $a^{p - 1} + a^{p - 2} b + \dots + a b^{p - 2} + b^{p - 1}$ cũng không chia hết cho $p^{2}$ $(2)$ .

Từ $(1), (2)$ ta có: $v_{p} (a^{p - 1} + a^{p - 2} b + \dots + a b^{p - 2} + b^{p - 1}) = 1$ .

Vậy $v_{p} (a^{p} - b^{p}) = v_{p} (a - b) + 1$ .

Tương tự, ta cũng có: nếu m không chia hết cho p thì $v_{p} (a^{m} - b^{m}) = v_{p} (a - b)$ $(* *)$ .

Ta quay lại định lí. Đặt $v_{p} (n) = k \Rightarrow n = p^{k} . m$ , với $(m, p) = 1$ .

Áp dụng $(*)$ và $(* *)$ ta có:

$v_{p} (a^{n} - b^{n}) = v_{p} ({(a^{p^{k - 1} . m})}^{p} - {(b^{p^{k - 1} . m})}^{p})$

$= v_{p} (a^{p^{k - 1} . m} - b^{p^{k - 1} . m}) + 1 = \dots = v_{p} (a^{m} - b^{m}) + k$

$= v_{p} (a - b) + v_{p} (n) .$

Vậy ta đã chứng minh xong phần $i)$ của định lí.

Vì $n$ lẻ nên thay $b$ bởi $- b$ trong i. ta được $v_{p} (a^{n} + b^{n}) = v_{p} (a^{n} - {(- b)}^{n}) = v_{p} (a + b) + v_{p} (n)$

Vậy ta đã chứng minh xong phần $i i)$ của định lí. Tương tự cách làm trong $i)$ ta cũng có kết quả $i i i)$ .

Như vậy ta đã chứng minh xong bổ đề số mũ đúng. Sau đây ta sẽ sử dụng bổ đề để giải quyết một bài toán thú vị.

2. Các bài toán áp dụng

Bài toán Fermat lớn: Cho $n$ là số tự nhiên lớn hơn $2.$ Chứng minh rằng phương trình $a^{n} + b^{n} = c^{n}$ không có nghiệm nguyên dương.

Bài Toán Fermat lớn là bài toán cực kì thú vị. Nó tồn tại gần bốn thế kỉ, kích thích biết bao nhà toán học thế giới. Bài toán cuối cùng được chứng minh bởi nhà toán học Andrew Wiles vào năm 1993. Và người ta nói rằng sẽ không có phương pháp sơ cấp nào có thể chứng minh bài toán trên. Bài báo sẽ đề cập một trường hợp đặc biệt của bài toán: số $c$ là số nguyên tố. Và chúng ta sẽ giải quyết thông qua bổ đề số mũ đúng.

Bài toán 1: Cho số nguyên lẻ $n > 2$ , $p$ là số nguyên tố. Chứng minh rằng phương trình $a^{n} + b^{n} = p^{n}$ không có nghiệm nguyên dương.

Giải

Không mất tính tổng quát, giả sử phương trình có nghiệm $a \geq b$ .

$1.$ Nếu $a = 1 \Rightarrow b = 1$ , thế vào phương trình suy ra vô lí.

$2.$ Nếu $a = 2 \Rightarrow b = 1; 2$ .

Trường hợp $(a, b) = (2, 2) \Rightarrow p = 2$ (vô lí).
Trường hợp $(a, b) = (2, 1) \Rightarrow p = 3$ , thế vào phương trình ta được $3^{n} - 2^{n} = 1$ , cũng suy ra vô lí.

Vậy bắt buộc $a \geq 3$ , mà $p^{n} > a^{n} \Rightarrow p > 3$ , nên p là số nguyên tố lẻ. Do n lẻ, ta có : $p^{n} = a^{n} + b^{n} = (a + b) (a^{n - 1} - a^{n - 2} b + \dots - a b^{n - 2} + b^{n - 1})$

Suy ra $p | a + b$ (do $a + b > 1$ ). Áp dụng bổ đề số mũ đúng cho $p$ , ta có

$v_{p} (a^{n - 1} - a^{n - 2} b + \dots - a b^{n - 2} + b^{n - 1}) = v_{p} (a^{n} + b^{n}) - v_{p} (a + b) = v_{p} (n)$

Mà $a^{n - 1} - a^{n - 2} b + \dots - a b^{n - 2} + b^{n - 1}$ là lũy thừa của $p$ nên ta có $(a^{n - 1} - a^{n - 2} b + \dots - a b^{n - 2} + b^{n - 1}) | n .$

Do $a^{n - 1} - a^{n - 2} b + \dots - a b^{n - 2} + b^{n - 1} = \frac{1}{2} [a^{n - 1} + a^{n - 3} {(a - b)}^{2} + \dots + b^{n - 3} {(a - b)}^{2} + b^{n - 1}] \geq \frac{1}{2} (a^{n - 1} + b^{n - 1})$

Vì $a \geq 3$ , $n \geq 3$ nên $\frac{1}{2} (a^{n - 1} + b^{n - 1}) > n$ nên không thể $(a^{n - 1} - a^{n - 2} b + \dots - a b^{n - 2} + b^{n - 1}) | n .$

Vậy phương trình vô nghiệm khi $p$ là số nguyên tố.

Bài tập 2: Cho số nguyên $n > 2$ có ước lẻ khác 1, $p$ là số nguyên tố. Chứng minh rằng phương trình $a^{n} + b^{n} = p^{n}$ không có nghiệm nguyên dương.

Giải

Gọi $k > 1$ là ước lẻ của $n$ , giả sử $n = k m$ . Đặt $x = a^{m}; y = b^{m}$ . Phương trình trên trở thành

$x^{k} + y^{k} = p^{n} .$

Không mất tính tổng quát, giả sử $x \geq y$ . Tương tự bài toán $1$ ta sẽ loại được các trường hợp tầm thường $x = 1; x = 2$ . Nên ta xét bài toán với trường hợp $x, p \geq 3.$ Do $k$ lẻ, ta có $p^{n} = a^{k} + b^{k} = (a + b) (a^{k - 1} - a^{k - 2} b + \dots - a b^{k - 2} + b^{k - 1})$

Suy ra $p | b + a$ . Áp dụng bổ đề số mũ đúng cho $p$ ta có

$v_{p} (a^{k - 1} - a^{k - 2} b + \dots - a b^{k - 2} + b^{k - 1}) = v_{p} (a^{k} + b^{k}) - v_{p} (a + b) = v_{p} (k)$

Mà $a^{k - 1} - a^{k - 2} b + \dots - a b^{k - 2} + b^{k - 1}$ là lũy thừa của $p$ nên ta có $(a^{k - 1} - a^{k - 2} b + \dots - a b^{k - 2} + b^{k - 1}) | k$

Lập luận tương tự bài toán $1$ ta cũng suy ra vô lí. Vậy phương trình vô nghiệm .

Bài tập 3: Cho số nguyên $n = 2^{k}, k > 1$ , p là số nguyên tố. Chứng minh rằng phương trình $a^{n} + b^{n} = p^{n}$ không có nghiệm nguyên dương.

Giải

Tương tự Bài toán $1$ , ta loại được các trường hợp tầm thường nên ta chỉ xét đối với trường hợp $a, b$ có ít nhất một số lớn hơn $2$ , khi đó $p > 3$ . Phương trình trở thành dạng

$x^{4} + y^{4} = p^{2^{k}}$

trong đó $x, y$ có ít nhất một số lớn hơn $2$ và $(x, y) = 1$ .

Do $p$ lẻ nên $x, y$ khác tính chẵn lẻ. Không mất tính tổng quát, giả sử $x$ lẻ, $y$ chẵn. Ta có

$y^{4} = p^{2^{k}} - x^{4} = (p^{2^{k - 1}} + x^{2}) (p^{2^{k - 1}} - x^{2})$

Do $(p^{2^{k - 1}} + x^{2}; p^{2^{k - 1}} - x^{2}) = 2$ nên

${\begin{cases} p^{2^{k - 1}} + x^{2} = 2 {m_{1}}^{2} \\ p^{2^{k - 1}} - x^{2} = 2 {n_{1}}^{2} \end{cases}$

Suy ra

${\begin{cases} p^{2^{k - 1}} = {m_{1}}^{2} + {n_{1}}^{2} \\ x^{2} = {m_{1}}^{2} - {n_{1}}^{2} \end{cases}$

và $y^{2} = 2 m_{1} n_{1} .$

Ta thấy $(m_{1}; n_{1}) = 1$ vì nếu ngược lại thì $m_{1}$ và $m_{2}$ đều phải chia hết cho $p$ (vô lí) nên có các trường hợp sau

$1)$ Nếu $m_{1} = m_{2}^{2}, n_{1} = 2 n_{2}^{2}$ và $(m_{2}, n_{2}) = 1$ thì thế vào ta được

$p^{2^{k - 1}} = {m_{2}}^{4} + 4 {n_{2}}^{4} = ({m_{2}}^{2} + 2 m_{2} n_{2} + 2 {n_{2}}^{2}) ({m_{2}}^{2} - 2 m_{2} n_{2} + 2 {n_{2}}^{2})$

mà $({m_{2}}^{2} + 2 m_{2} n_{2} + 2 {n_{2}}^{2}, {m_{2}}^{2} - 2 m_{2} n_{2} + 2 {n_{2}}^{2}) = 1$ nên ${m_{2}}^{2} - 2 m_{2} n_{2} + 2 {n_{2}}^{2} = 1 \Leftrightarrow {(m_{2} - n_{2})}^{2} + {n_{2}}^{2} = 1 \Leftrightarrow m_{2} = n_{2} = 1.$ Trường hợp này không thỏa.

$2)$ Nếu $m_{1} = 2 m_{2}^{2}, n_{1} = n_{2}^{2}$ và $(m_{2}, n_{2}) = 1$ thì cũng tương tự.

Vậy phương trình không có nghiệm nguyên dương.

Như vậy sử dụng bổ đề số mũ đúng ta đã chứng minh được một trường hợp đặc biệt của Định lí lớn Fermat.

Sau đây, chúng ta sẽ sử dụng Bổ đề số mũ đúng để giải quyết một số bài toán khác.

Bài tập 4: Tìm bộ số nguyên dương $(a, b, p)$ trong đó $p$ là số nguyên tố thỏa $2^{a} + p^{b} = 15^{a} .$

Giải

Ta có $\forall x, y \in Z; n \in N$ thì $x^{n} - y^{n} ⋮ x + y$ nên $p^{b} = 15^{a} - 2^{a} ⋮ 13 \Rightarrow p = 13.$

Áp dụng bổ đề

$b = v_{13} (13^{b}) = v_{13} (15^{a} - 2^{a}) = v_{13} (15 - 2) + v_{13} (a) \Rightarrow v_{13} (a) = b - 1 \Rightarrow a ⋮ 13^{b - 1}$

Mà $a > 0$ nên $a \geq 13^{b - 1}$ , suy ra

$13^{b} = 15^{a} - 2^{a} = (15 - 2) (15^{a - 1} + 15^{a - 2} .2 + \dots + {15.2}^{a - 2} + 2^{a - 1})$

$\geq (15 - 2) (15^{13^{b - 1} - 1} + 15^{13^{b - 1} - 2} .2 + \dots + {15.2}^{13^{b - 1} - 2} + 2^{13^{b - 1} - 1})$

$\Rightarrow b = 1 \Rightarrow a = 1.$

Vậy nghiệm bài toán là $(a, b, p) = (1, 1, 13)$ .

Bài tập 5: Chứng minh rằng không tồn tại cặp số $(a, n)$ nguyên dương, $n > 2$ , sao cho ${(a + 1)}^{n} - a^{n}$ là lũy thừa bậc dương của $5.$

Giải

Giả sử tồn tại số nguyên dương $m$ sao cho ${(a + 1)}^{n} - a^{n} = 5^{m} .$

Nhận xét: nếu $a$ hoặc $a + 1$ chia hết cho $5$ thì số còn lại cũng cũng chia hết cho $5$ (vô lí). Nên cả hai số đều không chia hết cho $5.$ Ta xét các trường hợp:

$1.$ Nếu $a \equiv 1 (mod 5) \Rightarrow 0 \equiv {(a + 1)}^{n} - a^{n} \equiv 2^{n} - 1 (mod 5)$ . Suy ra $4 | n$ .

$2.$ Nếu $a \equiv 2 (mod 5) \Rightarrow 0 \equiv {(a + 1)}^{n} - a^{n} \equiv 3^{n} - 2^{n} (mod 5)$ . Suy ra $2 | n$ .

$3.$ Nếu $a \equiv 3 (mod 5) \Rightarrow 0 \equiv {(a + 1)}^{n} - a^{n} \equiv 4^{n} - 3^{n} (mod 5)$ . Suy ra $4 | n$ .

Do đó, $n$ luôn là số chẵn, đặt $n = 2 n_{1}$ , $(n_{1} \in N, n_{1} \geq 2)$ . Ta có

$5^{m} = {(a + 1)}^{2 n_{1}} - a^{2 n_{1}} = ({(a + 1)}^{2} - a^{2}) ({(a + 1)}^{2 (n_{1} - 1)} + \dots + {(a + 1)}^{2} a^{2 (n_{1} - 2)} + a^{2 (n_{1} - 1)})$

$= (2 a + 1) ({(a + 1)}^{2 (n_{1} - 1)} + {(a + 1)}^{2 (n_{1} - 2)} a^{2} + \dots + {(a + 1)}^{2} a^{2 (n_{1} - 2)} + a^{2 (n_{1} - 1)}) .$

Suy ra $5 | 2 a + 15$ , áp dụng bổ đề số mũ đúng ta được

$v_{5} ({(a + 1)}^{2 (n_{1} - 1)} + {(a + 1)}^{2 (n_{1} - 2)} a^{2} + \dots + {(a + 1)}^{2} a^{2 (n_{1} - 2)} + a^{2 (n_{1} - 1)})$

$= v_{5} ({(a + 1)}^{2 n_{1}} - a^{2 n_{1}}) - v_{5} (2 a + 1) = v_{5} (n_{1}) .$

Do ${(a + 1)}^{2 (n_{1} - 1)} + {(a + 1)}^{2 (n_{1} - 2)} a^{2} + \dots + {(a + 1)}^{2} a^{2 (n_{1} - 2)} + a^{2 (n_{1} - 1)}$ là lũy thừa của $5$ nên $n_{1} ⋮ ({(a + 1)}^{2 (n_{1} - 1)} + {(a + 1)}^{2 (n_{1} - 2)} a^{2} + \dots + {(a + 1)}^{2} a^{2 (n_{1} - 2)} + a^{2 (n_{1} - 1)})$ (vô lí vì về phải gồm $n_{1}$ số nguyên dương, $n_{1} > 1$ và $a + 1 \geq 2$ ).

Vậy không tồn tại cặp số $(a, n)$ nguyên dương, $n > 2$ sao cho ${(a + 1)}^{n} - a^{n}$ là lũy thừa bậc dương của $5.$

Bài tập 6: Cho hai số nguyên $a, n \geq 2$ sao cho tồn tại số nguyên dương k thỏa $n | {(a - 1)}^{k}$ . Chứng minh rằng n là ước của $1 + a + a^{2} + \dots + a^{n - 1}$ .

Giải

Giả sử $p$ là ước nguyên tố bất kì của $n$ . Theo giả thiết $n | {(a - 1)}^{k}$ nên p cũng là ước của $a - 1$ .

Do $a^{n} - 1 = (a - 1) (1 + a + a^{2} + \dots + a^{n - 1})$ nên áp dụng bổ đề số mũ đúng ta có

$v_{p} (1 + a + a^{2} + \dots + a^{n - 1}) = v_{p} (a^{n} - 1) - v_{p} (a - 1) = v_{p} (n) .$

Do mọi ước nguyên tố $p$ của n đều thỏa điều trên nên ta có $n | 1 + a + a^{2} + \dots + a^{n - 1} .$

Bài tập 7 (HSG Trung Quốc 2009): Tìm cặp số nguyên tố $(p, q)$ thỏa $p q | 5^{p} + 5^{q}$ (*).

Giải

Ta xét các trường hợp

$1.$ $p = q = 5$ thỏa mãn bài toán.

$2.$ Nếu có một số bằng $5$ , một số khác $5$ . Không mất tính tổng quát, giả sử $p = 5; q \neq 5$ . Ta có :

$5 q | 5^{5} + 5^{q} \Leftrightarrow q | 5^{4} + 5^{q - 1} \Leftrightarrow q | 5^{4} + 1 = 626$ do $5^{q - 1} \equiv 1 (mod q)$ nên suy ra $q = 2$ hoặc $q = 313$ .

$3.$ Nếu cả hai số $p, q \neq 5$ . Do $5^{p} \equiv 5 (mod p), 5^{q} \equiv 5 (mod q)$ nên

$(*) \Leftrightarrow {\begin{cases} 5^{p - 1} + 1 ⋮ q \\ 5^{q - 1} + 1 ⋮ p \end{cases} \Rightarrow {\begin{cases} 5^{2 (p - 1)} - 1 ⋮ q \\ 5^{2 (q - 1)} - 1 ⋮ p \end{cases}$

Do $5^{2 (p - 1)} - 1$ chia hết cho $q$ nhưng $5^{p - 1} - 1$ không chia hết cho $q$ nên

$v_{2} ({ord}_{q} (5)) = 1 + v_{2} (p - 1) .$

Do $5^{q - 1} - 1$ chia hết $q$ nên $q - 1 ⋮ o r d_{q} (5)$ nên

$v_{2} (q - 1) \geq 1 + v_{2} (p - 1) .$

Tương tự khi xét chia hết cho $p$ ta lại có $v_{2} (p - 1) \geq 1 + v_{2} (q - 1)$ (vô lí).

Vậy các cặp số thỏa mãn là $(p, q) = (2, 5); (5, 2); (5, 5); (5, 313); (313, 5) .$

Bài tập 8 (HSG Brazil 2009): Cho hai số nguyên tố $p, q$ sao cho $q = 2 p + 1$ . Chứng minh rằng tồn tại một số là bội của $q$ có tổng các chữ số của nó trong hệ cơ số $10$ nhỏ hơn $4.$

Giải

Do $p, q$ đều là số nguyên tố nên $q \geq 5$ .

Nếu $q = 5$ thì ta chỉ cần chọn số $10$ thì thỏa yêu cầu bài toán.

Nếu $q > 5$ , áp dụng Định lí Fermat nhỏ thì $q | 10^{q - 1} - 1 = 10^{2 p} - 1 = (10^{p} - 1) (10^{p} + 1)$

Suy ra $q | 10^{p} + 1$ hoặc $q | 10^{p} - 1$ .

$1.$ Nếu $q | 10^{p} + 1$ thì số $a = 10^{p} + 1$ là số thỏa yêu cầu đề bài.

$2.$ Nếu $q | 10^{p} - 1$ . Do $p$ là số nguyên tố và $q$ không là ước của $10 - 1$ (do $q > 5$ ) nên $p$ cũng chính là $o r d_{q} (10)$ . Do đó $10; 10^{2}; \dots; 10^{p}$ sẽ có số dư khác nhau khi chia cho $q .$

Ta sẽ có các trường hợp

Nếu tồn tại $1 \leq k \leq p$ mà $10^{k} \equiv p (mod q)$ thì ${2.10}^{k} + 1 \equiv 2 p + 1 \equiv 0 (mod q)$ . Khi đó số $a = {2.10}^{k} + 1$ là số thỏa yêu cầu đề bài.
Nếu tồn tại $1 \leq k \leq p$ mà $10^{k} \equiv 2 p (mod q)$ thì $10^{k} + 1 \equiv 2 p + 1 \equiv 0 (mod q)$ . Khi đó số $a = 10^{k} + 1$ là số thỏa yêu cầu đề bài.
Nếu không tồn tại $1 \leq k \leq p$ mà $10^{k}$ có số dư là $p$ hay $2 p$ khi chia cho $q .$ Thì ta sẽ chia các số dư còn lại của $q$ thành $p$ bộ $(1; 2 p - 1), (2; 2 p - 2), \dots, (p - 1; p + 1)$ (tổng $2$ phần tử của một bộ bằng $2 p$ ) . Do tập số dư khi chia cho $q$ của tập ${10; 10^{2}; \dots; 10^{p}}$ có $p$ phần tử nên Theo nguyên lí Dirichlet sẽ có ít nhất hai số $10^{k}$ và $10^{l}$ thuộc cùng một bộ. Khi đó số $a = 10^{k} + 10^{l} + 1$ sẽ chia hết cho $q$ là số thỏa yêu cầu đề bài.

Bài tập 9 (IMO Shortlist 1997): Cho $b, m, n$ là các số nguyên dương thỏa $m > 1; m \neq n$ . Biết $b^{m} - 1$ và $b^{n} - 1$ có cùng tập hợp các ước nguyên tố. Chứng minh $b + 1$ là lũy thừa của $2.$

Giải

Theo đề, gọi $p$ là ước nguyên tố bất kì của $b^{m} - 1$ và $b^{n} - 1$ .

Ta có kết quả quen thuộc: $(b^{m} - 1, b^{n} - 1) = b^{(m, n)} - 1,$ đặt $α = (m, n)$ nên $p | b^{α} - 1$ . Suy ra tồn tại $k, l \in N *$ thỏa $m = α k; n = α l$ .

Đặt $a = b^{α}$ , từ giả thiết suy ra mọi ước nguyên tố của $a^{k} - 1$ và $a^{l} - 1$ đều là ước của $a - 1$ . Nói cách khác, tập hợp các ước nguyên tố của $a^{k} - 1, a^{l} - 1$ và $a - 1$ là trùng nhau.

Do $m \neq n$ suy ra tồn tại một số $k$ hoặc $l$ lớn hơn 1. Giả sử số đó là k.

Ta chứng minh $a + 1$ là lũy thừa của 2.

Thật vậy:

$1.$ Nếu $k$ là số chẵn, đặt $k = 2^{β} . k^{'}$ ( $k^{'}$ là số lẻ).

Ta có: $a^{k} - 1 = (a^{k^{'}} - 1) (a^{k^{'}} + 1) (a^{2 k^{'}} + 1) \dots (a^{2^{β - 1} k^{'}} + 1) .$

Do đó mọi ước nguyên tố $q$ của $a^{k^{'}} + 1$ cũng là ước của $a - 1$

Mà $a^{k^{'}} + 1 ⋮ a + 1$ , $(a + 1; a - 1) = 1$ hoặc $2.$ Suy ra $2 ⋮ q \Rightarrow q = 2$ nên $a^{k^{'}} + 1$ là lũy thừa của $2.$ Suy ra $a + 1$ cũng là lũy thừa của $2.$

$2.$ Nếu $k$ là số lẻ, ta có $a^{k} - 1 = (a - 1) (a^{k - 1} + a^{k - 2} + \dots + a + 1)$

Gọi $q$ là ước nguyên tố bất kì của $a^{k - 1} + a^{k - 2} + \dots + 1$ . Do $a^{k - 1} + a^{k - 2} + \dots + a + 1$ là số lẻ nên, nên $q$ cũng lẻ và là ước của $a^{k} - 1$ . Do đó q cũng là ước của $a - 1$ .

Áp dụng bổ đề số mũ đúng của $q$ ta có

$v_{q} (a^{k - 1} + a^{k - 2} + \dots + 1) = v_{q} (a^{k} - 1) - v_{q} (a - 1) = v_{q} (k)$

Suy ra $k ⋮ (a^{k - 1} + a^{k - 2} + \dots + 1)$ (vô lí vì vế phải có k số nguyên dương, $a > 1$ ).

Vậy $a + 1 = b^{α} + 1$ là lũy thừa của $2$ .

Vì $b^{α} + 1$ là lũy thừa của $2$ nên nếu $α$ là số chẵn thì $b^{α} + 1 = {(b^{α ‘})}^{2} + 1$ hoặc là số lẻ hoặc chia 4 dư 2 nên chỉ có một trường hợp thỏa là $b = 1$ . Còn nếu $α$ là số lẻ thì $b^{α} + 1 = (b + 1) (b^{α - 1} + b^{α - 2} + \dots + b + 1)$ nên $b + 1$ cũng là lũy thừa của $2$ .

Bài tập 10 (IMO Shortlist 1999): Tìm các số nguyên dương $n, p$ trong đó p nguyên tố thỏa $n^{p - 1} | {(p - 1)}^{n} + 1$ .

Giải

Ta xét các trường hợp sau

$1.$ Nếu $p = 2 \Rightarrow n | 2 \Rightarrow n = 1; 2$ (thỏa).

$2.$ Nếu $p > 2$ , suy ra $p$ lẻ nên ${(p - 1)}^{n} + 1$ lẻ $\Rightarrow n$ lẻ

Gọi $q$ là ước nguyên tố nhỏ nhất của n $\Rightarrow q | n^{p - 1} | {(p - 1)}^{n} + 1$ $\Rightarrow q | {(p - 1)}^{2 n} - 1$

Mà : $q | {(p - 1)}^{q - 1} - 1 \Rightarrow q | {(p - 1)}^{(2 n, q - 1)} - 1$

Do n lẻ và $q$ là ước nguyên tố nhỏ nhất của n nên $(2 n; q - 1) = 2$ .

Suy ra $q | {(p - 1)}^{2} - 1 = (p - 2) p$ $\Rightarrow$ $q | p - 2$ hoặc $q = p$ . Ta lại có các trường hợp nhỏ

$(a)$ Nếu $q | p - 2 \Rightarrow 0 \equiv {(p - 1)}^{n} + 1 \equiv 1 + 1 \equiv 2 (mod q)$ $\Rightarrow q = 2$ (vô lí vì q lẻ)

$(b)$ Nếu $q = p$ . Áp dụng bổ đề số mũ đúng cơ số q ta có

$(p - 1) v_{p} (n) = v_{p} (n^{p - 1}) \leq v_{p} [{(p - 1)}^{n} + 1] = v_{p} (p - 1 + 1) + v_{p} (n) = 1 + v_{p} (n)$

Suy ra : $(p - 2) v_{p} (n) \leq 1 \Rightarrow p = 3$ và $v_{p} (n) = 1.$

Đến đây, bài toán trở thành : Tìm n để $n^{2} | 2^{n} + 1$ .

Nhận xét $n = 1$ thỏa yêu cầu bài toán nên ta xét $n > 1$ . Suy ra $n$ là số lẻ, gọi $r$ là ước nguyên tố nhỏ nhất của $n$ . Suy ra $r | 2^{n} + 1 | 2^{2 n} - 1$ , mà $r | 2^{r - 1} - 1$ nên suy ra $r | 2^{(2 n; r - 1)} - 1$ .

Do $n$ là số lẻ và $r$ là ước nguyên tố nhỏ nhất của $n$ nên $(2 n; r - 1) = 2$ nên $r = 3$ . Ta có đánh giá sau

$2 v_{3} (n) \leq v_{3} (4^{n} - 1) = v_{3} (4 - 1) + v_{3} (n) \Rightarrow v_{3} (n) \leq 1 \Rightarrow v_{3} (n) = 1.$ Suy ra $n = 3. m$ , $(m, n) = 1$ . Thế vào đề bài, ta được $m^{2} | 8^{m} + 1 | 8^{2 m} - 1.$

Nếu $m > 1$ , tương tự ta gọi $s$ là ước nguyên tố nhỏ nhất của $m .$ Suy ra $m$ là ước của $8^{2} - 1 = 63$ . Do đó $s = 7$ , điều này vô lí vì $8^{m} + 1$ chia $7$ dư $2.$ Suy ra $m = 1 \Rightarrow n = 3$ .

Vậy $(n, p) = (1, 2); (2, 2); (3; 3)$ .

Các bài toán tổ hợp trên dãy số

CÁC BÀI TOÁN TỔ HỢP TRÊN DÃY SỐ

Thầy Lê Phúc Lữ

(Lớp Cao học Khoa học tự nhiên TP.HCM)

Trong bài viết nhỏ này, chúng ta sẽ cùng xét khía cạnh tổ hợp của dãy số nguyên; khi cần đếm số lượng dãy thỏa mãn một điều kiện cho trước nào đó. Các phương pháp thường gặp: truy hồi, xuống thang, cực hạn, phản chứng, …

1. Các bài toán chọn lọc

Bài tập 1.1: Tìm tất cả các bộ số nguyên dương $x_{1}, x_{2}, x_{3}, \dots, x_{2017}$ sao cho có thể đặt chúng lên vòng tròn theo thứ tự đó mà $6$ số liên tiếp bất kỳ đều có thể chia thành hai nhóm $3$ có tổng bằng nhau.

Giải

Dùng phương pháp xuống thang.

Ta có $x_{i} + x_{i + 1} + x_{i + 2} + x_{i + 3} + x_{i + 4} + x_{i + 5} \equiv 0 (\mod 2)$ với mọi $i = 1, 2, 3, \dots, 2017$ nên $x_{i} \equiv x_{i + 6}$ với mọi $i .$

Vì $(6, 2017) = 1$ nên suy ra tất cả các số có cùng tính chẵn lẻ. Ta xét phép biến đổi dãy số sau:

Nếu tất cả các số cùng chẵn thì thay bằng $y_{i} = \frac{x_{i}}{2}$ .
Nếu tất cả các số cùng lẻ thì thay bằng $y_{i} = \frac{x_{i} + 1}{2}$ .

Dễ thấy dãy mới cũng thỏa và tổng $S = \sum_{i = 1}^{2017} a_{i}$ sẽ giảm ngặt nếu có một số nào đó trong dãy khác $1$ ; suy ra quá trình biến đổi sẽ dừng lại khi tất cả đều là $1$ . Vì ta thu được một dãy toàn là $1$ nên dãy ban đầu có tất cả các số hạng bằng nhau.

Nhận xét: Bài toán trên có thể thay việc chia 2 nhóm thành $3, 4, 5, \dots$ nhóm và vẫn giải được bằng cách tương tự. Ta xét các bài tương tự sau:

Bài tập 1.2 (APMO 2017): Bộ năm số nguyên là tốt nếu có thể đặt chúng là $a, b, c, d, e$ để $a - b + c - d + e = 29.$ Tìm tất cả các bộ $2017$ số sao cho $5$ số liên tiếp bất kỳ trong chúng đều tốt.

Ở bài toán này, điểm khó là không biết các số đã cho có dương hay không; vì thể, đại lượng tổng ở trên không xét tiếp tục được.

Tuy nhiên, cách áp dụng vẫn tương tự như sau:

Trừ tất cả các số của bộ cho $29$ , ta thu được điều kiện tốt trở thành $a - b + c - d + e = 0.$
Tất cả các số đã cho cùng tính chẵn lẻ, và chính xác là cùng chẵn.
Xét đại lượng $S = \sum_{i = 1}^{2017} | \frac{a_{i}}{2} |$ thì thông qua phép chia 2, tổng này giảm ngặt. Từ đó suy ra tất cả các số này phải là $0$ và tất cả ban đầu phải là $29.$

Bài tập 1.3 (VMO 2014): Tìm tất cả các bộ số $2014$ số hữu tỷ không âm sao cho nếu bỏ đi bất kỳ số nào trong chúng thì các số còn lại có thể được chia thành $3$ nhóm rời nhau, mỗi nhóm có $671$ số sao cho tích các số trong mỗi nhóm là bằng nhau.

Bài này khó hơn vì: số hữu tỷ chứ không nguyên, tích chứ không phải tổng, … Ta lần lượt giải quyết điều đó như sau:

Quy đồng mẫu để đưa về số nguyên.
Xét số mũ của 1 ước nguyên tố để đưa về tổng.
Chú ý thêm trường hợp số 0 (nếu có 1 số thì phải có ít nhất 4 số).

Bài tập 1.4: Cho dãy số nguyên dương $(a_{n})$ thỏa mãn:

$i)$ Gồm các số phân biệt nhau.

$i i)$ Với mọi $n$ thì $a_{n} \geq n .$

$i i i)$ $a_{1} = 5, a_{2} = 4, a_{3} = 3$ .

a) Chứng minh rằng tồn tại $n > 2017$ sao cho $a_{n} \neq n + 1$ ?

b) Giả sử $a_{n} = n + 2$ với mọi $n > 2017$ , hỏi có tất cả bao nhiêu dãy số như thế?

Giải

a) Bài toán có thể giải quyết dễ dàng bằng phản chứng và Dirichlet. Thật vậy, nếu $a_{n} = n + 1$ với mọi $n > 2017$ thì các số hạng $a_{4} \to a_{2017}$ sẽ nhận các giá trị trong tập hợp $6 \to 2018$ . Khi đó, sẽ có hai số hạng bằng nhau, không thỏa.

b) Nếu đã có $a_{n} = n + 2$ với mọi $n > 2017$ thì các số hạng $a_{4} \to a_{2017}$ sẽ nhận các giá trị trong tập hợp $6 \to 2019.$ Nhận xét:

$a_{2017} \in {2017, 2018, 2019}$ nên có $3$ cách chọn.
$a_{2016} \in {2016, 2017, 2018, 2019}$ nhưng vì $a_{2017}$ đã lấy một số nên cũng còn $3$ cách chọn.
Tương tự, đến $a_{6}$ vẫn có $3$ cách chọn. Còn lại $a_{5}$ có $2$ cách chọn và $a_{4}$ có $1$ cách chọn.

Theo nguyên lý nhân, ta có $2 \cdot 3^{2012}$ dãy thỏa mãn.

Bài tập 1.5: Xét lục giác $A B C D E F$ có độ dài cạnh là $1$ được điền các số như hình vẽ

Một con ếch xuất phát từ $A$ và nhảy đến các đỉnh sao cho mỗi bước nhảy đều có độ dài nguyên. Hành trình của ếch là dãy các tên đỉnh mà ếch đã nhảy qua; và hai hành trình được coi là khác nhau nếu ở một lần thứ $k$ nào đó, đỉnh mà ếch nhảy đến ở hai hành trình là khác nhau.

Gọi $m$ là số hành trình ếch nhảy sao cho tổng các số mà nó nhảy qua là $2017$ . Chứng minh rằng $m$ không phải là số chính phương.

Giải

Ta thấy $A C E$ và $B D F$ là hai tam giác đều có cạnh là $\sqrt{3}$ nên mỗi lần, ếch sẽ nhảy từ tam giác đều này đến tam giác đều kia.

Chia nhóm:

$I = (A, C, E)$ tương ứng với các số $(0, 0, 1)$ .
$I I = (B, D, F)$ tương ứng với $(1, 1, 2)$ .

Ta thấy ${x + y | x \in I, y \in I I} = {1, 1, 1, 1, 2, 2, 2, 2, 3}$ chứng tỏ tổng các số trên hai bước nhảy liên tiếp của ếch sẽ nhận giá trị là $4$ số $1$ , $4$ số $2$ và $1$ số $3.$ Nếu gọi $s_{n}$ là số hành trình của ếch có tổng là $n$ thông qua chẵn bước thì

$s_{n} = 4 s_{n - 1} + 4 s_{n - 2} + s_{n - 3} .$

Một cách tương tự, gọi $t_{n}$ là số hành trình của ếch có tổng là $n$ thông qua lẻ bước thì công thức truy hồi vẫn thế (chỉ khác ở các số hạng đầu).

Vì vậy nên nếu gọi $u_{n} = s_{n} + t_{n}$ là số hành trình của ếch có tổng là $n$ thì

$u_{n} = 4 u_{n - 1} + 4 u_{n - 2} + u_{n - 3} với n \geq 3.$

Ta có $u_{0} = 1, u_{1} = 6, u_{2} = 28$ và từ công thức truy hồi thì $m = u_{2017} \equiv u_{1} \equiv 2 (\mod 4)$ nên $m$ không thể là số chính phương, ta có đpcm.

Nhận xét: Bài toán có thể giải bằng cách gọi $6$ dãy truy hồi $a_{n}, b_{n}, c_{n}, d_{n}, e_{n}, f_{n}$ chỉ số hành trình của ếch có tổng là $n$ và kết thúc tại $A, B, C, D, E, F$ . Tuy nhiên, cách tiếp cận đó khá phức tạp, đòi hỏi phải khai thác nhiều các liên hệ giữa các đường đi.

Một bài toán tương tự:

Bài tập 1.6 (Ả Rập TST 2017): Người ta đặt các số $1, 2, 3, 4$ trên vòng tròn theo thứ tự đó. Một con kiến xuất phát từ số $1$ và ở mỗi bước, nó sẽ bò qua số bên cạnh. Hỏi con kiến có bao nhiêu cách bò sao cho tổng tất cả các số mà nó bò qua (kể cả số ban đầu) bằng 21?

Tương tự bài trên, ta cũng tìm được hệ thức truy hồi là $s_{n} = s_{n - 3} + 2 s_{n - 5} + s_{n - 7}$ . Từ đó tính được $s_{21} = 167.$

Bài tập 1.7: Đếm số dãy số nguyên dương $(a_{1}, a_{2}, \dots, a_{12})$ thỏa mãn các điều kiện sau:

a) $1 \leq a_{1} \leq a_{2} \leq \dots \leq a_{12} \leq 2017$

b) $a_{i} \equiv i^{2} (mod 12)$ .

Giải

Theo giả thiết, ta có

$a_{1} \equiv a_{5} \equiv a_{7} \equiv a_{11} \equiv 1 (mod 12)$

$a_{2} \equiv a_{4} \equiv a_{8} \equiv a_{10} \equiv 4 (mod 12)$

$a_{3} \equiv a_{9} \equiv 9 (mod 12)$

$a_{6} \equiv a_{12} \equiv 0 (mod 12)$

Đặt $a_{i} = 12 b_{i} + r_{i}$ với $i = 1, 2, 3, \dots, 12$ và $r_{i}$ là số dư tương ứng đã chỉ ra ở trên.

Do tính không giảm của dãy nên ta phải có

$0 \leq b_{1} \leq b_{2} \leq b_{3} < b_{4} < b_{5} < b_{6} \leq b_{7} \leq b_{8} \leq b_{9} < b_{10} < b_{11} < b_{12} \leq 168.$

Từ đó suy ra

$0 \leq b_{1} < b_{2} + 1 < b_{3} + 2 < b_{4} + 2 < b_{5} + 2 < b_{6} + 2 \leq b_{7} + 3 \leq b_{8} + 4 \leq b_{9} + 5$

$< b_{10} + 5 < b_{11} + 5 < b_{12} + 5 \leq 173$

Do các số liệt kê ở trên đều phân biệt và thuộc $[0; 173]$ nên số cách chọn một bộ như thế là $C_{174}^{12}$ . Đó cũng chính là số dãy cần tìm.

Nhận xét: Điều kiện thứ hai có thể thay bằng một hàm số tùy ý theo $i$ chứ không nhất thiết phải là $i^{2}$ , cách giải vẫn tương tự như trên.

Bài tập 1.8: Hỏi có bao nhiêu hoán vị $a_{1}, a_{2}, \dots, a_{2017}$ của $2017$ số nguyên dương đầu tiên thỏa mãn đồng thời các điều kiện sau:

$i)$ $a_{i + 1} - a_{i} \leq 1$ với mọi $i = 1, 2, 3, \dots, 2016.$

$i i)$ Có đúng một chỉ số $i$ với $1 \leq i \leq 2017$ sao cho $a_{i} = i$ ?

Giải

Trước hết, ta sẽ chứng minh nhận xét rằng số hoán vị của $n$ số nguyên dương đầu tiên thỏa mãn điều kiện i), gọi là hoán vị đẹp, sẽ là $2^{n - 1}$ . Thật vậy,

Đầu tiên, ta đặt số $1$ vào hoán vị.
Số $2$ có thể xếp trước hoặc sau số $1$ , có $2$ cách.
Số $3$ có thể xếp vào đầu dãy hoặc ngay sau số $2$ đã xếp trước đó, có $2$ cách.
Số $4$ có thể xếp vào đầu dãy hoặc ngay sau số $3$ đã xếp trước đó, cũng có $2$ cách. Cứ như thế cho đến $n .$

Do đó, có tất cả $2^{n - 1}$ cách xếp, tương ứng vời $2^{n - 1}$ hoán vị.

Tiếp theo, giả sử ta có $a_{i} = i$ .

Khi đó $a_{i + 1} \leq a_{i} + 1 = i + 1$ , nhưng không thể có $a_{i + 1} = i + 1$ (do chỉ có 1 chỉ số thỏa mãn ii) nên $a_{i + 1} \leq i$ , mà $a_{i} = i$ nên $a_{i + 1} \leq i - 1$ . Tiếp theo, $a_{i + 2} \leq a_{i + 1} + 1 \leq i$ nên $a_{i + 2} \leq i - 1$ .

Do đó, các số từ $a_{i + 1}$ đến $a_{2017}$ nhận giá trị không vượt quá $i - 1$ .

Lập luận tương tự, các số từ $a_{1}$ đến $a_{i - 1}$ phải nhận giá trị không nhỏ hơn $i + 1.$

Do đó, hai đoạn hoán vị phía trước và phía sau $a_{i}$ phải có độ dài bằng nhau, tức là $a_{1009} = 1009$ là số ở giữa.

Rõ ràng các hoán vị phía trước và phía sau $1009$ đều phải là hoán vị đẹp và được sắp xếp độc lập với nhau.

Vậy số hoán vị cần tìm là ${(2^{1007})}^{2} = 2^{2014} .$

Nhận xét: Nếu đề đổi số $2017$ thành $2018$ thì sẽ tồn tại hai chỉ số $i$ như trên và chúng sẽ cách đều hai đầu $1$ và $2018$ . Khi đó, đoạn ở giữa cũng sẽ cố định, tức là có $i < j$ để

$a_{k} = k$ với mọi $k = i, i + 1, \dots, j$ và $i + j = 2019.$

Phần trước $i$ và phần sau $j$ sẽ đổi chỗ cho nhau với số cách xếp là ${(2^{i - 1})}^{2}$ .

Bài tập 1.9: Cho dãy các số nguyên dương $(u_{n})$ thỏa mãn điều kiện

$0 \leq u_{m + n} - u_{m} - u_{n} \leq 1$ với mọi $m, n \in Z^{+}$ .

Chứng minh rằng tồn tại $a \in R^{+}$ sao cho $- 1 \leq u_{n} - [a n] \leq 1$ với mọi $n = 1, 2, 3, \dots, 2017.$

Giải

Ta đưa điều cần chứng minh về

$\frac{u_{n}}{n} < a < \frac{u_{n} + 1}{n} .$

Đến đây, gọi

$m = min {\frac{u_{n} + 1}{n} | n = 1, 2, 3, \dots, 2017}$ và

$M = max {\frac{u_{n}}{n} | n = 1, 2, 3, \dots, 2017.}$

Cần chỉ ra $m > M$ rồi chọn số $a$ nằm giữa $(m, M)$ là xong. Gọi $p, q$ lần lượt là các chỉ số nhỏ nhất để có dấu bằng xảy ra ở các đánh giá trên. Khi đó

$u_{p} + 1 = p m$ và $u_{q} = M q .$

Ngoài ra, $u_{k} + 1 > k m, \forall k < p$ và $u_{k} < k q, \forall k < q .$

Nếu $p = q$ thì hiển nhiên đúng.
Nếu $p > q$ , ta đặt $p = q + k$ thì $k < p$ nên $u_{k} + 1 > k m$ , vì $u_{p} \geq u_{q} + u_{k}$ (theo giả thiết) nên $p m - 1 > M q + k m - 1 \Leftrightarrow m > M .$
Nếu $p < q$ thì cũng chứng minh tương tự với chú ý rằng $u_{q} \leq u_{p} + u_{k} + 1.$

Nhận xét: Nếu đề bài đổi giả thiết thành $0 \leq u_{m + n} - u_{m} - u_{n} \leq 2$ ,

ta sẽ cần đến hai số $a, b$ sao mới thỏa mãn được kết luận (vì khoảng chênh lệch của các số hạng rộng hơn một tí), cụ thể là tồn tại $a, b > 0$ để

$- 1 \leq u_{n} - [a n] - [b n] \leq 1.$

Ở bài toán trên, ta còn chứng minh được một kết quả mạnh hơn là tồn tại $a$ để $u_{n} = [a n]$ với mọi $n .$ Một bài toán tương tự trong đề trường Đông miền Trung:

Bài tập 1.10: Cho hàm số $f : R \to R$ thỏa mãn $| f (x + y) - f (x) - f (y) | \leq 1, \forall x, y \in R$ . Chứng minh rằng tồn tại hàm cộng tính $g : R \to R$ thỏa mãn $| f (x) - g (x) | \leq 1, \forall x .$

Đây có thể nói là một phiên bản trên $R$ của bài toán trên (thay vì xét trên $N$ ).

Tiếp theo, ta xét lớp các bài toán sử dụng một định lý thú vị trong dãy số, số học. Trước hết, ta xét định lý Beatty với nội dung như sau:

Cho hai số vô tỷ dương $α, β$ . Xét hai dãy số:

$[α], [2 α], [3 α], \dots$ tạo thành dãy $A .$
$[β], [2 β], [3 β], \dots$ tạo thành dãy $B .$

Khi đó $\frac{1}{α} + \frac{1}{β} = 1$ khi và chỉ khi $A, B$ là phân hoạch của $Z^{+}$ .

Chứng minh

Định lý này có thể chứng minh bằng cách sử dụng các BĐT về phần nguyên. Dưới đây là cách chứng minh cho chiều đảo:

Với mỗi số nguyên dương $k$ , gọi $m, n$ là các số nguyên dương thỏa mãn

$[m α] \leq k < [(m + 1) α] và [n β] \leq k < [(n + 1) β] .$

Đặt $A = {[i α], 1 \leq i \leq m}$ và $B = {[j β], 1 \leq j \leq n}$ thì $| A | = m, | B | = n$ và $A, B$ là phân hoạch của tập hợp ${1, 2, 3, \dots, k}$ theo định nghĩa của đề bài.

Do đó $m + n = k$ . Theo bất đẳng thức phần nguyên thì $m α - 1 < k < (m + 1) α$ nên $\frac{m}{k + 1} < \frac{1}{α} < \frac{m + 1}{k}$ .

Tương tự $\frac{n}{k + 1} < \frac{1}{β} < \frac{n + 1}{k} .$

Suy ra $\frac{m + n}{k + 1} < \frac{1}{α} + \frac{1}{β} < \frac{m + n + 2}{k} hay \frac{k}{k + 1} < \frac{1}{α} + \frac{1}{β} < \frac{k + 2}{k} .$

Cho $k \to + \infty$ , ta thu được $\frac{1}{α} + \frac{1}{β} = 1.$

Bài tập 1.11: Hai dung dịch $A, B$ có đặc điểm: số đo thể tích của $1$ kg $A$ bằng số đo khối lượng của $1$ lít $B .$ Ngoài ra, $p$ lít $A$ nặng bằng $q$ lít $B$ với $p, q$ nguyên tố khác nhau. Mỗi dung dịch được chia cho vào các bình nhỏ giống nhau, cùng chứa $1$ lít và vỏ nặng $1$ kg. Chứng minh rằng có đúng một cách ghép các bình cùng loại ( $A$ hoặc $B$ ) lại với nhau mà khối lượng của chúng thuộc khoảng $(2017; 2018) .$

Giải

Gọi $x, y$ lần lượt là khối lượng riêng của các dung dịch thì $\frac{1}{x} = 1 \cdot y, p x = q y$ nên $x = \sqrt{\frac{q}{p}}, y = \sqrt{\frac{p}{q}} .$

Khối lượng mỗi bình là $α = 1 + \sqrt{\frac{q}{p}}, β = 1 + \sqrt{\frac{p}{q}}$ . Dễ thấy $\frac{1}{α} + \frac{1}{β} = 1$ , thỏa mãn định lý Beatty.

Suy ra hai dãy $[m α], [n β]$ là phân hoạch của số nguyên dương nên ta có đpcm.

Bài tập 1.12 (APMO 2006): Với mỗi số nguyên dương $n$ , gọi $a_{n}, b_{n}$ lần lượt là số cách viết $10^{n}$ trong hệ nhị phân, ngũ phân. Chứng minh rằng $(a_{n}), (b_{n})$ là phân hoạch của $Z^{+} ∖ {1} .$

Giải

Để giải bài này, chú ý rằng: số chữ số của $M$ trong hệ $p$ phân là $[\log_{p} M] + 1$ .

Ngoài ra, $α = \log_{2} 10, β = \log_{5} 10$ thỏa mãn điều kiện của định lý Beatty.

Từ đó, ta có một nhận xét thú vị rằng: tổng số chữ số của $2^{n}$ và $5^{n}$ trong hệ thập phân là $n + 1.$

Bài tập 1.13 (VN TST 2000): Cho số nguyên dương $k$ . Dãy số $(u_{n})$ xác định bởi: $u_{1} = 1$ và $u_{n + 1}$ là số nguyên dương nhỏ nhất không thuộc tập hợp

${u_{1}, u_{2}, \dots, u_{n}, u_{1} + k, u_{2} + 2 k, \dots, u_{n} + n k} .$

Chứng minh rằng tồn tại $α$ vô tỷ dương sao cho $u_{n} = [n α]$ với mọi $n .$

Giải

Để giải bài toán này, ta xét đa thức $P (x) = x^{2} + (k - 2) x - k$ với $k$ là số nguyên dương đã cho thì $P (x)$ có hai nghiệm phân biệt trái dấu. Hơn nữa, $Δ_{P (x)} = {(k - 2)}^{2} + 4 k = k^{2} + 4$ , không thể là số chính phương với bất kì số k nguyên dương nào nên hai nghiệm này đều là số vô tỉ. Ta thấy $P (1) = 1 + (k - 2) - k = - 1 < 0, P (2) = 4 + 2 (k - 2) - k = k > 0$ nên nghiệm dương của phương trình $P (x) = 0$ thuộc khoảng $(1, 2)$ . Gọi nghiệm đó là $a .$

Đặt $b = a + k$ thì $a, b$ đều vô tỉ và $a b = a (a + k) = a^{2} + a k = 2 a + k = a + b$ nên $\frac{1}{a} + \frac{1}{b} = 1$ .

Xét $f (n) = [n a], g (n) = [n b] = f (n) + k n$ với $n$ là số nguyên dương.

Ta sẽ chứng minh rằng $x_{n} = f (n)$ bằng quy nạp. Thật vậy,

– Với $n = 1$ , khẳng định hiển nhiên đúng vì $1 < a < 2.$

– Giả sử $x_{n} = f (n)$ với mọi $n = 1, 2, 3, \dots, m$ . Ta sẽ chứng minh rằng $x_{m + 1} = f (x_{m + 1})$ .

Ta có $f (i) = x_{i}, g (i) = f (i) + i k = x_{i} + i k$ với mọi $i = 1, 2, 3, \dots, m$ nên ta có tập hợp

$H = {x_{1}, x_{2}, \dots, x_{m}, x_{1} + k, x_{2} + 2 k, \dots, x_{m} + m k}$

$= {f (1), f (2), \dots, f (m), g (1), g (2), \dots, g (m)}$

Rõ ràng $f (m + 1) \notin H$ và $g (n) > f (n)$ với mọi $n$ , $f (n)$ là hàm số đồng biến trên $N *$ nên ta thấy rằng $f (m + 1)$ chính là số tự nhiên nhỏ nhất không thuộc H. Theo định nghĩa dãy số $(x_{n})$ đã cho thì ta có $x_{m + 1} = f (m + 1)$ .

Do đó, khẳng định cũng đúng với $m + 1.$ Theo nguyên lí quy nạp, ta có đpcm. Vậy số tự nhiên cần tìm chính là $a$ là nghiệm dương của phương trình $x^{2} + (k - 2) x - k = 0$ .

Nhận xét: Đây là một kết quả có từ $1959$ . Ta có thể phân tích cách tiếp cận như sau:

Xuất phát từ việc $α = \sqrt{2}, β = \sqrt{2} + 2$ thỏa mãn điều kiện Beatty. Ta có hai dãy với công thức

$a_{n} = [n \sqrt{2}], b_{n} = a_{n} + 2 n$ là phân hoạch của $Z^{+}$ .

Từ đó, để giấu dãy $b_{n}$ đi, ta chỉ cần xét $a_{n} + 2 n$ .

Để ý $a_{1} = 1, a_{2} = 2, a_{3} = 4, b_{1} = 3, b_{2} = 6, b_{3} = 10$ nên $a_{4}$ có thể định nghĩa là số nguyên dương nhỏ nhất không thuộc ${a_{1}, a_{2}, a_{3}, a_{1} + 2, a_{2} + 4, a_{3} + 6}$ . Đó chính là cơ sở để có bài toán trên.

Bài tập 1.14 (Dãy Wythoff): Cho chuỗi $S_{1} = 1$ . Chuỗi $S_{n}$ được tạo thành từ chuỗi $S_{n - 1}$ bằng cách thay $1 \to 01$ và $0 \to 1.$ Các chuỗi $S_{1}, S_{2}, S_{3}, \dots$ được ghép liên tiếp lại với nhau thành một chuỗi vô hạn $L$ . Gọi $a_{n}$ là vị trí của số $1$ thứ $n$ trong chuỗi $L .$ Chứng minh rằng tồn tại $α$ vô tỷ dương sao cho $a_{n} = [n α], \forall n .$

Ở đây, ta có nhận xét rằng số $0$ thứ $n$ được sinh ra bởi số $1$ thứ $n$ nên nếu gọi $k_{n}$ là số các số $0$ đứng trước số $1$ thứ $n$ và $b_{n}$ là vị trí của số $0$ thứ $n,$ ta sẽ có $a_{n} = n + k_{n}$ và $b_{n} = 2 n + k_{n}$ nên $b_{n} = a_{n} + n$ .

Chú ý rằng $(a_{n}), (b_{n})$ chính là phân hoạch của $Z^{+}$ nên dễ dàng tìm được $α$ là nghiệm của $\frac{1}{α} + \frac{1}{α + 1} = 1$ hay $α$ chính là tỷ số vàng.

Bài tập 1.15: Cho $n$ là số nguyên dương, hỏi có bao nhiêu dãy số $a_{1}, a_{2}, \dots, a_{2 n}$ sao cho

$i)$ $a_{i} \in {- 1, 1}$ với $i = 1, 2, 3, \dots, 2 n .$

$i i)$ $| \sum_{i = 2 k + 1}^{2 l} a_{i} | \leq 2$ với $0 \leq k < l \leq n$ ?

Giải

Gọi $S$ là tập hợp các dãy thỏa mãn đề bài và đặt $| S | = s_{n}$ . Gọi $T$ là tập hợp tất cả các tổng các $a_{i}$ lấy từ chỉ số lẻ bất kỳ đến $2 n .$ Theo giả thiết thì $T \subset {\pm 2, \pm 1, 0}$ , tuy nhiên, tất cả các tổng trong $T$ đều có chẵn số hạng mà mỗi số hạng đều là $\pm 1$ nên tất cả phải đều chẵn. Suy ra $T \subset {\pm 2, 0}$ .

Nếu trong $T$ chứa cả $2$ lẫn $- 2$ thì giả sử $\sum_{k = 2 i + 1}^{2 n} a_{k} = 2$ và $\sum_{k = 2 j + 1}^{2 n} a_{k} = - 2$ với $i < j$ , khi đó

$4 = \sum_{k = 2 i + 1}^{2 n} a_{k} - \sum_{k = 2 j + 1}^{2 n} a_{k} = \sum_{k = 2 i + 1}^{2 j} a_{k},$ mâu thuẫn.

Ứng với $(a_{1}, a_{2}, \dots, a_{2 n}) \in S$ , ta có phân loại sau:

Tất cả các tổng trong $T$ đều là $0$ , đặt số lượng dãy có tính chất này là $a_{n}$ .
Trong $T$ có chứa số $2$ , đặt số lượng dãy có tính chất này là $b_{n}$ .
Trong $T$ có chứa số $- 2$ , đặt số lượng dãy có tính chất này là $c_{n}$ .

Từ đó, ta dễ dàng chứng minh được hệ thức truy hồi

$a_{n + 1} = 2 a_{n}$

$b_{n + 1} = a_{n} + 2 b_{n} + c_{n}$

$c_{n + 1} = a_{n} + b_{n} + 2 c_{n}$

Chú ý rằng $a_{n} = 2^{n}$ và $a_{n} + b_{n} + c_{n} = s_{n}$ . Cộng hai công thức cuối lại, ta có

$b_{n + 1} + c_{n + 1} = 2 a_{n} + 3 (b_{n} + c_{n}) \Leftrightarrow s_{n + 1} - 2^{n + 1} = 2^{n + 1} + 3 (s_{n} - 2^{n})$ hay

$s_{n + 1} = 3 s_{n} + 2^{n} \Leftrightarrow s_{n + 1} + 2^{n + 1} = 3 (s_{n} + 2^{n}) .$

Với $n = 1$ , ta có $4$ dãy là $(1, 1), (- 1, - 1), (- 1, 1), (1, - 1)$ nên $s_{1} = 4.$

Từ đẳng thức trên, ta có $s_{n} + 2^{n} = 3^{n - 1} (s_{1} + 2^{1}) = 2 \cdot 3^{n}$ nên $s_{n} = 2 \cdot 3^{n} - 2^{n}$ .

Nhận xét: Bài toán thoạt nhìn có vẻ quen thuộc nhưng thật không đơn giản. Điều kiện đề cho là giá trị tuyệt đối của tất cả các tổng con từ vị trí lẻ đến vị trí chẵn bất kỳ đều không vượt quá $2$ buộc ta phải có đánh giá thích hợp mới có thể truy hồi được.

2. Bài tập áp dụng

Bài 1 (TP.HCM 2018): Hỏi có bao nhiêu hoán vị $(a_{1}, a_{2}, \dots, a_{164})$ của $164$ số nguyên dương đầu tiên sao cho $a_{i} \neq i$ và $a_{i} \equiv i (mod 41)$ với mọi $i = 1, 2, \dots, 164 ?$

Bài 2: (Bài toán phát kẹo) Cô giáo có $10$ loại kẹo (mỗi loại có nhiều viên) và cần phát cho $30$ học sinh của lớp (một em nhận không quá $1$ viên/loại), giả sử rằng các em này có học lực đôi một khác nhau. Hỏi cô giáo có bao nhiêu cách phát kẹo, biết rằng nếu học sinh $A$ giỏi hơn $B$ thì $B$ có kẹo gì là $A$ có kẹo đó (tính cả trường hợp không em nào nhận được kẹo)?

Bài 3: (Bài toán con nhện) Một con nhện có $8$ cái chân, $8$ cặp vớ – giày khác nhau (vớ chỉ dùng chung với chiếc giày tương ứng). Con nhện có bao nhiêu thứ tự mang vớ và giày để sao cho trên cùng một chân, giày phải được mang vào sau vớ?

Một số bài toán số học ôn thi vào 10 – P1

Bài 1. Tìm tất cả các số nguyên tố $p$ sao cho tổng các ước dương của $p^{4}$ là một số chính phương.

Lời giải

Theo đề ta có phương trình $1 + p + p^{2} + p^{3} + p^{4} = x^{2}$ .
Ta có $(2 p^{2} + p)^{2} < 4 x^{2} < (2 p^{2} + p + 2)$ .
Do đó $4 x^{2} = (2 p^{2} + p + 1) = 4 p^{2} + 4 p^{3} + 4 p^{2} + 4 p + 4$
$p^{2} - 2 p - 3 = 0 \Leftrightarrow p = 3$ .

Bài 2. Cho $m, n$ là các số nguyên dương thỏa $m + m + 1$ là một ước nguyên tố của $2 (m^{2} + n^{2}) - 1$ . Chứng minh rằng $m . n$ là một số chính phương.

Lời giải

Ta có $2 m^{2} + 2 n^{2} - 1 = (m + n)^{2} + (m - n)^{2} - 1 = (m + n - 1) (m + n + 1) + (m - n)^{2}$ chia hết cho $m + n - 1$ ,

suy ra $(m - n)^{2}$ chia hết cho $m + n + 1$ .

Mà $m + n + 1$ nguyên tố, suy ra $(| m - n |, m + n + 1) = 1$ , do đó $m = n$ , suy ra $m n = m^{2}$ là số chính phương.

Bài 3. Chứng minh rằng nếu tích của hai số nguyên tố cùng nhau là một số chính phương thì mỗi số cũng là số chính phương.

Lời giải

Cho $a b = x^{2}$ , trong đó $(a, b) = 1$ .\
Đặt $d = (a, x), a = a^{'} d, x = x^{'} d$ ta có $a^{'} b = x^{' 2} d$ . \
Do $(a^{'}, x^{' 2}) = 1$ nên $b$ chia hết cho $x^{' 2}$ . \
Mặt khác do $(a, b) = 1$ nên $(b, d) = 1$ , suy ra $x^{' 2}$ chia hết cho $b$ .\
Do đó $b = x^{' 2}$ , $a^{'} = d$ . Từ đó ta có $a = a^{' 2}, b = x^{' 2}$ là các số chính phương.\
\textbf{Nhận xét} Tương tự nếu $(a, b) = 1$ và $a b = x^{k}$ thì $a, b$ là lũy thừa bậc $k$ của một số nguyên.\
Đây là một bổ đề rất hay sử dụng.

Bài 4. Cho các số nguyên dương $a, b$ thỏa $2 a^{2} + a = 3 b^{2} + b$ .
a) Tìm $a, b$ biết $a$ và $b$ là hai số nguyên tố cùng nhau.
b) Chứng minh $a - b$ và $2 a + 2 b + 1$ là các số chính phương.

Lời giải

a) $a (2 a + 1) = b (3 b + 1)$ . Ta có $3 b + 1$ chia hết cho $a$ và $2 a + 1$ chia hết cho $b$ .
Đặt $2 a + 1 = k b$ , suy ra $3 b + 1 = k a$ . Suy ra $6 a b + 2 a + 3 b + 1 = k^{2} a b$ , suy ra $k = 1, 2$ .
Nếu $k = 1$ ta có $2 a + 1 = b, 3 b + 1 = a$ (Vô nghiệm).
Nếu $k = 2$ ta có $2 a + 1 = 2 b, 3 b + 1 = 2 a$ . (Vô nghiệm).
Phương trình vô nghiệm.
b) Ta có $(a - b) (2 a + 2 b + 1) = b^{2}$ .
Giả sử $p$ là ước nguyên tố của $a - b, 2 a + 2 b + 1$ , suy ra $p | b^{2} \Rightarrow p | b$ , suy ra $p | a$ , suy ra $p | 1$ (vô lý).\
Do đó $(a - b, 2 a + 2 b + 1) = 1$ .
Từ đó ta có $a - b, 2 a + 2 b + 1$ là các số chính phương.

Bài 5. Tìm tất cả số tự nhiên $a$ để tồn tại các số nguyên tố $p, q, r$ thỏa $a = \frac{p + q}{r} + \frac{q + r}{p} + \frac{p + r}{q}$ .

Lời giải

Nếu trong 3 số có đúng 2 số bằng nhau, giả sử $p = q \neq r$ . Khi đó ta có $a = 2 (\frac{p}{r} + \frac{r}{p}) + 2$ . Suy ra $\frac{2 (p^{2} + r^{2})}{p r} = a - 2$ .

Suy ra $p r | 2 (p^{2} + r^{2})$ , mà $(p, r) = 1$ , suy ra $p | 2$ , suy ra $p = 2$ . Vô lý.

Nếu 3 số đều khác nhau. Ta có $a p q r = p q (p + q) + q r (q + r) + p r (p + r)$ . Suy ra $p | q r (q + r)$ , suy ra $p | p + q + r$ .
Tương tự ta có $q | p + q + r, r | p + q + r$ . Suy ra $p q r | p + q + r$ .
Ta có $p q r > 4 r$ , suy ra $3 p q r > 4 (p + q + r) > 4 p q r$ . Vô lý.
3 số bằng nhau, thì $a = 6$ .

Bài tập

Bài 1. Cho $m, n$ và $d$ là các số nguyên dương. Chứng minh rằng nếu $m n^{2} + 1$ và $m^{2} n + 1$ cùng chia hết cho $d$ thì $m^{3} + 1$ và $n^{3} + 1$ cũng chia hết cho $d$ .

Bài 2. Cho $n \geq 3$ là số tự nhiên sao cho $3 n + 1$ là số chính phương. Chứng minh rằng có thể tìm được các số nguyên dương $a, b, c$ sao cho $x = \sqrt{1 + \frac{3 n + 3}{a^{2} + b^{2} + c^{2}}}$
là một số nguyên.

Bài 3. Tìm tất cả các số nguyên $n$ sao cho $n = q (q^{2} - q - 1) = r (2 r + 1)$ với $p, r$ là các số nguyên tố.

Phương trình nghiệm nguyên – Phương pháp đồng dư thức

Phương trình nghiệm nguyên – Phương pháp biến đổi thành tích

Phương trình nghiệm nguyên – Phương pháp biến đổi thành tổng

Toán Việt

Chia sẻ và học hỏi

Tag Archives: Sohoc

Phương trình nghiệm nguyên – Phương pháp sử dụng tính chất chia hết

Một số bài toán số học hay ôn thi vào 10 Chuyên Toán

Bổ đề về số mũ đúng

Các bài toán tổ hợp trên dãy số

Một số bài toán số học ôn thi vào 10 – P1

Phương trình nghiệm nguyên – Phương pháp đồng dư thức

Phương trình nghiệm nguyên – Phương pháp biến đổi thành tích

Phương trình nghiệm nguyên – Phương pháp biến đổi thành tổng