Chuyên đề Đồng dư

ĐỒNG DƯ
Định nghĩa.
Cho a, b, m là các số nguyên, m ¹ 0. 
Nếu a – b chia hết cho m thì a được gọi là đồng dư với b modulo m, ký hiệu a º b mod m.
Tính chất
Cho a, b, c, d là các số nguyên
Nếu a º b mod m thì b º a mod m 
Nếu a º b mod m và b º c mod m thì a º c mod m
Nếu a º b mod m và c º d mod m thì a + c º b + d mod m
Nếu a º b mod m và c º d mod m thì ac º bd mod m 
Nếu a º b mod m, k nguyên dương thì ak º bk mod m
Nếu a º b mod m và d| m thì a º b mod d
Nếu a º b mod m thì ac º bc mod cm với mọi c khác 0.
Nếu ab º ac mod m và (a,m) = 1 thì b º c mod m
 a º b mod mi ( i =1,2,,n) Û a º b mod [m1,m2,,mn]
Định lý Fermat nhỏ
Giả sử p nguyên tố, (a, p) = 1. Khi đó ap–1 º 1 mod p
Chứng minh.
Xét p – 1 số a, 2a, 3a, , (p – 1)a. Ta chứng minh rằng không tồn tại 2 số đồng dư trong phép chi a cho p.
Giả sử ka º la mod p với k, l Î{1,2,,p – 1} và k ¹ l Þ a(k – l) p Þ k – l p Þ k = l (mâu thuẩn)
Vậy khi chia p – 1 số trên cho p ta nhận được p – 1 số dư khác nhau từ 1, 2,, p – 1 
Suy ra a. 2a. (p – 1)a º 1.2.(p – 1) mod p Û (p – 1)!. ap–1 º (p – 1)! mod p
Vì ((p – 1)!,p) = 1 nên ap–1 º 1 mod p.
Từ định lý ta có ap º a mod p (với p nguyên tố, (a,p) =1)
Hệ thặng dư đầy đủ.
Tập hợp x1, x2, , xn gọi là một hệ thặng dư đầy đủ modulo m nếu với mỗi số nguyên y tồn tại duy nhất một xi sao cho y º xi mod m.
Tập {1,2,, m – 1, m} là một hệ thặng dư đầy đủ modulo m
Mọi hệ thặng dư đầy đủ modulo m đều có đúng m phần tử
Một tập gồm m phần tử là một hệ thặng dư đầy đủ modulo m nếu và chỉ nếu hai phần tử khác nhau bất kỳ của nó không đồng dư với nhau modulo m.
Cho số nguyên a và m > 0. Tập hợp tất cả các số nguyên x thỏa mãn x º a mod m được gọi là một lớp đồng dư modulo m, ký hiệu . Có m lớp đồng dư phân biệt modulo m, thu được bằng cách lấy lần lượt a = 1,2,,m. 
Một tập hợp {r1,r2,,rn} được gọi là một hệ thặng dư thu gọn modulo m nếu (ri,m) = 1, ri ¹ rj "i ¹ j, 1 £ i, j £ n và với mọi số nguyên x nguyên tố cùng nhau với m thì tồn tại ri sao cho ri º x mod m.
Số các phần tử của hệ thặng dư thu gọn modulo m được xác định bởi hàm Euler là số các số nguyên dương không vượt quá m và nguyên tố cùng nhau với m.
Hàm có các tính chất sau
với (m,n) = 1
Nếu p nguyên tố, ,
Nếu , pi là các số nguyên tố thì
Ví dụ : , , , 
Định lý.	
Cho (a,m) = 1 và r1, r2,., rn là một hệ thặng dư thu gọn (đầy đủ) modulo m. Khi đó ar1, ar2, , arn cũng là một hệ thặng dư thu gọn (đầy đủ) modulo m.
Chứng minh.
Vì (a,m) = 1 nên nếu (ri,m) = 1 thì (ari, m) = 1. Ta chứng minh các phần tử của tập {ar1,ar2,,arn} đôi một phân biệt modulo m. Thật vậy, nếu ari = arj mod m thì do (a,m) = 1 nên ri º rj mod m (vô lý). Theo 4.4 ta có đpcm.
Định lý Euler. 
Giả sử m là số nguyên dương và (a,m) = 1. Khi đó mod m.
Chứng minh.
Giả sử r1, r2, , là hệ thặng dư thu gọn gồm các số nguyên dương không vượt quá m và nguyên tố cùng nhau với m. Theo định lý trên ta suy ra ar1, ar2, , là một hệ thặng dư thu gọn modulo m. Như vậy các đồng dư dương bé nhất của ar1, ar2,.., phải là các số r1, r2, , xếp theo một thứ tự nào đó. Vì thế ta có hay 
Vì nên 
Ví dụ. Tìm dư khi chia số 112010 cho số 24.
Giải
Ta có (11,24) = 1 Þ Þ 
 mod 24.
