§ 6.1. Phương trình đồng dư bậc nhất
6.1.1. Khái niệm phương trình đồng dư
6.1.2. Phương trình đồng dư bậc nhất
§ 6.2. Hệ phương trình đồng dư một ẩn bậc nhất
§ 6.3. Phương trình đồng dư một ẩn bậc cao
§ 6.4. Phương trình đồng dư một ẩn bậc cao theo modul nguyên tố
§ 6.1. Phương trình đồng dư bậc nhất. |
| 6.1.1. Khái niệm phương trình đồng dư |
Khái niệm
Phương trình đồng dư đại số bậc n là một đồng dư thức có dạng:
aoxn + a1xn-1 + ... + an º 0 [mod m] [1] trong đó ai Î Z, i =
Giải phương trình là tìm tất cả các giá trị nguyên của x thỏa mãn đồng dư thức [1].
Nghiệm của phương trình đồng dư
Nếu số nguyên x = xo thỏa phương trình [1] thì mọi số x º xo [mod m] đều thỏa [1]. Tập hợp tất cả các giá trị đó được xem là một nghiệm của phương trình đồng dư [1].
Số nghiệm của phương trình [1] là số các phần tử trong một hệ thặng dư đầy đủ theo modul m mà thỏa [1].
Hai phương trình đồng dư được gọi là tương đương nếu tập hợp nghiệm của chúng trùng nhau.
Ví dụ: Xét phương trình x2 º 1 [mod 5]
Trong các số 0, 1, 2, 3, 4 của hệ thặng dư không âm bé nhất theo modul 5, hai số 1 và 4 thỏa mãn phương trình đã cho. Vậy phương trình có 2 nghiệm:
x º 1 [mod 5] và x º 4 [mod 5].
| 6.1.2. Phương trình đồng dư bậc nhất |
Dạng
Phương trình đồng dư bậc nhất là những phương trình có dạng
ax º b [mod m]. [1]
Để ý rằng phương trình [1] luôn có thể được đưa về dạng ax º b [mod m] với
Định lý 6.1 [ Định lý của phương trình đồng dư một ẩn ]
Phương trình ax = b [mod m] [1] có nghiệm Û d = [a,m]|b khi phương trình có nghiệm thì có d nghiệm.
Chứng minh: [Þ] [1] có nghiệm x º xo [mod m]
Þ axo º b [mod m] Þ axo = b + mt; t Î Z.
Þ axo - mt = b; d = [a,m] Þ d|b.
[Ü] Giả sử d = [a,m]|b. Khi đó: $ d > 0:
a = a1.d; b = b1.d; m = m1.d, [a1,m1] = 1
Khi x chạy qua hệ thặng dư đầy đủ mod m1, thì a1x - b1 cũng chạy qua hệ thặng dư đầy đủ mod m1 Þ $ xo sao cho a1xo º b1 [mod m1] hay x º xo [mod m1] là 1 nghiệm của phương trình a1x º b1 [mod m1].
Hiển nhiên, khi đó ta có: axo º b [mod m].
Hay nói cách khác: phương trình [1] có nghiệm.
Ta có x º xo [mod m1] Û x = xo + m1t; t Î Z. Chia t cho d ta được: t = q.d + r;
0 £ r < d. Khi t thay đổi trong Z thì r nhận tất cả các giá trị của {0, ..., d - 1}.
Þ x = xo + m1t = xo + m1[q.d + r] = xo + m1r + m1dq = xo + m1r + mq
Þ Nghiệm của phương trình [1] là: x º xo + m1r [mod m]; r Î {0, ..., d-1}
Þ [1] có d nghiệm: x º xo + 0.m1 [mod m]
M
x º xo + [d-1].m1[mod m]
Ví dụ: Phương trình: 9x º 6 [mod 15] [2]
Ta có: [9,15] = 3|6 Þ [2] có 3 nghiệm.
Ta có: [2] có thể viết lại:
3x º 2 [mod 5] Û x º 4 [mod 5]
Þ x = 4 + 5t = 4 + 5[3q + r]; r = 0, 1, 2
Þ
Phương pháp giải phương trình đồng dư bậc nhất một ẩn
Cho phương trình ax º b [mod m]
Ta luôn luôn có thể giả sử [a, m] = 1 với 1 £ a < m.
a. Phương pháp "chia cho a"
+ Nếu b M a Þ x º
+ b
Þ x º
Ví dụ: 4x º 12 [mod 7] Û x º 3 [mod 7]
3x º 4 [mod 11] Û 3 x º 4 + 11 [mod 11] Û x º 5 [mod 11]
b. Phương pháp dùng định lý Euler
Do [a,m] = 1 nên theo định lý Euler:
aj[m] º 1 [mod m]
Û a.aj[m]-1.b º b [mod m]
Þ x º aj[m]-1.b [mod m]
là nghiệm của phương trình [1].
Ví dụ: giải phương trình 2x º 9 [mod 17]
Ta có: [2,17] = 1 và j[17] = 16
Nên phương trình đã cho có nghiệm x º 215.9 [mod 17]
Mà ta có 24 º - 1 [mod 17] Þ 212 º - 1 [mod 17]
Þ 215 º - 8 [mod 17]
Þ 215.9 º - 72 [mod 17] º - 4 [mod 17]
Þ x º - 4 [mod 17].
c. Phương pháp dùng liên phân số
Do [a,m] = 1 Þ
Khai triển
Xét 2 giản phân cuối cùng:
Ta có: Pn-1.Qn - Qn-1.Pn = [-1]n
Mà m = Pn; a = Qn
Þ Pn-1.a - Qn-1.m = [-1]n
Þ a.Pn-1 º [-1]n [mod m]
Þ a.Pn-1.b º [-1]n.b [mod m]
Þ a.[-1]n.Pn-1.b º b [mod m]
Þ x º [-1]n.Pn-1.b [mod m]
Ví dụ: 11x º 40 [mod 47]
[11,47] = 1 Þ
Lập bảng các tử số của các giản phân ta có:
| qk | 4 | 3 | 1 | 2 | |
| Pk | 1 | 4 | 13 | 17 | 47 |
n = 3
P2 = 17
b = 40 º - 7 [mod 47]
Þ x º [-1]3.17[-7] [mod 47] º 25 [mod 47]
§ 6.2. Hệ phương trình đồng dư một ẩn bậc nhất |
Ta chỉ xét hệ phương trình đồng dư đơn giản nhất
[I]
Với m1, ..., mn nguyên tố sánh đôi
Định lý thặng dư Trung Hoa
Định lý 6.2: Hệ [I] có nghiệm [!] theo modul [m1. m2... mn].
Chứng minh: [$] Đặt M = m1.m2....mn; Mi =
Hiển nhiên [Mi, mi] = 1 và mj|Mi; j ¹ i.
Do [Mi, mi] = 1 Þ Phương trình Miy º 1 [mod mi]
Có nghiệm duy nhất y º Ni [mod mi]
Đặt xo = M1N1a1 + ... + MnNnan
Ta có: xo =
Vì mj|Ni; j ¹ i Þ xo là nghiệm của hệ [I]
[!] Giả sử x º x1 [mod mi]; i =
x º x2 [mod mi]
Þ x1 º x2 [mod mi] Þ x1 º x2 [mod [m1, ..., mn] º x2 [mod M]
Đảo lại, nếu x1 nghiệm đúng hệ đã cho và x2 º x1 [mod m1 ... mn]
thì x2 º x1 [mod mi] Þ x2 cũng là nghiệm của hệ [I].
Ví dụ: Bài toán điểm binh của Hàn Tín:
Ta có: M = 3.5.7 = 105; M1 = 35; M2 = 21; M3 = 15.
Phương trình M1y1 º 1 [mod m1] Û 35y º 1 [mod 3]
Û - y º 1 [mod 3] Û y º 2 [mod 3]
21 y º 1 [mod 5] Û y º 1 [mod 5]
15 y º 1 [mod 7] Û y º 1 [mod 7]
Þ xo = 35.2.2 + 21.1.3 + 15.1.4 º 263 [mod 105]
º 53 [mod 105]
§ 6.3. Phương trình đồng dư một ẩn bậc cao |
Xét phương trình đồng dư
f[x] = aoxn + a1xn-1 + ... + an º 0 [mod m] [1]
trong đó ao
Định lý 6.3 : Nếu m = p1a1 p2a2... pkak là sự phân tích chính tắc của m thành thừa số nguyên tố thì phương trình [1] tương đương hệ phương trình đồng dư:
[2]
Chứng minh: Giả sử x º xo [mod m] là một nghiệm của [1]
Þ f[xo] º 0 [mod m]. Do m là bội của các piai Þ f[xo] º 0 [mod piai]; i =
Þ x º xo [mod m] là 1 nghiệm của hệ [2].
Ngược lại x º xo [mod piai] là nghiệm của hệ [2].
Þ f[xo] º 0 [mod piai]; i =
Þ f[xo] º 0 [mod pia1 ... pkak]
Û f[xo] º 0 [mod m] Þ x º xo [mod m] là nghiệm của [1].
Từ định lý trên, ta thấy việc giải phương trình f[x] º 0 [mod m] được đưa về giải phương trình f[x] º 0 [mod pa]; p nguyên tố; a dương.
Bây giờ ta sẽ chứng minh rằng phép giải phương trình f[x] º 0 [mod pa] [3] được đưa về phép giải phương trình f[x] º 0 [mod p] [4].
Ta có mỗi nghiệm của [3] hiển nhiên là nghiệm của [4]. Giả sử x º x1 [mod p] là một nghiệm của [4] Þ x = x1 + pt1; t1 Î Z.
Thay giá trị x = x1 + pt1 vào phương trình:
f[x] º 0 [mod p2] Û f[x1 + pt1] º 0 [mod p2] [*]
Khai triển vế trái theo công thức Taylor tại x1: f[x] =
Þ f[x1 + pt1] = f[x1] + f'[x1].pt1 +
Để ý rằng
Þ
Þ [*] Û f[x1] + f'[x1].pt1 º 0 [mod p2]
Chia 2 vế cho p:
* Nếu f'[x1]
Þ [f'[x1],p] = 1 Þ [5] có nghiệm [!]
t1 º t'1 [mod p] Þ t1 = t'1 + pt2
Þ x = x1 + pt1 = x1 + p[t'1 + pt2] = x1 + pt'1 + p2t2 = x2 + p2t2.
* f'[x1] º 0 [mod p]
[5] trở thành 0.t1 º -
+
+
Trở lại [5], ta có: x = x2 + p2t2
Thay vào phương trình f[x] º 0 [mod p3]
Tương tự ta được f[x2] + p2t2f'[x2] º 0 [mod p3]
Þ
Þ x = x3 + p3t3
Quá trình cứ tiếp tục ... x = xa + pa.ta.
Như vậy, ta đã đưa việc giải phương trình f[x] º 0 [mod pa] về việc giải các
phương trình f[x] º 0 [mod p] ...; f[x] º 0 [mod pa-1].
* Cách giải phương trình f[x] º 0 [mod pa] p nguyên tố, a ³ 2
Bước 1: Giải phương trình f[x] º 0 [mod p] bằng cách thử qua hệ thặng dư đầy đủ modul p.
Giả sử phương trình có nghiệm x º xo [mod p]
Û x = xo + pt; t Î Z
Bước 2: Giải phương trình f[x] º 0 [mod p2]
~ f'[xo]t º -
Þ t = to + p.k Þ x = xo + pt
Û x = xo + p[to + pk] = xo + pto + p2.k
Û x = x1 + p2.k
Bước 3: Giải phương trình f[x] º 0 [mod p3]...
Giống như bước 2.
Ví dụ: Giải phương trình: f[x] = x4 + 2x3 - 9x + 1 º 0 [mod 53]
Xét phương trình f[x] º 0 [mod 5] Û x4 + 2x3 - 9x + 1 º 0 [mod 5]
Û x º 1 [mod 5]; x º 2 [mod 5]
* x º 1 [mod 5] Þ x = 1 + 5t; t Î Z.
Giải phương trình f[x] º 0 [mod 52]
Ta có: f'[x] = 4x3 + 6x2 - 9; f'[1] = 1; f[1] = - 5
Do đó: f[x] º 0 [mod p2] ~ 1.t º
Û t º 1 [mod 5] Þ t = 1 + 5k
Þ x = 1 + 5t = 1 + 5[1 + 5k] = 6 + 25k
Xét phương trình f[x] º 0 [mod 53]
ta có: f[6] = 1675; f'[6] = 1071
| 1 | 2 | 0 | - 9 | 1 | |
| 6 | 1 | 8 | 48 | 279 | 1675 |
| 4 | 6 | 0 | - 9 | |
| 6 | 4 | 30 | 180 | 1071 |
f[x] º 0 [mod 53] ~ f'[6].k º
Û k º - 67 [mod 5] Û k º 3 [mod 5]
Þ k = 3 + 5l; l Î Z
Þ x = 6 + 25[3 + 5l] = 81 + 125 l
Û x º 81 [mod 125]
Tương tự với x º 2 [mod 5] Þ x º 57 [mod 53]
Ví dụ: Giải phương trình:
Ta có:
Ta có:
*
·
*
*
·
*
*
*
*
*
*
Vậy phương trình đã cho có 11 nghiệm.
§ 6.4. Phương trình đồng dư một ẩn bậc cao theo modul nguyên tố |
Định lý 6.4.
Phương trình đồng dư bậc n theo modul nguyên tố p:
aoxn + a1xn-1 + ... + an º 0 [mod p] [1]
Với p X ao có không quá n nghiệm.
Chứng minh: ta chứng minh qui nạp trên n.
+ Nếu n = 0 thì phương trình có dạng
ao º 0 [mod p] với p X ao.
Þ Phương trình vô nghiệm.
Giả sử phương trình [1] có bậc n > 0. Giả sử [1] có nghiệm x º xo [mod p]. Tức là ta có:
aoxon + a1xon-1 + ... + an º 0 [mod p]
Trừ vào [1]:
ao[xn - xon] + a1[xn-1 - xon-1] + ... + an-1[x - xo] º 0 [mod p] [2]
Mỗi xk - xok có chứa nhân tử [x - xo] cho nên:
[2] Û [x - xo][boxn-1 + ... + bn-1] º 0 [mod p]
Do đó mọi nghiệm khác của [1] đều là nghiệm của
boxn-1 + ... + bn-1 º 0 [mod p] [3]
Thật vậy, giả sử x º x1 [mod p] là 1 nghiệm khác tức là x1
Vì p nguyên tố và x1
boxn-1 + ... + bn-1 º [mod p]
Vì bậc của [3] bằng n-1, theo giả thiết qui nạp
Þ [3] có không nhiều hơn [n-1] nghiệm.
Do đó [1] có không quá n nghiệm.
Hệ quả 6.5
Nếu phương trình đồng dư
aoxn + ... + an º 0 [mod p] có nhiều hơn n nghiệm Þ ai M p [i =
Hệ quả 6.6 [Định lý Wilson]
Số tự nhiên p là nguyên tố Û [p-1]! + 1 º 0 [mod p]
Chứng minh [Þ] * p = 2 Þ đúng
* p > 2: xét phương trình đồng dư
[x - 1][x - 2] ... [x - [p - 1]] - [xp-1 - 1] º 0 [mod p] [*]
Bậc của phương trình này không vượt quá [p-2] và rõ ràng nó có [p-1] nghiệm phân biệt:
x º 1, 2, ..., p-1 [mod p]
Þ Theo hệ quả trên, các hệ số của phương trình [*] đều chia hết cho p. Nói riêng số hạng tự do chia hết cho p.
Þ [p - 1]! + 1 º 0 [mod p]
[Ü] Nếu p không nguyên tố Þ p = m.n; 1 < m < n < p
[p - 1]! + 1 º 0 [mod p] Þ [p - 1]! + 1 º 0 [mod m]
Þ 1 º 0 [mod m]: mâu thuẫn Þ p nguyên tố.
BÀI TẬP
1. Cho p là số nguyên tố. Giải phương trình
a] x2 º 1 [mod p]
b] x2 º x [mod p.
Từ đó giải các phương trình: i] x2 º 1 [mod 21]; ii] x2 º x [mod 35].
2. Cho [a,b] = 1. Giải phương trình: [a + b]x º a2 + b2 [mod ab].
3. Giải các phương trình đồng dư:
a] 4x º 1 [mod 5]
b] 6x º 27 [mod 33]
c] 9x º 42 [mod 52]
d] 137x º 243 [mod 481]
e] 91x º 84 [mod 143]
4. Giải các hệ phương trình:
a]
5. Giải các phương trình Diophante:
a] 4x2 - 11x - 11y = 3
b] 3x2 - 2x = 7y
6. Giải các phương trình đồng dư:
a] 2x2 + 3x + 1 º 0 [mod 27]
b] x3 + 2x2 + 2x - 2 º 0 [mod 27]
c] 3x3 + 2x2 + x - 1 º 0 [mod 125]
d] x3 + 2x2 + 3x + 9 º 0 [mod 27]
e] x3 - 2x + 4 º 0 [mod 125]
f] x3 - 5x2 + 3 º 0 [mod 27]
g] x3 + x2 + 1 º 0 [mod 27]
h] x3 + x2 + 23 º 0 [mod 125]
i] x2 + 3x - 50 º 0 [mod 125]
j] x2 - x - 12 º 0 [mod 1000]
7. Tìm các số nguyên dương x sao cho: [x - 1]! + 1 = x2.
8. Tìm tất cả các số nguyên n sao cho
9. [Bài toán Trung Hoa cổ] Một băng cướp gồm 13 tên vừa cướp được một túi đựng một số đồng tiền vàng. Khi bọn cướp đem chia đều các đồng tiền vừa cướp thì có 3 đồng dư ra. Bọn cướp đánh nhau và hai tên bị giết. Chúng lại cố gắng chia đều các đồng tiền vàng, lần này có 10 đồng dư ra. Trận chiến lại nổ ra và lần này 4 tên cướp bị giết. Chúng lại chia các đồng tiền vàng và vẫn còn dư 4 đồng. Bọn chúng lại đánh nhau và 4 tên cướo bị giết. Các tên sống sót lại chia tiền vàng và lúc đó không có đồng nào dư ra. Hỏi số đồng tiền vàng ít nhất có thể có trong túi là bao nhiêu?