Lý thuyết Phương trình đồng dư | Đại học Yersin Đà Lạt

Phương trình đồng dư
Nguyễn Thị Hồng Thắm
 Đồng dư thức có dạng
Trong đó , với a0 không chia hết cho m đgl
phương trình đồng dư bậc n.
 Nếu x0 là một nghiệm của phương trình thì các phần tử thuộc lớp
thặng dư với x0 mod m cũng là nghiệm.
Chứng minh: Giả sử y thuộc lớp thặng dư với x0: ⇒ ⇒ Với mọi Mặt khác
Cộng từng vế n+1 đồng dư thức ta được: (mod m) ⇒ đpcm. Phương pháp chung: Ta có: khi và chỉ khi: ⇒
Do vậy việc giải phương trình đồng dư tương đương với giải một phương trình bất định dạng:
Phương trình có nghiệm duy nhất khi
1. Phương trình đồng dư tuyến tính
 Phương trình được gọi là phương trình đồng dư tuyến tính với a, b, x là các số đã biết.
 x0 là một nghiệm của phương trình khi và chỉ khi .
Ví dụ 1.1: Giải phương trình đồng dư:
Lời giải: Do nên phương trình có nghiệm duy nhất. Phương trình đã cho tương
đương với: . Lấy ⇒ . Vậy nghiệm của phương trình đã cho là (mod 23).
Ví dụ 1.2: Giải phương trình đồng dư sau:
Lời giải: Ta có: ⇒
Phương trình đồng dư
Nguyễn Thị Hồng Thắm
Từ (1) và (2), theo tính chất bắc cầu: . Do nên đơn giản 2 vế cho 2 ta được: hay
Lấy ⇒ . Do nên phương trình có nghiệm duy nhất là
2. Phương trình đồng dư bậc cao
Ví dụ 2.1: Giải phương trình đồng dư sau:
Lời giải: Phương trình đã cho tương đương với: . Dễ thấy khi thì ta tìm được
. Vậy phương trình có nghiệm là .
Ví dụ 2.2: Giải phương trình đồng dư sau:
Lời giải: Xét phương trình . Dễ thấy phương trình có nghiệm là
hay . Thay x vào phương trình cần giải và bỏ đi những số hạng chia hết cho 9 ta được: ⇔ ⇔ ⇔
Vậy phương trình có nghiệm là .
3. Hệ phương trình đồng dư
 Trường hợp 1: Hệ 2 phương trình { ⇔ {
Ví dụ 3.1:Giải hệ phương trình sau:{
Lời giải: Hệ phương trình đã cho tương đương với: { Từ (2) ta có: ⇔
Dễ thấy phương trình có nghiệm là hay
Vậy nghiệm của hệ phương trình là
Phương trình đồng dư
Nguyễn Thị Hồng Thắm
 Trường hợp 2: Hệ nhiều phương trình {
Ví dụ 3.2: Giải hệ phương trình sau:{
Lời giải: Từ (1) và (2) ta tìm được
Do đó hệ 3 phương trình tương đương với hệ: { ⇔ {
Từ (2’) cho ta: . Phương trình có nghiệm là hay
Vậy hệ phương trình có nghiệm là
4. Bậc c a phương trình đồng dư:
Ví dụ 4.1: Xác định bậc của phương trình:
Lời giải: Do 15 và 6 chia hết cho 3 nên bậc của phương trình không phải là bậc 6.
Phương trình trên tương đương với: . Vì nên bậc của phương trình là 4.
5. ng dụng đ nh lí Euler để giải bài tập đồng dư:
Ví dụ 5.1: Tìm ít nhất 1 nghiệm của phương trình sau:
Lời giải: Do nên ta có: Vì: Tương tự ta có:
Suy ra phương trình có nghiệm là 6. Một s bài tập
Bài 1: Chứng minh phương trình đồng dư sau có nghiệm(x, y, z, t) khác (0, 0, 0, 0):
Bài 2: Tìm ít nhất 1 nghiệm của phương trình đồng dư sau:
Bài 3: Chứng minh rằng trong các số tự nhiên thế nào cũng có số k sao cho chia hết cho
(Đề thi học sinh giỏi cấp II toàn quốc, 1983)
Bài 4: Một lớp gồm 40 học sinh đứng thành vòng tròn và quay mặt vào trong vòng tròn
để chơi bóng. Mỗi học sinh nhận bóng phải ném bóng qua mặt 6 bạn đứng ở tay trái
mình. Chứng minh rằng tất cả các học sinh đều nhận được bóng ném đến mình sau 40 lần ném bóng liên tiếp.
(Đề thi học sinh giỏi cấp II toàn quốc, 1987)
Bài 5: Tồn tại hay không một số nguyên x sao cho
Phương trình đồng dư
Nguyễn Thị Hồng Thắm
Tài liệu tham khảo:
 Bài giảng s h c (Đặng Hùng Thắng – Nguyễn Văn Ng c – Vũ Kim Th y)
 S H C – Bà chúa c a Toán h c (Hoàng Chúng)
 Tinh dưỡng các chuyên đề bồi dưỡng Olympic toán 10 ( Văn Phú Qu c – Huỳnh Công Thái)
 chuyendesohocVMF – Vietmaths.com