Phương trình đồng dư tuyến tính
Phương trình dạng ax º b mod m được gọi là phương trình đồng dư tuyến tính với a, b, m là các số đã biết.
x0 là một nghiệm của phương trình khi và chỉ khi ax0 º b mod m. 
Nếu x0 là nghiệm thì các phần tử thuộc lớp cũng là nghiệm.
Định nghĩa. 
Giả sử a, m là các số nguyên, m > 1. Nghiệm của phương trình ax º 1 mod m được gọi là nghịch đảo của a modulo m.
Định lý.
Nghịch đảo của a modulo m là duy nhất Û (a,m) = 1
Chứng minh.
Gọi a’ là nghịch đảo của a modulo m Þ aa’ º 1 mod m Þ aa’ + mb = 1 Þ (a,m) = 1
Đảo lại nếu (a,m) = 1 Þ tồn tại a’, m’ sao cho aa’ + mm’ = 1 Þ aa’ º 1 mod m Þ a’ là nghịch đảo của a modulo m. a’ là duy nhất bởi vì nếu có a’’ sao cho aa’’ º 1 mod m thì aa’ º aa’’ mod m , mà (a,m) = 1 Þ a’ º a’’ mod m
Hệ quả.
Nếu p nguyên tố thì mỗi phần tử của tập hợp {1,2, , p – 1} đều có nghịch đảo duy nhất modulo p.
Định lý.
Nếu (a,m) = 1 thì phương trình ax º b mod m có nghiệm duy nhất theo modulo m.
Chứng minh.
Ta có {1,2,,m} là một hệ thặng dư đầy đủ modulo m và (a,m) =1 nên {a,2a, ,ma} cũng là một hệ thặng dư đầy đủ modulo m Þ có đúng một phần tử của hệ này đồng dư với b mod m . Suy ra đpcm.
Định lý tồn tại nghiệm phương trình đồng dư tuyến tính.
Giả sử (a,m) = d. Khi đó phương trình ax º b mod m (1) có nghiệm khi và chỉ khi d| b
Hơn nữa, khi d | b thì (1) có d nghiệm phân biệt modulo m, đó là 
 (2)
