B i d ng h c sinh gi i toán 8ồ ưỡ ọ ỏ
CHUYÊN Đ: PH NG TRÌNH NGHI M NGUYÊNỀ ƯƠ Ệ
M C L CỤ Ụ
A.KI N TH C C N NHẾ Ứ Ầ Ớ 2
B.M T S PH NG PHÁP GI IỘ Ố ƯƠ Ả 3
1. Tìm m t nghi m riêng c a ph ng trình:ộ ệ ủ ươ ............................................................................................... 3
2. Tìm nghi m riêng c a ph ng trình (1) b ng thu t toán -clit m r ng.ệ ủ ươ ằ ậ ơ ở ộ ............................................. 4
3. Ph ng pháp dùng tính chia h tươ ế ............................................................................................................... 5
D ng 1.Phát hi n tính chia h t c a m t n ạ ệ ế ủ ộ ẩ ............................................................................................ 5
D ng 2.Ph ng pháp đa v ph ng trình c sạ ươ ư ề ươ ướ ố ................................................................................. 8
D ng 3.Ph ng pháp tách ra các giá tr nguyên.ạ ươ ị ..................................................................................... 17
4. Ph ng pháp s d ng tính ch n l c a n ho c xét s d t ng vươ ử ụ ẵ ẻ ủ ẩ ặ ố ư ừ ế ................................................... 19
D ng 1.S d ng tính ch n lạ ử ụ ẵ ẻ ................................................................................................................. 19
D ng 2.Xét tính ch n l và xét s d t ng vạ ẵ ẻ ố ư ừ ế ....................................................................................... 19
5. S d ng tính ch t a(a + 1) = k2ử ụ ấ .............................................................................................................. 21
6. S d ng lý thuy t ph n nguyênử ụ ế ầ ............................................................................................................. 22
7. Ph ng pháp dùng tính ch t c a s chính ph ngươ ấ ủ ố ươ ............................................................................... 22
D ng 1: Dùng tính ch t v chia h t c a s chính ph ngạ ấ ề ế ủ ố ươ .................................................................... 22
D ng 2: Đa v t ng các s chính ph ng ạ ư ề ổ ố ươ .......................................................................................... 23
D ng 3: Xét các s chính ph ng liên ti pạ ố ươ ế ............................................................................................ 27
D ng 4: S d ng đi u ki n ạ ử ụ ề ệ là s chính ph ngố ươ ................................................................................ 29
D ng 5: S d ng tính ch t: N u hai s nguyên liên ti p có tích là m t s chính ph ng thì m t trongạ ử ụ ấ ế ố ế ộ ố ươ ộ
hai s nguyên liên ti p đó b ng 0ố ế ằ ........................................................................................................... 30
D ng 6: S d ng tính ch t: N u hai s nguyên d ng nguyên t cùng nhau có tích là m t s chínhạ ử ụ ấ ế ố ươ ố ộ ố
ph ng thì m i s đu là s chính ph ngươ ỗ ố ề ố ươ ........................................................................................... 31
8. Ph ng pháp đa v c sươ ư ề ướ ố .................................................................................................................. 32
9. S d ng ph ng pháp k p gi aử ụ ươ ẹ ữ ............................................................................................................ 35
10. S d ng tính ch t chia h t và đng dử ụ ấ ế ồ ư ............................................................................................... 40
11. S d ng lý thuy t đng dử ụ ế ồ ư .................................................................................................................. 43
12. Ph ng pháp xu ng thangươ ố .................................................................................................................... 46
13. Ph ng pháp dùng b t đng th cươ ấ ẳ ứ ........................................................................................................ 48
D ng 1: S d ng b t đng th c c đi nạ ử ụ ấ ẳ ứ ổ ể ............................................................................................... 48
D ng 2: S p x p th t các nạ ắ ế ứ ự ẩ .............................................................................................................. 50
D ng 3: Ch ra nghi m nguyênạ ỉ ệ ............................................................................................................... 54
D ng 4: S d ng đi u ki n ạ ử ụ ề ệ 0 đ ph ng trình b c hai có nghi mể ươ ậ ệ ................................................. 54
14. Ph ng pháp kh n đ gi i ph ng trình nghi m nguyên.ươ ử ẩ ể ả ươ ệ ............................................................. 55
Biên so nạ: Tr n Đình Hoàng 0814000158ầ 1
B i d ng h c sinh gi i toán 8ồ ưỡ ọ ỏ
15. Ph ng pháp lùi vô h n, nguyên t c c c h nươ ạ ắ ự ạ ..................................................................................... 56
D ng 1: Ph ng pháp lùi vô h nạ ươ ạ ............................................................................................................ 56
D ng 2: Nguyên t c c c h nạ ắ ự ạ .................................................................................................................. 58
16. Đi u ki n ph ng trình có nghi m nguyênề ệ ươ ệ ........................................................................................ 58
17. Bài toán đa v gi i ph ng trình nghi m nguyênư ề ả ươ ệ ............................................................................ 59
D ng 1. Bài toán v s t nhiên và các ch sạ ề ố ự ữ ố ..................................................................................... 59
D ng 2. Bài toán v hàm s ạ ề ố ................................................................................................................... 60
D ng 3. Bài toán v tính chia h t v s nguyên tạ ề ế ề ố ố ................................................................................ 61
D ng 4. Các bài toán th c tạ ự ế ................................................................................................................... 63
C. BÀI T P V N D NGẬ Ậ Ụ 65
D. H NG D N GI IƯỚ Ẫ Ả 75
A. KI N TH C C N NHẾ Ứ Ầ Ớ
1. Gi i ph ng trình nghi m nguyên.ả ươ ệ
-Ph ng trình nghi m nguyên là ph ng trình có nhi u n s , t t c các h s c a ph ngươ ệ ươ ề ẩ ố ấ ả ệ ố ủ ươ
trình đu là s nguyên. Các nghi m c n tìm cũng là s nguyên. (Ph ng trình nghi mề ố ệ ầ ố ươ ệ
nguyên còn g i là ph ng trình Diophantus - mang tên nhà toán h c c Hy L p vào th kọ ươ ọ ổ ạ ế ỷ
th II).ứ
-Gi i ph ng trình f(x, y, z, ...) = 0 ch a các n x, y, z, ... v i nghi m nguyên là tìm t t cả ươ ứ ẩ ớ ệ ấ ả
các b s nguyên (x, y, z, ...) th a mãn ph ng trình đó.ộ ố ỏ ươ
2. M t s l u ý khi gi i ph ng trình nghi m nguyên.ộ ố ư ả ươ ệ
-Khi gi i các ph ng trình nghi m nguyên c n v n d ng linh ho t các tính ch t v chia h t,ả ươ ệ ầ ậ ụ ạ ấ ề ế
đng d , tính ch n l ,… đ tìm ra đi m đc bi t c a các n s cũng nh các bi u th cồ ư ẵ ẻ ể ể ặ ệ ủ ẩ ố ư ể ứ
ch a n trong ph ng trình, t đó đa ph ng trình v các d ng mà ta đã bi t cách gi iứ ẩ ươ ừ ư ươ ề ạ ế ả
ho c đa v nh ng ph ng trình đn gi n h n. Các ph ng pháp th ng dùng đ gi iặ ư ề ữ ươ ơ ả ơ ươ ườ ể ả
ph ng trình nghi m nguyên là:ươ ệ
Ph ng pháp dùng tính ch t chia h tươ ấ ế
Đa v ph ng trình tíchư ề ươ
Đa v c sư ề ướ ố
Ph ng pháp xét s d t ng vươ ố ư ừ ế
S d ng lý thuy t đng dử ụ ế ồ ư
Ph ng pháp s d ng b t đng th cươ ử ụ ấ ẳ ứ
Ph ng pháp dùng tính ch t c a s chính ph ngươ ấ ủ ố ươ
S d ng tính ch t ử ụ ấ
( )
+ =
2
a a 1 k
Biên so nạ: Tr n Đình Hoàng 0814000158ầ 2
B i d ng h c sinh gi i toán 8ồ ưỡ ọ ỏ
S d ng lý thuy t ph n nguyênử ụ ế ầ
Ph ng pháp lùi vô h n, nguyên t c c c h n.ươ ạ ắ ự ạ
S d ng ph ng pháp k p gi aử ụ ươ ẹ ữ
Ph ng pháp xu ng thangươ ố
S d ng delta c a ph ng trình b c haiử ụ ủ ươ ậ
B. M T S PH NG PHÁP GI IỘ Ố ƯƠ Ả
1. Tìm m t nghi m riêng c a ph ng trìnhộ ệ ủ ươ :
Lý Thuy tế
Đi v i ph ng trình b c nh t 2 n ax + by = c (a, b, c ố ớ ươ ậ ấ ẩ Z; a, b không đng th i b ng 0).ồ ờ ằ
Đnh lýị: Đi u ki n c n và đ đ ph ng trình ax + by = c (ề ệ ầ ủ ể ươ
a,b,c ; a,bι0
) có nghi mệ
nguyên là c s chung l n nh t c a a và b là c c a c.ướ ố ớ ấ ủ ướ ủ
H qu :ệ ả N u CLN(a;b) = 1 thì ph ng trình (1) có nghi m nguyên.ế Ư ươ ệ
Ph ng pháp gi iươ ả
Áp d ng tính ch t:ụ ấ N u ph ng trình (1) có m t nghi m nguyên (xế ươ ộ ệ 0; y0) thì nó có vô số
nghi m nguyên và t p h p các nghi m nguyên c a nó g m các c p s nguyên (x; y) xác đnhệ ậ ợ ệ ủ ồ ặ ố ị
b i:ở
0
0
b
x x t
d
a
y y t
d
= +
= −
v i d = CLN(a;b) và t = 0,ớ Ư
1,
2,...
Ví d 1.ụ (Bài toán dân gian)
“ Trăm trâu, trăm c ,ỏ
Trâu đng ăn năm,ứ
Trâu n m ăn baằ
L kh trâu già,ụ ụ
Ba con m t bó”.ộ
H i có bao nhiêu trâu đng, bao nhiêu trâu n m và bao nhiêu trâu già?ỏ ứ ằ
L i gi i:ờ ả
G i s trâu đng là x, s trâu n m là y thì s trâu già là 100 – (x + y) và ta có ph ng trìnhọ ố ứ ố ằ ố ươ
5x + 3y +
3
100 yx
= 100.
đó x, y là nh ng s nguyên d ng. Ph ng trình trên t ng đng v i: 7x + 4y = 100.Ở ữ ố ươ ươ ươ ươ ớ
Ta ph i tìm nghi m nguyên d ng c a ph ng trình này. D th y xả ệ ươ ủ ươ ễ ấ 0 = 0, y0 = 25 là m tộ
nghi m nguyên c a ph ng trình 7x + 4y = 100 nên t p h p nghi m nguyên c a nó g m t tệ ủ ươ ậ ợ ệ ủ ồ ấ
c các c p s nguyên (x;y) sau đây.ả ặ ố
4
25 7
x t
y t
=
= −
v i t là m t s nguyên tu ýớ ộ ố ỳ
B i vì x = 4t > 0 và y = 25 – 7t > 0 nên 0 < t < 4.ở
V y s trâu đng là 4t, s trâu n m là 25 – 7t và s trâu già là 25 + 3t v i t = 1, 2, 3ậ ố ứ ố ằ ố ớ
Tóm l i có ba kh năng cho s trâu m i lo i.ạ ả ố ỗ ạ
Biên so nạ: Tr n Đình Hoàng 0814000158ầ 3
B i d ng h c sinh gi i toán 8ồ ưỡ ọ ỏ
t S trâu đngố ứ S trâu n mố ằ S trâu giàố
1 4 18 78
2 8 11 81
3 12 4 84
Nghi m (xệ0 = 0; y0 = 25) đc g i là m t nghi m riêng và nghi m (x = 4t; y = 25 – 7t), tượ ọ ộ ệ ệ
Z, đc g i là nghi m t ng quát c a ph ng trình 7x + 4y = 100.ượ ọ ệ ổ ủ ươ
Nh v y đ gi i ph ng trình (1) trong đi u ki n gi i đc, ta ch c n tìm m t nghi mư ậ ể ả ươ ề ệ ả ượ ỉ ầ ộ ệ
riêng nào đó c a nó. Sau đây chúng ta s d ng thu t toán -clit m r ng đ ch ra m tủ ử ụ ậ ơ ở ộ ể ỉ ộ
nghi m riêng c a ph ng trình (1).ệ ủ ươ
2. Tìm nghi m riêng c a ph ng trình (1) b ng thu t toán -clit m r ng.ệ ủ ươ ằ ậ ơ ở ộ
Xét ph ng trình Đi-ô-phăng b c nh t hai n: ax + by = c v i d = CLN(a; b) là m t cươ ậ ấ ẩ ớ Ư ộ ướ
c a c, ch ng h n c = dc’ (c’ ủ ẳ ạ
Z)
Th c hi n thu t toán -clit m r ng trên hai s a, b chúng ta đc d và hai s ngyên x’, y’ự ệ ậ ơ ở ộ ố ượ ố
sao cho x y ra đng th c ax’ + by’ = d. Chúng ta nhân hai v c a đng th c này v i c’ sả ẳ ứ ế ủ ẳ ứ ớ ẽ
đc ượ
a(c’x’) + b(c’y’) = d.
Đng th c sau cùng này ch ng t c’x’, c’y’ là m t nghi m riêng c a ph ng trình (1) vàẳ ứ ứ ỏ ộ ệ ủ ươ
áp d ng đnh lí trên chúng ta đc t t c các nghi m nguyên c a nó.ụ ị ượ ấ ả ệ ủ
Ví d 1.ụ Tìm các nghi m nguyên c a ph ng trình: 1821x + 675y = 6.ệ ủ ươ
L i gi i:ờ ả
Tr c h t ta hãy tìm c p s nguyên x, y sao cho: 1821x + 675y = d (d = CLN(1821; 675))ướ ế ặ ố Ư
Th c hi n thu n toán -clit m r ng trên hai s 1821 và 675, ta có b ng sau.ự ệ ậ ơ ở ộ ố ả
t q r0r1r2x0x1x2y0y1y2
0 2 1821 675 471 1 0 1 0 1 -2
1 1 675 471 204 0 1 -1 1 -2 3
2 2 471 204 63 1 -1 3 -2 3 -8
3 3 204 63 15 -1 3 -10 3 -8 27
4 4 63 15 3 3 -10 43 -8 27 -116
5 5 15 3 0 -10 43 27 -116
Nhìn vào b ng trên ta đc d = CLN(1821; 675) = 3ả ượ Ư
x = 43; y = -116 và có đng th c 1821.43 + 675(-116) = 3.ẳ ứ
Chúng ta th y d = 3 là c c a 6 nên ph ng trình đã cho có nghi m nguyên. B ng cáchấ ướ ủ ươ ệ ằ
nhân hai v c a đng th c trên v i 2 ta đc 1821.86 + 675(-232) = 6ế ủ ẳ ứ ớ ượ
Đng th c cu i cùng này ch ng t (x = 86, y = -232) là m t nghi m riêng c a ph ngẳ ứ ố ứ ỏ ộ ệ ủ ươ
trình đã cho và do đó nghi m t ng quát c a nó làệ ổ ủ
675
86 86 225
3
1821
232 232 607
3
x t t
y t t
= + = +
= − − = − −
t = 0,
,
2...
Biên so nạ: Tr n Đình Hoàng 0814000158ầ 4
B i d ng h c sinh gi i toán 8ồ ưỡ ọ ỏ
Ví d 2.ụ Ph ng trình 15x – 5y = – 20 t ng đng v i ph ng trình 3x – y = – 4 ươ ươ ươ ớ ươ hay y = 3x + 4
nên ta đc. ượ
4 3
x t
y t
=
= +
v i ớt = 0,
,
2...là t t c các nghi m c a ph ngấ ả ệ ủ ươ
trình 15x – 5y = – 20.
N u |a| và |b| đu l n h n 1. Bao gi ta cũng có th chuy n vi c tìm nghi m nguyên c aế ề ớ ơ ờ ể ể ệ ệ ủ
ph ng trình (1) v vi c tìm nghi m nguyên c a m t ph ng trình b c nh t hai n mà có ítươ ề ệ ệ ủ ộ ươ ậ ấ ẩ
nh t m t h s c a n là ấ ộ ệ ố ủ ẩ
1.
Ví d 3.ụ Gi i ph ng trình vô đnh: 17x – 47y = 5ả ươ ị
L i gi i:ờ ả
B i vì – 47 = 17(– 3) + 4 nên ta vi t ph ng trình d i d ng: 17(x – 3y) + 4y = 5ờ ế ươ ướ ạ
Đt x – 3y = z ặ
Z ta đc ph ng trình: 17z + 4y = 5ượ ươ
vì 17 = 4.4 + 1 nên ph ng trình này đc vi t d i d ng: 4(y + 4z) + z = 5.ươ ượ ế ướ ạ
Đt y + 4z = t ặ
Z ta đc ph ng trình: 4t + z = 5.ượ ươ
Đây là m t ph ng trình b c nh t hai n có h s c a n z là 1 nó cho ta z = 5 – 4t, t ộ ươ ậ ấ ẩ ệ ố ủ ẩ
Z.
T đó y = t – 4z = t – 5( 5 – 4t ) = – 20 + 17t.ừ
x = z + 3y = (5 – 4t) = 3(– 20 + 17t) = – 55 + 47t
V y ph ng trình đã cho có nghi m là: ậ ươ ệ
5
0 17
5
2
47
y
t
t
x= −
+
+
= −
t = 0,
1,
2, ...
3. Ph ng pháp dùng tính chia h tươ ế
D ng 1.ạ Phát hi n tính chia h t c a m t nệ ế ủ ộ ẩ
Bài 1. Gi i ph ng trình nghi m nguyên 3x + 17y = 159 (1)ả ươ ệ
L i gi i:ờ ả
Gi s x, y là các s nguyên th a mãn ph ng trình (1). Ta th y 159 và 3x đu chia h t cho 3ả ử ố ỏ ươ ấ ề ế
nên
17y 3 y 3M M
(do 17 và 3 nguyên t cùng nhau). ố
Đt ặ
( )
y 3t t Z
=
thay vào ph ng trình ta đc: 3x + 17.3y = 159 ươ ượ
x + 17t = 53
Do đó:
( )
= −
=
x 53 17t t
y 3t
. Th l i ta th y th a mãn ph ng trình đã cho ử ạ ấ ỏ ươ
V y ph ng trình có nghi m (x, y) = (53 – 17t, 3t) v i t là s nguyên tùy ý.ậ ươ ệ ớ ố
Bài 2. Tìm nghi m nguyên c a ph ng trình 2x + 13y = 156ệ ủ ươ (1).
L i gi iờ ả
- Ph ng pháp 1ươ : Ta có
13y 13M
và
156 13M
nên
2x 13 x 13M M
(vì (2,3) = 1).
Đt ặ
x 13k (k Z)
=
thay vào (1) ta đc: ượ
y 2k 12
= − +
V y nghi m nguyên c a ph ng trình là: ậ ệ ủ ươ
x 13k (k Z).
y 2k 12
=�
= − +
- Ph ng pháp 2:ươ T (1)ừ
156 13y 13y
x 78
2 2
−
= = −�
,
Biên so nạ: Tr n Đình Hoàng 0814000158ầ 5