Giáo trình môn Lý thuyết số

äy có đúng ϕ(ϕ(m)) các số u như vậy, hay m có đúng ϕ(ϕ(m)) căn nguyên thuỷ không đồng dư nhau modulo m.
Ví dụ 5.1.8. Giả sử m = 11. Do (2, 11) = 1 nên ord112 | ϕ(11) = 10. Ta thấy 21 ≡ 2 (mod 11), 22 ≡ 4 (mod 11), 25 ≡ 10 (mod 11); suy ra ord112 = ϕ(11). Vậy 11 có 2 là căn nguyên thuỷ, do đó 11 có cả thảy ϕ(ϕ(11)) = ϕ(10) = 4 căn nguyên thuỷ không đồng dư nhau modulo 11. Đó là: 21 = 2, 23 = 8, 27 = 128, và 29 = 512; hay cũng vậy: 2, 8, 7, và 6.  5.2 Căn nguyên thuỷ của số nguyên tố Trong mục này chúng ta sẽ chỉ ra rằng mọi số nguyên tố đều có căn nguyên thuỷ. Để đạt được điều này, trước hết chúng ta cần khảo sát vài tính chất của đồng dư đa thức. Giả sử f(x) là đa thức với hệ số nguyên. Chúng ta sẽ nói số nguyên c là nghiệm của f(x) modulo m nếuu f(c) ≡ 0 (mod m). Dễ dàng thấy rằng, nếu c là nghiệm của f(x) modulo m thì mọi số nguyên đồng dư với c modulo m cũng là nghiệm. 62 5. CĂN NGUYÊN THỦY Ví dụ 5.2.1. Đa thức f(x) = x2 +x+1 có đúng hai nghiệm không đồng dư nhau modulo 7, cụ thể là x ≡ 2 (mod 7) và x ≡ 4 (mod 7). Đa thức g(x) = x2 + 2 là không có nghiệm modulo 5. Định lý Fermat cũng chỉ ra rằng, nếu p là số nguyên tố thì đa thức h(x) = xp−1− 1 có đúng p− 1 nghiệm không đồng dư nhau modulo p, cụ thể là x ≡ 1, 2, 3, · · · , p− 1 (mod p).  Định lý 5.7. Định lý Lagrange. Giả sử p là số nguyên tố; f(x) = anx n + an−1xn−1+· · ·+a1x+a0 là đa thức với hệ số nguyên, có bậc n ≥ 1, (an, p) = 1. Thế thì f(x) ≡ 0 (mod p) có không quá n nghiệm không đồng dư nhau modulo p. Chứng minh. Chúng ta chứng minh định lý bằng phương pháp qui nạp. Khi n = 1, ta có f(x) = a1x + a0 với p
a1. Nghiệm của f(x) modulo p chính là nghiệm của đồng dư tuyến tính a1x ≡ a0 (mod p). Ta đã biết nếu (a1, p) = 1 thì a1x ≡ a0 (mod p) có duy nhất nghiệm modulo p. Giả sử định lý đã đúng cho các đa thức bậc n − 1. Nếu đa thức f(x) = anx n+an−1xn−1+· · ·+a1x+a0 có quá n nghiệm không đồng dư nhau modulo p. Thế thì có các số nguyên c0, c1, · · · , cn không đồng dư nhau modulo p sao cho f(ck) ≡ 0 (mod p) với mọi 0 ≤ k ≤ n. Khi đó ta có f(x)− f(c0) = an(xn − cn0 ) +an−1(xn−1 − cn−10 ) + · · ·+ a1(x− c0) = an(x− c0) (xn−1 + xn−2c0 + · · ·+ xcn−20 + cn−10 ) + +an−1(x− c0) (xn−2 + xn−3c0 + · · ·+ xcn−30 + cn−20 ) + . . . +a1(x− c0) = (x− c0)g(x) . trong đó g(x) là đa thức bậc n− 1 với hệ số bậc cao nhất cũng chính là an. Từ hệ thức trên ta có (ck − c0)g(ck) = f(ck)− f(c0) ≡ 0 (mod p). Nhưng với mọi k, 1 ≤ k ≤ n, ck ≡ c0 (mod p); hay (ck − c0, p) = 1. Vậy g(ck) ≡ 0 (mod p), với mọi k, 1 ≤ k ≤ n; điều này mâu thuẫn với giả 5.2. CĂN NGUYÊN THUỶ CỦA SỐ NGUYÊN TỐ 63 thiết qui nạp: g(x) có không quá n− 1 nghiệm không đồng dư nhau modulo p.
Định lý 5.8. Giả sử p là số nguyên tố và d là ước của p−1. Thế thì xd−1 ≡ 0 (mod p) có đúng d nghiệm không đồng dư nhau modulo p. Chứng minh. Đặt p− 1 = de. Ta có xp−1−1 = (xd)e−1 = (xd−1)(xd(e−1)+xd(e−2)+ · · ·+xd +1) = (xd−1)g(x). Vì p nguyên tố nên xp−1 − 1 = (xd − 1)g(x) ≡ 0 (mod p) khi và chỉ khi (xd − 1) ≡ 0 (mod p) hoặc g(x) ≡ 0 (mod p). Do xp−1− 1 ≡ 0 (mod p) có đúng p− 1 nghiệm và g(x) với bậc p− 1−d sẽ có không quá p− 1− d nghiệm không đồng dư nhau modulo p; ta suy ra xd − 1 ≡ 0 (mod p) có không ít hơn d nghiệm không đồng dư nhau modulo p. Do định lý 5.7 ta suy ra xd − 1 ≡ 0 (mod p) có đúng d nghiệm không đồng dư nhau modulo p.
Định lý 5.9. Giả sử p là số nguyên tố và d là ước của p− 1. Thế thì có đúng ϕ(d) số nguyên không đồng dư nhau modulo p và có bậc bằng d modulo p. Chứng minh. Ký hiệu F (d) là số các số nguyên dương nhỏ hơn p và có bậc d modulo p. Vì tất cả các số nguyên dương nhỏ hơn p đều có bậc và bậc là ước của p− 1 nên p− 1 = ∑ d|p−1 F (d). Mặt khác, theo định lý **refdl39 ta có p− 1 = ∑ d|p−1 ϕ(d). Vậy ∑ d|p−1 F (d) = ∑ d|p−1 ϕ(d). Để kết thúc việc chứng minh định lý, ta chỉ cần chứng minh rằng F (d) ≤ ϕ(d) với d | p− 1. Nếu F (d) = 0 thì F (d) ≤ ϕ(d) là hiển nhiên. Ngược lại, nếu ordpa = d thì a, a2, · · · , ad 64 5. CĂN NGUYÊN THỦY là các số đôi một không đồng dư nhau modulo p. Mỗi một trong các số này đều là nghiệm của (xd − 1) ≡ 0 (mod p), vì (ak)d = (ad)k ≡ 1 (mod p). Từ định lý 5.8 ta suy ra rằng, mỗi nghiệm của (xd − 1) ≡ 0 (mod p) đều đồng dư modulo p với một lũy thừa ak của a, 1 ≤ k ≤ d. Định lý 5.5 lại nói rằng, ak có bậc bằng d = ordpa khi và chỉ khi (k, d) = 1. Như vậy có đúng ϕ(d) số không đồng dư nhau modulo p và có bậc bằng d. Vậy F (d) ≤ ϕ(d).
Hệ quả 5.9.1. Mọi số nguyên tố đều có căn nguyên thuỷ. Chứng minh. Giả sử p là số nguyên tố. Theo định lý trên, với d = p − 1, ta có cả thảy ϕ(p − 1) số không đồng dư nhau modulo p và có bậc bằng p− 1 = ϕ(p).
5.3 Các số có căn nguyên thuỷ Trong mục này chúng ta sẽ chỉ ra tất cả các số có căn nguyên thuỷ. Trước hết chúng ta chỉ ra rằng các lũy thừa của mỗi số nguyên tố lẻ đều có căn nguyên thuỷ. Định lý 5.10. Nếu r là căn nguyên thuỷ của số nguyên tố lẻ p thì r hoặc r+p là căn nguyên thuỷ modulo p2. Chứng minh. Vì r là căn nguyên thuỷ modulo p nên ordpr = ϕ(p) = p − 1. Đặt n = ordp2r, ta có rn ≡ 1 (mod p2). Suy ra rn ≡ 1 (mod p). Theo định lý 5.1 thì p− 1 = ordp | n. Ta cũng có n = ordp2r | ϕ(p2) = p(p− 1). Vì p − 1 | n và n | p(p − 1) ta suy ra n = p − 1 hoặc n = p(p − 1). Nếu n = p(p − 1) thì r là căn nguyên thuỷ modulo p2 vì ordp2r = n = ϕ(p2). Ngược lại, nếu n = p− 1 ta có rp−1 = rn ≡ 1 (mod p2). 5.3. CÁC SỐ CÓ CĂN NGUYÊN THUỶ 65 Đặt s = r + p. Do s ≡ r (mod p) nên s cũng là căn nguyên thuỷ modulo p. Tương tự như trên, ta có ordp2s = p− 1 hoặc ordp2s = p(p− 1). Cũng tương tự như trên, để chứng minh s là căn nguyên thuỷ modulo p2 chúng ta chỉ cần chứng tỏ rằng ordp2s = p− 1. Ta có sp−1 = (r + p)p−1 = rp−1 + (p− 1)rp−2p + [ p− 1 2 ] rp−3p2 + · · ·+ pp−1 và rp−1 ≡ 1 (mod p2) nên sp−1 ≡ rp−1 + (p− 1)prp−2 ≡ 1− prp−2 (mod p2). Vì (r, p) = 1 nên prp−2 ≡ 0 (mod p2), suy ra sp−1 ≡ 1 (mod p2), hay ordp2s = p− 1.
Ví dụ 5.3.1. Ta đã biết r = 3 là căn nguyên thuỷ modulo p = 7. Sử dụng định lý ?? ta có ord493 = p− 1 = 6 hoặc ord493 = p(p− 1) = 42. Do r6 = 36 = 729 ≡ 1 (mod 49) ta suy ra r = 3 là căn nguyên thuỷ modulo 49.  Định lý 5.11. Nếu p là số nguyên tố lẻ thì pk có căn nguyên thuỷ với mọi số nguyên dương k. Hơn nữa, nếu r là căn nguyên thuỷ modulo p2 thì r là căn nguyên thuỷ modulo pk với mọi số nguyên dương k. Chứng minh. Hệ quả 5.9.1 nói rằng p có căn nguyên thuỷ, và do đó theo định lý 5.10 ta suy ra p2 cũng có căn nguyên thuỷ. Giả sử r là căn nguyên thuỷ modulo p2. Trước hết, bằng qui nạp chúng ta chứng minh rằng với mọi số nguyên k ≥ 2 đều có rp k−2(p−1) ≡ 1 (mod pk). Khi k = 2, ta có rp k−2(p−1) = rp−1 ≡ 1 (mod p2), vì ordp2r = ϕ(p2) = p(p−1). Giả sử rằng với số nguyên k ≥ 2 ta đã có rp k−2(p−1) ≡ 1 (mod pk). 66 5. CĂN NGUYÊN THỦY Vì (r, pk−1) = 1 nên theo định lý Euler, ta có rp k−2(p−1) = rϕ(p k−1) ≡ 1 (mod pk−1), và điều này kéo theo rp k−2(p−1) = 1 + dpk−1 trong đó p
d vì rp k−2(p−1) ≡ 1 (mod pk). Lũy thừa p hai vế của đồng dư trên, ta được rp k−1(p−1) = (1 + dpk−1)p = 1 + p(dpk−1) + [ p 2 ] (dpk−1)2 + · · ·+ (dpk−1)p. Suy ra rp k−1(p−1) ≡ 1 + dpk (mod pk+1). Nhưng p
d nên rp k−1(p−1) ≡ 1 (mod pk+1). Bây giờ chúng ta sẽ chứng minh rằng r là căn nguyên thuỷ của pk với k ≥ 2. Đặt n = ordpkr. Ta có n | ϕ(pk) = pk−1(p− 1). Mặt khác, vì rn ≡ 1 (mod pk) nên rn ≡ 1 (mod p); suy ra p− 1 = ϕ(p) | n. Do n | pk−1(p−1) và (p−1) | n nên n = pt(p−1) với t nào đó, 0 ≤ t ≤ k−1. Trường hợp n = pt(p − 1) với 0 ≤ t ≤ k − 2 không thể xảy ra, vì nếu 0 ≤ t ≤ k − 2 thì rp k−2(p−1) = (rp t(p−1))k−2−t = (rn)k−2−t ≡ 1 (mod pk), và điều này vô lý với điều đã được chứng minh là rp k−2(p−1) ≡ 1 (mod pk). Vậy n = pk−1(p− 1), và điều này nói lên rằng ordpkr = ϕ(pk), hay cũng vậy: r là căn nguyên thuỷ của pk.
Định lý 5.12. Nếu a là số lẻ và k > 2 thì aϕ(2 k)/2 ≡ 1 (mod 2k). 5.3. CÁC SỐ CÓ CĂN NGUYÊN THUỶ 67 Chứng minh. Chúng ta chứng minh bằng phương pháp qui nạp theo k. Khi k = 3, đặt a = 2b + 1. Vì 2 | b(b + 1) nên aϕ(2 3)/2 = (2b + 1)2 = 4b(b + 1) + 1 ≡ 1 (mod 23). Giả sử đã có aϕ(2 k)/2 ≡ 1 (mod 2k), ta cần chứng minh rằng aϕ(2k+1)/2 ≡ 1 (mod 2k+1). Vì ϕ(2n) = 2n(1− 1/2) = 2n−1 nên từ giả thiết qui nạp ta có a2 k−2 ≡ 1 (mod 2k), suy ra a2 k−2 = 1 + d2k. Bình phương cả hai vế, ta được a2 k−1 = 1 + d2k+1 + d222k ≡ 1 (mod 2k+1), điều này kéo theo aϕ(2 k+1)/2 = a2 k−1 ≡ 1 (mod 2k).
Nhận xét: 1. Định lý trên nói lên rằng tất cả các lũy thừa dương của 2, trừ hai số 2 và 4, đều không có căn nguyên thuỷ. 2. Các số 2 và 4 đều có có căn nguyên thuỷ. Định lý 5.13. Nếu số nguyên dương n không là lũy thừa nguyên tố hoặc hai lần lũy thừa nguyên tố thì n không có căn nguyên thuỷ. Chứng minh. Giả sử n có căn nguyên thuỷ r, và có khai triển thành lũy thừa nguyên tố n = pt11 p t2 2 · · · ptmm . Gọi p là thừa số nguyên tố của n, do (r, pt) = 1 nên rϕ(p t) ≡ 1 (mod pt). Đặt U = [ϕ(pt11 ), ϕ(p t2 2 ), · · · , ϕ(ptmm )]. 68 5. CĂN NGUYÊN THỦY Vì ϕ(ptii ) | U nên theo định lý Trung hoa về phần dư ta có rU ≡ 1 (mod n). Điều này kéo theo ordnr = ϕ(n) ≤ U. Nhưng ϕ(n) = ϕ(pt11 )ϕ(p t2 2 ) · · ·ϕ(ptmm ), ta suy ra ϕ(pt11 )ϕ(p t2 2 ) · · ·ϕ(ptmm ) ≤ [ϕ(pt11 ), ϕ(pt22 ), · · · , ϕ(ptmm )]. Vậy ϕ(pt11 )ϕ(p t2 2 ) · · ·ϕ(ptmm ) = [ϕ(pt11 ), ϕ(pt22 ), · · · , ϕ(ptmm )]. Đẳng thức cuối cùng xảy ra chỉ khi các số nguyên ϕ(pt11 ), ϕ(p t2 2 ), · · · , ϕ(ptmm ) là đôi một nguyên tố cùng nhau. Với chú ý rằng ϕ(pt) = pt−1(p−1) ta thấy ϕ(pt) là số chẵn nếu p lẻ hoặc p = 2 và t ≥ 2. Như vậy, các số nguyên ϕ(pt11 ), ϕ(pt22 ), · · · , ϕ(ptmm ) là không đôi một nguyên tố cùng nhau, ngoại trừ trường hợp m = 1 hoặc m = 2 và n = 2pt mà p là số nguyên tố lẻ.
Định lý 5.14. Nếu p là số nguyên tố lẻ và t là số nguyên dương thì 2pt có căn nguyên thuỷ. Cụ thể hơn: nếu r là căn nguyên thuỷ modulo pt và r lẻ thì nó cũng là căn nguyên thuỷ modulo 2pt; ngược lại nếu r là căn nguyên thuỷ modulo pt và r chẵn thì r + pt là căn nguyên thuỷ modulo 2pt. Chứng minh. Gọi r là căn nguyên thuỷ modulo pt, ta có rϕ(p t) ≡ 1 (mod pt) và không có số mũ nguyên dương nào nhỏ hơn ϕ(pt) có tính chất này. Ta có ϕ(2pt) = ϕ(2)ϕ(pt) = ϕ(pt). Vậy rϕ(2p t) ≡ 1 (mod pt). Nếu r lẻ thì rϕ(2p t) ≡ 1 (mod 2). 5.4. CHỈ SỐ SỐ HỌC 69 Vì (2, pt) = 1, ta suy ra rϕ(2p t) ≡ 1 (mod 2pt). Dễ thấy không có số mũ nguyên dương nào nhỏ hơn ϕ(2pt) = ϕ(pt) có tính chất trên, do đó ord2ptr = ϕ(2p t). Nếu r chẵn thì r + pt là số lẻ. Do đó (r + pt)ϕ(2p t) ≡ 1 (mod 2). Mặt khác, vì r + pt ≡ r (mod pt) nên (r + pt)ϕ(2p t) ≡ 1 (mod pt). Suy ra (r + pt)ϕ(2p t) ≡ 1 (mod 2pt). Cũng thấy rằng không có số mũ nguyên dương nào nhỏ hơn ϕ(2pt) = ϕ(pt) có tính chất trên, do đó ord2pt(r + p t) = ϕ(2pt).
Từ các định lý 5.11, 5.12, 5.13 và 5.14, ta có định lý sau Định lý 5.15. Số nguyên dương n > 1 có căn nguyên thuỷ khi và chỉ khi n = 2, 4, pt, 2pt trong đó p là số nguyên tố lẻ và t là số nguyên dương. 5.4 Chỉ số số học Giả sử số nguyên dương cố định m có căn nguyên thuỷ r. Vìù các số nguyên r1, r2, · · · , rϕ(m) làm thành hệ thặng dư thu gọn modulo m, nên mỗi số nguyên a nguyên tố cùng nhau với m đều tồn tại duy nhất một số nguyên x, 1 ≤ x ≤ ϕ(m), mà rx ≡ a (mod m). Số nguyên x như vậy được gọi là chỉ số của a với cơ sở r modulo m, ký hiệu x = indra. 70 5. CĂN NGUYÊN THỦY Như vậy aindra ≡ a (mod m). Từ định nghĩa ta cũng thấy ngay rằng, đối với mọi số a, b nguyên tố cùng nhau với m, hệ thức a ≡ b (mod m) là tương đương với indra = indrb. Có một số tính chất của chỉ số tương tự như của logarithm, chỉ có điều thay dấu bằng bởi dấu đồng dư modulo ϕ(m). Định lý 5.16. Giả sử số nguyên dương m có căn nguyên thuỷ r, và a, b là các số nguyên tố cùng nhau với m. Thế thì: 1. indr1 ≡ 0 (mod ϕ(m)). 2. indr(ab) ≡ indra + indrb (mod ϕ(m)). 3. indra k ≡ k · indra (mod ϕ(m)) với k nguyên dương. Chứng minh. 1. rϕ(m) ≡ 1 (mod m), kéo theo indr1 = ϕ(m) ≡ 0 (mod ϕ(m)). 2. rindr(ab) ≡ ab ≡ rindra · rindrb ≡ rindra+indrb (mod m). Theo định lý 5.2 ta có indr(ab) ≡ indra + indrb (mod ϕ(m)). 3. rindra k ≡ ak ≡ (rindra)k ≡ rk·indra (mod m), kéo theo indra k ≡ k · indra (mod ϕ(m)).
Ví dụ 5.4.1. Chúng ta cần giải đồng dư 7x ≡ 6 (mod 17). Dễ dàng xác định được ϕ(17) = 16 và 3 là căn nguyên thuỷ modulo 17. Như vậy, bằng cách lấy chỉ số với cơ sở 3 modulo 17 cả hai vế, ta có ind37 x ≡ ind36 = 15 (mod 16). Vì ind37 x ≡ x · ind37 ≡ 11x (mod 16), nên 11x ≡ 15 (mod 16). Do 3 là nghịch đảo của 11 modulo 16, nên x ≡ 3 · 15 = 45 ≡ 13 (mod 16). 5.4. CHỈ SỐ SỐ HỌC 71  Giả sử m, k là các số nguyên dương và (a,m) = 1; ta sẽ nói a là thặng dư lũy thừa k của m nếuu đồng dư xk ≡ a (mod m) có nghiệm. Khi m có căn nguyên thuỷ, định lý sau đây sẽ cho một tiêu chuẩn để xem số nguyên a nguyên tố cùng nhau với m có là thặng dư lũy thừa k của m hay không. Định lý 5.17. Giả sử m có căn nguyên thuỷ, k là các số nguyên dương và (a,m) = 1. Thế thì: đồng dư xk ≡ a (mod m) có nghiệm khi và chỉ khi aϕ(m)/d ≡ 1 (mod m) trong đó d = (k, ϕ(m)). Hơn nữa, nếu đồng dư xk ≡ a (mod m) có nghiệm thì có đúng d nghiệm không đồng dư nhau modulo m. Chứng minh. Giả sử r là căn nguyên thuỷ của m. Đồng dư xk ≡ a (mod m) tương đương với k · indrx ≡ indra (mod ϕ(m)). Đặt d = (k, ϕ(m)), y = indrx, hay cũng vậy x ≡ ry (mod m). Ta đã biết đồng dư ky ≡ indra (mod ϕ(m)) không có nghiệm y khi d
indra, hay cũng vậy, không có x thỏa xk ≡ a (mod m). Trong trường hợp d | indra, đồng dư ky ≡ indra (mod ϕ(m)) có đúng d các nghiệm y không đồng dư nhau modulo ϕ(m), do đó có đúng d nghiệm x của xk ≡ a (mod m) không đồøng dư nhau modulo m. Mặt khác, ta có d | indra tương đương với (ϕ(m)/d)indra ≡ 0 (mod ϕ(m)), 72 5. CĂN NGUYÊN THỦY hay indra ϕ(m)/d ≡ indr1 (mod ϕ(m)). Đồng dư cuối cùng lại tương đương với aϕ(m)/d ≡ 1 (mod m).
Trong định lý trên, nếu m = p là số nguyên tố và (a, p) = 1 thì a là thặng dư lũy thừa k của p khi và chỉ khi a(p−1)/d ≡ 1 (mod p) trong đó d = (k, p− 1). Ví dụ 5.4.2. 1. Cần xác định xem 4 có là thặng dư lũy thừa năm của 11 hay không, nghĩa là xét xem đồng dư x5 ≡ 4 (mod 11) có nghiệm hay không. Ta có 410/(5,10) = 42 = 16 ≡ 1 (mod 11), vậy 4 không là thặng dư lũy thừa năm của 11. 2. Ta có 4 là thặng dư bình phương của 11 vì 410/(2,10) = 45 = 1024 ≡ 1 (mod 11), vậy 4 là thặng dư bình phương của 11.  BÀI TẬP CHƯƠNG V 5.4. CHỈ SỐ SỐ HỌC 73 1. Hãy tìm bậc của các số sau: ord52; ord103; ord1310; ord107; ord113; ord172; ord2110; ord259. 2. Hãy tìm tất cả các căn nguyên thuỷ của các số sau: 2; 3; 4; 5; 6; 7; 8; 9; 10. 3. Chứng minh rằng: nếu a¯ là nghịch đảo của a modulo m thì ordma = ordma¯. 4. Chứng minh rằng: nếu (a,m) = (b,m) = (ordma, ordmb) = 1 thì ordm(ab) = ordma·ordmb. 5. Chứng minh rằng nếu (a,m) = 1 và ordma = st thì ordma t = s. 6. Cho p là số nguyên tố lẻ. Chứng minh rằng r là căn nguyên thuỷ modulo p khi và chỉ khi r(p−1)/q ≡ 1 (mod p) đối với mọi ước nguyên tố q của p. 7. Chứng minh rằng nếu r¯ là nghịch đảo của r modulo m và r là căn nguyên thuỷ của m thì r¯ cũng là căn nguyên thuỷ của m. 8. Giả sử m = an− 1, với a, n là các số nguyên dương. Chứng minh rằng ordma = n và n | ϕ(m). 9. Cho p, q là các số nguyên tố lẻ khác nhau. Chứng minh rằng pq là số giả nguyên tố cơ sở 2 khi và chỉ khi ordq2 | (p− 1) , ordp2 | (q − 1). 10. Cho p, q là các số nguyên tố lẻ khác nhau. Chứng minh rằng pq là số giả nguyên tố cơ sở 2 khi và chỉ khi MpMq = (2 p− 1)(2q− 1) là số giả nguyên tố cơ sở 2. 11. Xác định số nghiệm không đồng dư nhau modulo 11 của các đa thức sau x2 + 2; x2 + 10; x4 + x2 + 1. 12. Xác định số nghiệm không đồng dư nhau modulo 13 của các đa thức sau x2 + 1; x2 + 3x + 2; x4 + x2 + x + 1. 74 5. CĂN NGUYÊN THỦY 13. Cho p là số nguyên tố lẻ. Chứng minh rằng đồng dư x2 ≡ −1 (mod p) có nghiệm khi và chỉ khi p ≡ 1 (mod 4). 14. Giả sử q và p = 2q+1 là các số nguyên tố, 1 < a < p−1. Chứng minh rằng p− a2 là căn căn nguyên thuỷ modulo p. 15. Các số nguyên nào trong các số từ 1 đến 100 có căn nguyên thuỷ. 16. Xác định tất cả các căn nguyên thuỷ modulo 22, modulo 25, modulo 38. 17. Chứng minh rằng m có căn nguyên thuỷ khi và chỉ khi đồng dư x2 ≡ 1 (mod m) chỉ có các nghiệm là x ≡ ±1 (mod m). 18. Giả sử n có căn nguyên thuỷ. Bằng cách sử dụng căn nguyên thuỷ, hãy chứng minh rằng tích của tất cả các số nguyên dương nhỏ hơn n và nguyên tố cùng nhau với n là đồng dư với −1 modulo n. (Khi n là số nguyên tố, ta nhận được định lý Wilson.) 19. Xác định tất cả các nghiệm của đồng dư: a) 3x5 ≡ 1 (mod 23); b) 3x14 ≡ 2 (mod 23); c) 3x ≡ 2 (mod 23); d) 13x ≡ 5 (mod 23). 20. Tìm các số nguyên a để đồng dư sau có nghiệm: a) ax4 ≡ 2 (mod 13); b) 8x7 ≡ a (mod 29). 21. Sử dụng chỉ số với cơ sở 2 modulo 13 để tìm nghiệm của 2x ≡ x (mod 13). 22. Xác định tất cả các nghiệm của đồng dư: xx ≡ x (mod 23). 23. Cho p là số nguyên tốû lẻ và r là căn nguyên thuỷ của p. Chứng minh rằng indr(p− 1) = (p− 1)/2. 24. Giả sử p là số nguyên tốû lẻ. Chứng minh rằng đồng dư x4 ≡ −1 (mod p) có nghiệm khi và chỉ khi p ≡ 1 (mod 8). 25. Chứng minh rằng có vô số số nguyên tố dạng 8k + 1. 6THẶNG DƯ BÌNH PHƯƠNG 6.1 Thặêng dư bình phương Giả sử m là số nguyên dương. Chúng ta nói rằng số nguyên a là thặng dư bình phương của m nếuu (a,m) = 1 và đồng dư x2 ≡ a (mod m) có nghiệm. Nếu đồng dư x2 ≡ a (mod m) không có nghiệm thì ta nói a là không thặng dư bình phương. Ví dụ 6.1.1. Để tìm các thặng dư bình phương của 11 chúng ta tính bình phương của tất cả các số 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Ta thấy 12 ≡ 102 ≡ 1 (11), 22 ≡ 92 ≡ 4 (11), 32 ≡ 82 ≡ 9 (11), 42 ≡ 72 ≡ 5 (11), 52 ≡ 62 ≡ 3 (11). Như vậy, các thặêng dư bình phương của 11 là: 1, 3, 4, 5, 9; các không thặng dư bình phương của 11 là: 2, 6, 7, 8, 10.  Chúng ta sẽ chỉ ra rằng nếu p là số nguyên tố lẻ thì số các thặng dư bình phương bằng số các không thặng dư bình phương của p trong dãy 1, 2, · · · , p− 1. Định lý 6.1. Nếu p là số nguyên tố lẻ và p
a thì đồng dư x2 ≡ a (mod p) hoặc không có nghiệm hoặc có đúng hai nghiệm không đồng dư nhau modulo p. Chứng minh. Giả sử đồng dư x2 ≡ a (mod p) có nghiệm x = x0. Ta thấy x = −x0 cũng là nghiệm, vì (−x0)2 = x20 ≡ a (mod p). Nhưng x0 ≡ −x0 (mod p); vì nếu trái lại thì p | x0 − (−x0) = 2x0, điều này kéo theo p | x0, và như vậy p | a. 75 76 6. THẶNG DƯ BÌNH PHƯƠNG Giả sử x = x1 là một nghiệm của đồng dư x 2 ≡ a (mod p). Thế thì x21 ≡ a ≡ x20 (mod p). Suy ra p | x21 − x20 = (x1 − x0)(x1 + x0); điều này kéo theo p | (x1 − x0) hoặc p | (x1 + x0), hay cũng vậy x1 ≡ x0 (mod p) hoặc x1 ≡ −x0 (mod p).
Định lý 6.2. Nếu p là số nguyên tố lẻ thì số các thặng dư bình phương bằng số các không thặng dư bình phương của p trong dãy 1, 2, · · · , p− 1. Chứng minh. Để xác định tất cả các các thặng dư bình phương của p trong dãy 1, 2, · · · , p − 1 chúng ta tính các thặng dư dương nhỏ nhất modulo p của bình phương của tất cả các số 1, 2, · · · , p− 1. Vì có cả thảy p− 1 các bình phương và mỗi đồng dư x2 ≡ a (mod p) hoặc không có nghiệm hoặc có đúng hai nghiệm, ta suy ra có đúng (p− 1)/2 các thặng dư bình phương, và do đó có p− 1− (p− 1)/2 = (p− 1)/2 các không thặng dư bình phương của p.
Giả sử p là øsố nguyên tố lẻ và p
a. Ta định nghĩa ký hiệu Legendre [a p ] := { 1 nếu a là thặng dư bình phương của p −1 nếu a là không thặng dư bình phương của p Ví dụ 6.1.2. Trong ví dụ trước đã chỉ ra [ 1 11 ] = [ 3 11 ] = [ 4 11 ] = [ 5 11 ] = [ 9 11 ] = 1, [ 2 11 ] = [ 6 11 ] = [ 7 11 ] = [ 8 11 ] = [10 11 ] = −1.  Sau đây chúng ta đưa ra tiêu chuẩn của số nguyên là thặng dư bình phương của số nguyên tố. Định lý 6.3. Tiêu chuẩn Euler. Nếu p là số nguyên tố lẻ và p
a thì [a p ] ≡ a(p−1)/2 (mod p). Chứng minh. Trường hợp [a p ] = 1. Khi đó, đồng dư x2 ≡ a (mod p) có nghiệm, giả sử là x = x0. Theo định lý Fermat, ta có a(p−1)/2 ≡ (x20)(p−1)/2 = xp−10 ≡ 1 (mod p). 6.1. THẶÊNG DƯ BÌNH PHƯƠNG 77 Trường hợp [a p ] = −1. Khi đó, đồng dư x2 ≡ a (mod p) không có nghiệm. Với mọi i, 1 ≤ i ≤ p − 1, đều có duy nhất j, 1 ≤ j ≤ p − 1 để ij ≡ a (mod p); nhưng do x2 ≡ a (mod p) vô nghiệm nên i = j. Như vậy ta có thể nhóm các số 1, 2, · · · , p−1 thành (p−1)/2 cặp có tích đồng dư với a modulo p. Vậy (p− 1)! ≡ a(p−1)/2 (mod p). Theo định lý Wilson, (p− 1)! ≡ −1 (mod p), nên ta suy ra a(p−1)/2 ≡ −1 (mod p).
Hệ quả 6.3.1. Nếu p là số nguyên tố lẻ thì [−1 p ] = { 1 nếu p ≡ 1 (mod 4) −1 nếu p ≡ −1 (mod 4) Định lý 6.4. Nếu p là số nguyên tố lẻ và p
a, p
b thì a) Nếu a ≡ b (mod p) thì [a p ] = [ b p ] . b) [ab p ] = [a p ][ b p ] . c) [a2 p ] = 1. Chứng minh. a) Nếu a ≡ b (mod p) thì x2 ≡ a (mod p) có nghiệm khi và chỉ khi x2 ≡ b (mod p) có nghiệm, hay [a p ] = [ b p ] . b) Theo tiêu chuẩn Euler, ta có[ab p ] ≡ (ab)(p−1)/2 = a(p−1)/2b(p−1)/2 ≡ [a p ][ b p ] (mod p). c) Do [a p ] = ±1, nên [a2 p ] = [a p ][a p ] = 1.
78 6. THẶNG DƯ BÌNH PHƯƠNG Định lý 6.5. Bổ đề Gauss. Nếu p là số nguyên tố lẻ và (a, p) = 1 và s là số các thặng dư dương nhỏ nhất lớn hơn p/2 của các số a, 2a, · · · , ((p−1)/2)a thì [a p ] = (−1)s. Chứng minh. Giả sử u1, u2, · · · , us là các thặng dư dương nhỏ nhất lớn hơn p/2 và v1, v2, · · · , vt là các thặng dư dương nhỏ nhất nhỏ hơn p/2 của các số a, 2a, · · · , ((p− 1)/2)a. Vì (ja, p) = 1 với mọi j, 1 ≤ j ≤ (p− 1)/2 nên các thặng dư dương nhỏ nhất thuộc 1, 2, · · · , p− 1. Chúng ta sẽ chỉ ra rằng tập {p−u1, p−u2, · · · , p−us, v1, v2, · · · , vt} chính là tập {1, 2, · · · , (p− 1)/2}. Vì (p− 1)/2 số p− u1, p− u2, · · · , p− us, v1, v2, · · · , vt đều nhỏ hơn (p − 1)/2 nên ta chỉ cần chứng tỏ rằng chúng không đồng dư nhau modulo p. Hiển nhiên p − ui ≡ p − uj (mod p) cũng như vi ≡ vj (mod p) nếu i = j; vì nếu không thì ta suy ra ma ≡ na (mod p), hay m ≡ n (mod p), và điều này không xảy ra với m = n mà 1 ≤ m,n ≤ (p− 1)/2. Tương tự, chúng ta cũng thấy p− ui ≡ vj (mod p); vì nếu không thì −m ≡ n (mod p), và điều này không thể xảy ra khi m = n và 1 ≤ m,n ≤ (p− 1)/2. Vậy thì (p− u1)(p− u2) · · · (p− us)v1v2 · · · vt = (p− 1 2 ) ! hay (−1)su1u2 · · · usv1v2 · · · vt = (p− 1 2 ) ! Do a(p−1)/2 (p− 1 2 ) ! = a · 2a · · · (p− 1 2 ) a ≡ u1u2 · · · usv1v2 · · · vt (mod p) Suy ra (−1)sa(p−1)/2(p− 1 2 ) ! ≡ (p− 1 2 ) ! (mod p). Vì (p, ((p− 1)/2)!) = 1 nên (−1)sa(p−1)/2 ≡ 1 (mod p). Suy ra [a p ] ≡ a(p−1)/2 ≡ (−1)s (mod p).
6.1. THẶÊNG DƯ BÌNH PHƯƠNG 79 Định lý 6.6. Nếu p là số nguyên tố lẻ thì[2 p ] = (−1)(p2−1)/8. Do đó, 2 là thặng dư bình phương của mọi số nguyên tố p ≡ ±1 (mod 8) và không là thặng dư bình phương của mọi số nguyên tố p ≡ ±3 (mod 8). Chứng minh. Theo bổ đề Gauss, gọi s là số các thặng dư dương nhỏ nhất lớn hơn p/2 của các số 1 · 2, 2 · 2, · · · , ((p− 1)/2) · 2, thì[2 p ] = (−1)s. Vì tất cả các số 1 · 2, 2 · 2, · · · , ((p − 1)/2) · 2