trong đó t là nghiệm duy nhất của phương trình (3)
Chứng minh.
Nếu phương trình có nghiệm là x0 Þ ax0 = b + mt Þ d| b
Đảo lại, nếu d | b thì phương trình có nghiệm t duy nhất 
Þ phương trình ax º b mod m cũng có nghiệm t .
Mỗi nghiệm của (3) là nghiệm của (1) và ngược lại. 
Dễ thấy rằng (2) là d nghiệm của (3) nên (2) cũng là d nghiệm của (1). Ngoài ra hai nghiệm của (2) là phân biệt theo modulo m. Thật vậy nếu Þ Þ r – s d Þ r = s
Tiếp tục, ta chứng minh (1) không còn nghiệm nào khác ngoài (2). 
Giả sử y là nghiệm của (1) Þ ay º b mod m Þ ay º at mod m Þ y º t mod m Þ y º t mod m/d Þ y = t + km/d . Ta có k º r mod d với 0 £ r < d. Do đó Þ y º t + rm/d mod m Þ y thuộc (2).
Ví dụ. Giải phương trình 12x º 7 mod 23
Giải
Do (12,23) = 1 nên phương trình luôn có nghiệm duy nhất.
Ta tìm một số nguyên k sao cho 7 + 23k chia hết cho 12. Chọn k = 7
Þ 12x º 7.24 mod 23 Þ x º 14 mod 23
Mệnh đề.
Giả sử p là số nguyên tố. Số nguyên a là nghịch đảo modulo p của chính nó khi và chỉ khi a º 1 mod p hoặc a º – 1 mod p
Chứng minh.
Nếu a º 1 mod p hoặc a º – 1 mod p thì a2 º 1 mod p nên a là nghịch đảo modulo p của chính nó.
Ngược lại, giả sử a là nghịch đảo modulo của chính nó, tức là a2 º 1 mod p Þ a2 – 1 p Þ a + 1 p hoặc a – 1 p hay a º – 1 mod p hoặc a º 1 mod p.
Định lý Wilson.
Với số nguyên tố p, ta có (p – 1)! º – 1 mod p
Chứng minh.
Khi p = 2, ta có (p – 1)! = 1 º –1 mod 2
Giả sử p là số nguyên tố lớn hơn 2, khi đó mỗi số nguyên a với 1 £ a £ p – 1 tồn tại nghịch đảo a’ với 1 £ a’ £ p – 1 sao cho aa’ º 1 mod p. Theo mệnh đề trên chỉ có 2 số 1 và p – 1 là nghịch đảo modulo p của chính nó. Như vậy, ta có thể nhóm các số 2, 3,, p – 2 thành (p – 3)/2 cặp mà tích của chúng đồng dư 1 modulo p.
2.3. (p – 3)(p – 2) º 1 mod p
Þ (p – 1)! º 1(p – 1) º –1 mod p.
Mệnh đề đảo của định lý Wilson cũng đúng.
Định lý.
Giả sử p là số nguyên dương sao cho ( p – 1)! º – 1 mod p thì p là số nguyên tố.
Định lý đồng dư Trung Hoa.
Giả sử m1, m2, , mr là các số nguyên tố cùng nhau đôi một. Khi đó hệ phương trình đồng dư tuyến tính 
x º a1 mod m1
x º a2 mod m2
.
x º ar mod mr
có nghiệm duy nhất modulo m = m1m2mr.
Ví dụ. Giải hệ phương trình x º 2 mod 5, x º 3 mod 7, x º 5 mod 3
Giải
x º 2 mod 5 Þ x º 17 mod 5
x º 3 mod 7 Þ x º 17 mod 7
Þ x º 17 mod 35 
x º 5 mod 3 Þ x º 5 + 3.4 mod 3 Þ x º 17 mod 3
Þ x º 17 mod 105 
Bài tập
Chứng minh rằng nếu a là số nguyên chẵn thì a2 º 0 mod 4, nếu a là số nguyên lẻ thì a2 º 1 mod 4
Chứng minh rằng nếu a lẻ thì a2 º 1 mod 8
Chứng minh rằng n7 – n 42 với n nguyên dương
Chứng minh rằng nếu a + b + c 30 thì a5 + b5 + c5 30 (a,b,c Î Z)
Chứng minh rằng với n nguyên dương
Giả sử n là số tự nhiên không chia hết cho 17. Chứng minh rằng hoặc n8 – 1 17 hoặc n8 + 1 chia hết 17
Tìm tất cả các số nguyên n sao cho n.2n + 1 chia hết cho 3.
Với số nguyên n nào ta có 12 + 22 + + (n – 1)2 º 0 mod n
Tìm dư trong phép chia 
	b. 	c. 	d. 
Giải hệ 
x º 1 mod 2, x º 2 mod 3, x º 3 mod 5
x º 2 mod 11, x º 3 mod 12, x º 4 mod 13, x º 5 mod 17, x º 6 mod 19
x º 5 mod 6, x º 3 mod 10, x º 8 mod 15	
Chứng minh định lý đảo của định lý Wilson
Chứng minh rằng nếu p, q là các số nguyên tố khác nhau thì º 1 mod pq
Chứng minh nếu p nguyên tố và ap º bp mod p thì ap º bp mod p2
Chứng minh rằng nếu p là số nguyên tố lẻ thì 12.32(p– 4)2(p –2)2 º (–1)(p+1)/2 mod p
Chứng minh rằng nếu p nguyên tố thì (p – 2)! – 1 p nhưng nếu p > 5 thì (p –2)! – 1 không phải là một lũy thừa của p
Giả sử hàm số f: N* à N* thỏa mãn điều kiện f(mf(n)) = n2f(m) "m,n ÎN*
Chứng minh rằng f(2009) hoặc là số nguyên tố hoặc là bình phương của một số nguyên tố
Hãy xây dựng một hàm f thỏa mãn điều kiện trên.