äy có đúng ϕ(ϕ(m)) các số u như vậy, hay m có đúng ϕ(ϕ(m)) cănnguyên thuỷ không đồng dư nhau modulo m.

Bạn đang xem: Giáo trình lý thuyết số

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 raord112 = ϕ(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ênthuỷ. Để đạt được điều này, trước hết chúng ta cần khảo sát vài tính chấtcủ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 clà 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 modulom cũng là nghiệm.62 5. CĂN NGUYÊN THỦYVí 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ứch(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) = anxn +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 modulop.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 pchí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) =anxn+an−1xn−1+· · ·+a1x+a0 có quá n nghiệm không đồng dư nhau modulop. Thế thì có các số nguyên c0, c1, · · · , cn không đồng dư nhau modulo p saocho 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ậyg(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Ố 63thiết qui nạp: g(x) có không quá n− 1 nghiệm không đồng dư nhau modulop.
Đị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−dsẽ có không quá p− 1− d nghiệm không đồng dư nhau modulo p; ta suy raxd − 1 ≡ 0 (mod p) có không ít hơn d nghiệm không đồng dư nhau modulop. 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ậcd 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ênp− 1 =∑d|p−1F (d).Mặt khác, theo định lý **refdl39 ta cóp− 1 =∑d|p−1ϕ(d).Vậy ∑d|p−1F (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 = dthìa, a2, · · · , ad64 5. CĂN NGUYÊN THỦYlà 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 đồngdư 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ằngp− 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ướchế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ănnguyê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+plà 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 rarn ≡ 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ếun = 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ươngtự như trên, để chứng minh s là căn nguyên thuỷ modulo p2 chúng ta chỉ cầnchứng tỏ rằng ordp2s = p− 1. Ta cósp−1 = (r + p)p−1 = rp−1 + (p− 1)rp−2p +< p− 12>rp−3p2 + · · ·+ pp−1và rp−1 ≡ 1 (mod p2) nênsp−1 ≡ rp−1 + (p− 1)prp−2 ≡ 1− prp−2 (mod p2).Vì (r, p) = 1 nên prp−2 ≡ 0 (mod p2), suy rasp−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. Dor6 = 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ănnguyê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ênthuỷ 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ênk ≥ 2 đều córpk−2(p−1) ≡ 1 (mod pk).Khi k = 2, ta có rpk−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órpk−2(p−1) ≡ 1 (mod pk).66 5. CĂN NGUYÊN THỦYVì (r, pk−1) = 1 nên theo định lý Euler, ta córpk−2(p−1) = rϕ(pk−1) ≡ 1 (mod pk−1),và điều này kéo theorpk−2(p−1) = 1 + dpk−1trong đó p
d vì rpk−2(p−1) ≡ 1 (mod pk). Lũy thừa p hai vế của đồng dưtrên, ta đượcrpk−1(p−1) = (1 + dpk−1)p = 1 + p(dpk−1) +< p2>(dpk−1)2 + · · ·+ (dpk−1)p.Suy rarpk−1(p−1) ≡ 1 + dpk (mod pk+1).Nhưng p
d nênrpk−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 rap− 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ếu0 ≤ t ≤ k − 2 thìrpk−2(p−1) = (rpt(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à rpk−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ũngvậ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ϕ(2k)/2 ≡ 1 (mod 2k).5.3. CÁC SỐ CÓ CĂN NGUYÊN THUỶ 67Chứng minh.

Xem thêm: Cách Luộc Trứng Chuẩn Thời Gian Luộc Trứng Cút, Luộc Trứng Cút Trong Bao Lâu

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ênaϕ(23)/2 = (2b + 1)2 = 4b(b + 1) + 1 ≡ 1 (mod 23).Giả sử đã có aϕ(2k)/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óa2k−2 ≡ 1 (mod 2k),suy raa2k−2= 1 + d2k.Bình phương cả hai vế, ta đượca2k−1= 1 + d2k+1 + d222k ≡ 1 (mod 2k+1),điều này kéo theoaϕ(2k+1)/2 = a2k−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ố 2và 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 hailầ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ừanguyên tốn = pt11 pt22 · · · ptmm .Gọi p là thừa số nguyên tố của n, do (r, pt) = 1 nênrϕ(pt) ≡ 1 (mod pt).ĐặtU = <ϕ(pt11 ), ϕ(pt22 ), · · · , ϕ(ptmm )>.68 5. CĂN NGUYÊN THỦYVì ϕ(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 theoordnr = ϕ(n) ≤ U.Nhưngϕ(n) = ϕ(pt11 )ϕ(pt22 ) · · ·ϕ(ptmm ),ta suy raϕ(pt11 )ϕ(pt22 ) · · ·ϕ(ptmm ) ≤ <ϕ(pt11 ), ϕ(pt22 ), · · · , ϕ(ptmm )>.Vậyϕ(pt11 )ϕ(pt22 ) · · ·ϕ(ptmm ) = <ϕ(pt11 ), ϕ(pt22 ), · · · , ϕ(ptmm )>.Đẳng thức cuối cùng xảy ra chỉ khi các số nguyên ϕ(pt11 ), ϕ(pt22 ), · · · , ϕ(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ặcp = 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ϕ(pt) ≡ 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. Tacó ϕ(2pt) = ϕ(2)ϕ(pt) = ϕ(pt). Vậyrϕ(2pt) ≡ 1 (mod pt).Nếu r lẻ thìrϕ(2pt) ≡ 1 (mod 2).5.4. CHỈ SỐ SỐ HỌC 69Vì (2, pt) = 1, ta suy rarϕ(2pt) ≡ 1 (mod 2pt).Dễ thấy không có số mũ nguyên dương nào nhỏ hơn ϕ(2pt) = ϕ(pt) có tínhchất trên, do đó ord2ptr = ϕ(2pt).Nếu r chẵn thì r + pt là số lẻ. Do đó(r + pt)ϕ(2pt) ≡ 1 (mod 2).Mặt khác, vì r + pt ≡ r (mod pt) nên(r + pt)ϕ(2pt) ≡ 1 (mod pt).Suy ra(r + pt)ϕ(2pt) ≡ 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 + pt) = ϕ(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ỉ khin = 2, 4, pt, 2pttrong đó p là số nguyên tố lẻ và t là số nguyên dương.5.4 Chỉ số số họcGiả sử số nguyên dương cố định m có căn nguyên thuỷ r. Vìù các số nguyênr1, 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ỦYNhư vậy aindra ≡ a (mod m). Từ định nghĩa ta cũng thấy ngay rằng, đốivớ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ềuthay 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. indrak ≡ 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.2ta cóindr(ab) ≡ indra + indrb (mod ϕ(m)).3. rindrak ≡ ak ≡ (rindra)k ≡ rk·indra (mod m), kéo theoindrak ≡ 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áchlấy chỉ số với cơ sở 3 modulo 17 cả hai vế, ta cóind37x ≡ ind36 = 15 (mod 16).Vìind37x ≡ x · ind37 ≡ 11x (mod 16),nên11x ≡ 15 (mod 16).Do 3 là nghịch đảo của 11 modulo 16, nênx ≡ 3 · 15 = 45 ≡ 13 (mod 16).5.4. CHỈ SỐ SỐ HỌC 71Giả 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ủam 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ỉ khiaϕ(m)/d ≡ 1 (mod m)trong đó d = (k, ϕ(m)). Hơn nữa, nếu đồng dư xk ≡ a (mod m) có nghiệmthì 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ớik · 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 khid
indra, hay cũng vậy, không có x thỏaxk ≡ a (mod m).Trong trường hợp d | indra, đồng dư ky ≡ indra (mod ϕ(m)) có đúng d cácnghiệm y không đồng dư nhau modulo ϕ(m), do đó có đúng d nghiệm x củaxk ≡ a (mod m)không đồøng dư nhau modulo m.Mặt khác, ta cód | indratương đương với(ϕ(m)/d)indra ≡ 0 (mod ϕ(m)),72 5. CĂN NGUYÊN THỦYhayindraϕ(m)/d ≡ indr1 (mod ϕ(m)).Đồng dư cuối cùng lại tương đương vớiaϕ(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ặngdư lũy thừa k của p khi và chỉ khia(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 11hay 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 V5.4. CHỈ SỐ SỐ HỌC 731. 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ì ordmat = 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ỉ khir(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ănnguyê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ằngordma = 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 = (2p− 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ứcsaux2 + 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ứcsaux2 + 1; x2 + 3x + 2; x4 + x2 + x + 1.74 5. CĂN NGUYÊN THỦY13. 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 giao_trinh_mon_ly_thuyet_so.pdf