Lời cảm ơn
2
Mở đầu 3
1 Kiến thức chuẩn bị 5
1.1 Lý thuyết chia hết trong tập số nguyên 5
1.2 Dồng dư thức và phương trình đồng dư 9
2 ứng dụng của cấp và chỉ số của số nguyên 16
2.1 Khái niệm, ví dll. tính chất cơ bản về cấp cho số nguyên
theo modulo 16
2.2 Khái niệm và tính chất của căn nguyên thủy modulo . 21
2.3 Cấp cho số nguyên theo modulo và ứng dụng để kiểm tra
tính nguyên tố 24
2.4 Cấp cho số nguyên theo modulo và ứng dụng nhận diện các
căn nguyên thủy của số nguyên tố 27
2.5 Cấp cho số nguyên theo modulo và áp dụng nhận diện số
nguyên có căn nguyên thủy 34
2.6 Chỉ số cho số nguyên theo modulo và ứng dụng 43
Kết luận 48
Tài liệu tham khảo 49
51 trang |
Chia sẻ: honganh20 | Ngày: 28/02/2022 | Lượt xem: 328 | Lượt tải: 2
Bạn đang xem trước 20 trang tài liệu Luận văn Ứng dụng của cấp và chỉ số cho số nguyên theo modulo, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
1 1 1 1 1
2 4 8 7 5 1
4 7 1 4 7 1
5 7 8 4 2 1
7 4 1 7 4 1
8 1 8 1 8 1
Bảng 2.1: Giỏ trị thặng dư của a theo modulo 9
Khỏi niệm cấp một số theo modulo m đó được nhà toỏn học Carl
Friedrich Gauss (1777 − 1855) xuất bản vào năm 1801 trong cuốn sỏch
“Disquisitiones Arithmeticae”.
Định nghĩa 2.1.1. Cho m, a là cỏc số nguyờn dương sao cho (a,m) = 1.
Khi đú số mũ dương e nhỏ nhất sao cho ae ≡ 1 (mod m) được gọi là
cấp của a theo modulo m, kớ hiệu bởi ordm a (hoặc ord a, nếu việc bỏ qua
modulo m mà khụng dẫn đến nhầm lẫn).
Theo định nghĩa trờn và nhỡn vào Bảng 2.1 ta cú ord9 1 = 1, ord9 2 =
ord9 5 = 6, ord9 4 = ord9 7 = 3 và ord9 8 = 2.
Vớ dụ 2.1.2. Tỡm ord13 5 và ord13 7.
Giải. Ta cú (5, 13) = 1 = (7, 13). Ta tỡm số mũ e nhỏ nhất của 5 và 7 theo
modulo 13 sao cho 5e ≡ 1 (mod 13) và 7e ≡ 1 (mod 13). Ta cú
52 ≡ −1 (mod 13), 53 ≡ −5 (mod 13), 54 ≡ 1 (mod 13)
17
Do vậy, ord135 = 4. Tương tự ta tớnh được
72 ≡ −3 (mod 13), 73 ≡ 5 (mod 13), 74 ≡ −4 (mod 13)
75 ≡ −2 (mod 13), 76 ≡ −1 (mod 13), 77 ≡ 6 (mod 13)
78 ≡ 3 (mod 13), 79 ≡ −5 (mod 13), 710 ≡ 4 (mod 13)
711 ≡ 2 (mod 13), 712 ≡ 1 (mod 13).
Do vậy, ord137 = 12.
Vậy, để tớnh ordm a, chỳng ta cần tớnh a
k theo modulo m với mọi số
nguyờn dương k ≤ ϕ(m). Việc tớnh toỏn này tốn khỏ nhiều thời gian nếu
như cỏc số nguyờn dương đó cho cú giỏ trị lớn. Định lý dưới đõy giỳp chỳng
ta loại trừ khỏ nhiều ứng cử viờn để tớnh ordma.
Định lý 2.1.3. Cho a,m là số nguyờn dương sao cho (a,m) = 1 và
ordm a = e. Khi đú a
n ≡ 1 (mod m) khi và chỉ khi e | n.
Chứng minh. Giả sử an ≡ 1 (mod m) nhưng e - n, vậy ta cú n = qe + r
trong đú 0 ≤ r < e. Khi đú
an =aqe+r = (ae)q.ar
≡1q.ar ≡ ar (mod m).
Nhưng theo giả thiết an ≡ 1 (mod m) nờn ar ≡ 1 (mod m) trong đú
0 ≤ r < e. Vỡ e là số mũ bộ nhất thỏa món ae ≡ 1 (mod m) và r < e suy
ra r = 0. Do đú, n = qe và suy ra e | n. Để chứng minh chiều ngược lại,
giả sử e | n. Khi đú n = be với b là số nguyờn dương. Do đú
an =abe = (ae)b
≡1b ≡ 1 (mod m).
Hệ quả của Định lý 2.1.3 cung cấp cho ta một cụng cụ hiệu quả để tớnh
ordm a.
Hệ quả 2.1.4. Cho a,m là cỏc số nguyờn dương sao cho (a,m) = 1. Khi
đú ordm a | ϕ(m). Trong trường hợp đặc biệt, nếu p là một số nguyờn tố
và p - a thỡ ordp a | (p− 1).
18
Chứng minh. Theo định lý Euler, aϕ(m) ≡ 1 (mod m). Do đú theo Định
lý 2.1.3 ta cú ordm a | ϕ(m). Đặc biệt, khi p là số nguyờn tố, ta cú ϕ(p) =
p− 1, nờn ordp a | (p− 1).
Hệ quả 2.1.4 đó giới hạn đỏng kể số ứng viờn cho vị trớ số ordm a, cụ thể
nú giới hạn vào tập cỏc ước số của ϕ(m). Do đú, để tớnh ordm a, ta khụng
cần phải tỡm tất cả cỏc lũy thừa k của a trong phạm vi k ≤ ϕ(m), mà ta
chỉ cần quan tõm đến cỏc số mũ dương d của a sao cho d|ϕ(m). Cỏc vớ dụ
sau đõy sẽ minh họa cho điều này.
Vớ dụ 2.1.5. Hóy tỡm ord21 5.
Chứng minh. Ta cú ϕ(21) = ϕ(3.7) = ϕ(3)ϕ(7) = 2.6 = 12. Cỏc ước số d
của ϕ(21) = 12 là 1, 2, 3, 4, 6 và 12, do đú cỏc giỏ trị ấy cũng là cỏc ứng
viờn tiềm năng của ord21 5. Để tỡm nú, ta tớnh toỏn 5
d modulo 21 ứng với
mỗi d lần lượt là 1, 2, 3, 4, 6, 12 cho đến khi đạt được lũy thừa đú bằng 1:
51 ≡ 5 (mod 21), 52 ≡ 4 (mod 21), 53 ≡ −1 (mod 21)
54 ≡ −5 (mod 21), 56 ≡ 1 (mod 21).
Vậy ord21 5 = 6.
Giả sử ai ≡ aj (mod m). Khi đú cú một cõu hỏi hợp lý được đặt ra là:
Mối quan hệ giữa i và j là gỡ? Cõu trả lời được trỡnh bày trong hệ quả
dưới đõy.
Hệ quả 2.1.6. Cho ordm a = e. Khi đú a
i ≡ aj (mod m) khi và chỉ khi
i ≡ j (mod e).
Chứng minh. Giả sử ai ≡ aj (mod m) với i ≥ j. Vỡ (a,m) = 1, nờn
(aj,m) = 1. Do đú phương trỡnh đồng dư ajx ≡ 1 (mod m) cú nghiệm,
tức là tồn tại x0 (mod m) để a
jx0 ≡ 1 (mod m). Vỡ thế aix0 ≡ ajx0 ≡ 1
(mod m). Do đú
aix0 ≡ 1 (mod m)ajx0 ≡ 1 (mod m).
Suy ra ajx0(a
i−j − 1) ≡ 0 (mod m). Tức là m|ajx0(ai−j − 1). Từ đú với
lưu ý (aj,m) = 1 = (x0,m), ta suy ra được m|(ai−j − 1). Do đú ai−j ≡ 1
(mod m). Vỡ thế ỏp dụng Định lý 2.1.3 ta suy ra e|(i − j), tức là i ≡ j
(mod e).
19
Ngược lại, cho i ≡ j (mod e) với i ≥ j. Khi đú tồn tại k ≥ 0 sao cho
i = j + ke. Do đú
ai = aj+ke = aj.(ae)k
≡ aj.1k (mod m)
≡ aj (mod m).
Đú là điều phải chứng minh.
Vớ dụ sau minh họa cho kết quả này.
Vớ dụ 2.1.7. Xột lại vớ dụ 2.1.5, ta cú ord21 5 = 6. Ta cú thể kiểm
chứng rằng 514 ≡ 52 (mod 21) trong đú 14 ≡ 2 (mod 6). Nhưng 517 6≡ 53
(mod 21) bởi vỡ 17 6≡ 3 (mod 6).
Giả sử ta đó biết ordm a = e. Khi đú cú cõu hỏi đặt ra là “liệu cú quan
hệ nào giữa ordm(a
k) với e hay khụng?” (trong đú k > 0). Định lý dưới
đõy sẽ cho ta biết về mối quan hệ giữa hai số này.
Định lý 2.1.8. Cho ordm a = e và 0 < k ∈ Z. Khi đú ordm(ak) = e
(e, k)
.
Chứng minh. Giả sử ordm(a
k) = r và đặt d = (e, k). Khi đú cú cỏc số
nguyờn dương s, t sao cho e = sd, k = td và (s, t) = 1. Vỡ
(ak)s = (atd)s = (asd)t = (ae)t ≡ 1t ≡ 1 (mod m),
nờn theo Định lý 2.1.3 ta suy ra r | s.
Vỡ ordm(a
k) = r nờn (ak)r = akr ≡ 1 (mod m); nờn từ Định lý 2.1.3
ta cú e | kr. Vỡ vậy, e = sd | tdr = kr, suy ra s | tr. Nhưng lưu ý rằng
(s, t) = 1, do vậy s | r.
Do vậy, s | r và r | s nờn s = r, nghĩa là
ordm(a
k) = r = s =
e
d
=
e
(e, k)
.
Vớ dụ 2.1.9. Trong Vớ dụ 2.1.5, ta thấy rằng ord21 5 = 6. Do đú, theo
Định lý 2.1.8, ta cú ord21(5
9) =
6
(6, 9)
=
6
3
= 2. Để kiểm chứng lại kết
quả này, ta tớnh toỏn
52 ≡ 4 (mod 21), 54 ≡ 16 (mod 21), 58 ≡ 4 (mod 21)
59 ≡ −1 (mod 21), 518 ≡ 1 (mod 21).
20
Vỡ vậy ord21(5
9) = 2.
Hệ quả 2.1.10. Cho ordm a = e và k là số nguyờn dương. Khi đú ordm(a
k) =
e khi và chỉ khi (e, k) = 1.
Chứng minh. Theo Định lý 2.1.8, ta cú ordm(a
k) =
e
(e, k)
. Do đú
e
(e, k)
= e
khi và chỉ khi (e, k) = 1.
Vớ dụ 2.1.11. Theo vớ dụ 2.1.5 ta cú ord21 5 = 6. Suy ra ord21(5
11) = 6
vỡ (6, 11) = 1. Ta cú thể kiểm chứng trực tiếp kết quả này.
2.2 Khỏi niệm và tớnh chất của căn nguyờn thủy modulo
Ta nhắc lại, cho a,m là cỏc số nguyờn dương sao cho (a,m) = 1. Khi
đú theo Hệ quả 2.1.4, ta cú ordm a | ϕ(m); vỡ vậy cấp lớn nhất của số
nguyờn a theo modulo m là ϕ(m). Cỏc trường hợp thặng dư dương nhỏ
nhất như thế là tồn tại, chẳng hạn như ở Vớ dụ 2.1.2 ta đó tỡm được
ord13 7 = 12 = ϕ(13).
Định nghĩa 2.2.1. Cho α là số nguyờn dương sao cho (α,m) = 1. Khi
đú ta núi α là căn nguyờn thủy modulo m nếu ordm α = ϕ(m).
Vớ dụ sau minh họa cho định nghĩa này.
Vớ dụ 2.2.2. Theo Bảng 2.1 ta cú ord9 2 = ord9 5 = 6 = ϕ(9), vỡ vậy cả
2 và 5 đều là cỏc căn nguyờn thủy modulo 9.
Trong vớ dụ 2.1.2 chỳng ta cú ord137 = 12 = ϕ(13), nờn 7 là căn nguyờn
thủy modulo 13.
Vớ dụ 2.2.2 cú thể gõy cho người đọc ấn tượng rằng mọi số nguyờn dương
bất kỳ đều cú căn nguyờn thủy. Tuy nhiờn, điều này khụng chắc đỳng. Vớ
dụ như khụng cú căn nguyờn thủy modulo 12. Bởi vỡ ϕ(12) = 4, cỏc số
nguyờn dương nhỏ hơn 12 và nguyờn tố cựng nhau với 12 lần lượt là 1, 5, 7
và 11. Nhưng ord12 1 = 1; ord12 5 = ord12 7 = ord12 11 = 2. Như vậy ta
khụng cú căn nguyờn thủy modulo 12.
Tiếp theo ta sẽ tập trung nghiờn cứu căn nguyờn thủy modulo cỏc số
nguyờn tố Fermat fn, với n ≥ 0. Rừ ràng, số 2 là một căn nguyờn thủy
modulo số Fermat f0 = 3 và f1 = 5 (vỡ 2
1 ≡ 2 (mod f0), 22 ≡ 1 (mod f0);
21 ≡ 2 (mod f1), 22 ≡ 4 (mod f1), 23 ≡ 3 (mod f1), 24 ≡ 1 (mod f1)).
21
Vớ dụ sau đõy chỉ ra được rằng chỉ cú duy nhất cỏc số nguyờn tố Fermat
f0 và f1 là nhận 2 là một căn nguyờn thủy.
Vớ dụ 2.2.3. Chứng minh rằng 2 khụng là căn nguyờn thủy modulo bất
kỳ số nguyờn tố Fermat fn = 2
2n + 1 nào với n ≥ 2.
Giải. Ta cú
22
n
+ 1 = fn ≡ 0 (mod fn)
vỡ vậy
22
n ≡ −1 (mod fn).
Khi đú
22
n+1
= (22
n
)2 ≡ 1 (mod fn).
Vỡ thế theo Định lý 2.1.3, ta suy ra ordfn 2 | 2n+1. Do đú ordfn 2 ≤ 2n+1.
Mặt khỏc bằng quy nạp ta cú thể chứng minh được rằng n + 1 < 2n với
mọi n ≥ 2 (vỡ rừ ràng n = 2 thỏa món; ta cú (n + 1) + 1 < 2n + 1 <=
2n + 2n = 2n+1). Vỡ thế
ordfn 2 ≤ 2n+1 < 22
n
= fn − 1 = ϕ(fn).
Do đú, số 2 khụng thể là một căn nguyờn thủy modulo số nguyờn tố Fermat
fn = 2
2n + 1, với n ≥ 2.
Định lý dưới đõy đúng vai trũ quan trọng trong bài toỏn xỏc định xem
số nguyờn dương nào thỡ cú căn nguyờn thủy. Kết quả của định lý này gúp
phần nhận diện cỏc số cú căn nguyờn thủy.
Định lý 2.2.4. Nếu α là một căn nguyờn thủy modulo m, thỡ cỏc thặng
dư dương nhỏ nhất của α, α2, . . . , αϕ(m) modulo m tạo thành một hoỏn vị
của ϕ(m) cỏc số nguyờn dương ≤ m và nguyờn tố cựng nhau với m.
Chứng minh. Để chứng minh định lý, ta chỉ cần chứng minh hai điều là:
α, α2, . . . , αϕ(m) là nguyờn tố cựng nhau với m; và khụng cú hai số nào
trong số chỳng là đồng dư với nhau theo modulo m. Ta sẽ thực hiện điều
này sau đõy.
Vỡ (α,m) = 1, nờn (αk,m) = 1 với mọi số nguyờn dương k. Đặc biệt ta
suy ra cỏc số α, α2, . . . , αϕ(m) đều nguyờn tố cựng nhau với m.
Để chứng minh khụng cú hai số nào trong ϕ(m) lũy thừa của α cựng
đồng dư modulo m, ta giả sử tồn tại 1 ≤ i, j ≤ ϕ(m) sao cho αi = αj
22
(mod m), khụng mất tổng quỏt ta cú thể giả thiết i ≤ j. Khi đú theo Hệ
quả 2.1.6, thỡ i ≡ j (mod ϕ(m)). Nhưng i, j ≤ ϕ(m), nờn suy ra i = j.
Vỡ thế khụng cú cặp số phõn biệt nào trong cỏc số α, α2, . . . , αϕ(m) cựng
đồng dư nhau theo modulo m.
Do vậy cỏc thặng dư dương nhỏ nhất của α, α2, . . . , αϕ(m) modulo m là
một bộ sắp xếp lại của ϕ(m) cỏc số nguyờn dương nhỏ hơn hoặc bằng m
và nguyờn tố cựng m.
Vớ dụ sau đõy sẽ minh họa cho định lý này.
Vớ dụ 2.2.5. Cho m = 18, khi đú cú ϕ(18) = 6 cỏc số nguyờn dương ≤ 18
và nguyờn tố cựng nhau với 18; chỳng lần lượt là 1, 5, 7, 11, 13 và 17. Ta
cú thể chứng minh được rằng α = 5 là một căn nguyờn thủy modulo 18.
Thật vậy, ta tớnh ϕ(18) = 6 cỏc lũy thừa của 5 là 5, 52, 53, 54, 55 và 56;
và lấy modulo 18 lần lượt cỏc số đú ta được cỏc số: 5, 7, 17, 13, 11 và 1:
51 ≡ 5 (mod 18), 52 ≡ 7 (mod 18), 53 ≡ 17 (mod 18)
54 ≡ 13 (mod 18), 55 ≡ 11 (mod 18), 56 ≡ 1 (mod 18).
Rừ ràng chỳng là một hoỏn vị của cỏc số 1, 5, 7, 11, 13 và 17.
Định lý 2.2.4 cú một hệ quả rất hữu ớch. Nú cho ta biết chớnh xỏc số cỏc
căn nguyờn thủy modulo m, nếu chỳng tồn tại.
Hệ quả 2.2.6. Nếu m cú một căn nguyờn thủy, thỡ nú cú ϕ(ϕ(m)) cỏc
căn nguyờn thủy modulo m. Đặc biệt, nếu m = p là số nguyờn tố thỡ nú
cú ϕ(p− 1) căn nguyờn thủy modulo p.
Chứng minh. Giả sử α là một căn nguyờn thủy modulo m. Khi đú theo
Định lý 2.2.4, cỏc thặng dư dương nhỏ nhất của α, α2, . . . , αϕ(m) theo
modulo m là cỏc số phõn biệt và nguyờn tố cựng nhau với m. Theo Hệ quả
2.1.10, ta cú ordm(α
k) = ϕ(m) khi và chỉ khi (k, ϕ(m)) = 1, nghĩa là αk
là một căn nguyờn thủy modulo m khi và chỉ khi (k, ϕ(m)) = 1. Nhưng
ta biết cú ϕ(ϕ(m)) cỏc số nguyờn dương ≤ ϕ(m) và nguyờn tố cựng nhau
với ϕ(m). Do đú m cú ϕ(ϕ(m)) cỏc căn nguyờn thủy.
Trường hợp đặc biệt, nếu m = p là số nguyờn tố thỡ ϕ(p) = p − 1. Do
đú ta cú ϕ(p− 1) căn nguyờn thủy modulo p.
Phần chứng minh của định lý trờn đó đưa ra một phương phỏp để tỡm tất
cả ϕ(ϕ(m)) cỏc căn nguyờn thủy modulo m xuất phỏt từ một căn nguyờn
23
thủy α modulo m cho trước. Chỳng chớnh xỏc là αk với (k, ϕ(m)) = 1,
như được minh họa ở vớ dụ dưới đõy.
Vớ dụ 2.2.7. Cho biết số 5 là một căn nguyờn thủy modulo 54, hóy tỡm
cỏc căn nguyờn thủy cũn lại.
Giải. Theo Hệ quả 2.2.6, số 54 cú ϕ(ϕ(54)) = ϕ(18) = 6 cỏc căn nguyờn
thủy. Chỳng được cho dưới dạng 5k trong đú (k, 18) = 1. Cỏc số nguyờn
dương k ≤ 18 và nguyờn tố cựng nhau với 18 lần lượt là 1, 5, 7, 11, 13, 17;
do đú ta tớnh cỏc lũy thừa
51 ≡ 5 (mod 54), 55 ≡ 47 (mod 54), 57 ≡ 41 (mod 54)
511 ≡ 29 (mod 54), 513 ≡ 23 (mod 54), 517 ≡ 11 (mod 54).
Do vậy cỏc căn nguyờn thủy modulo 18 cũn lại lần lượt là 11, 23, 29, 41 và
47.
Vớ dụ tiếp theo là ỏp dụng trường hợp đặc biệt của Hệ quả 2.2.6.
Vớ dụ 2.2.8. Tỡm tất cả cỏc căn nguyờn thủy modulo 19.
Giải. Ta thấy số 2 là một căn nguyờn thủy modulo 19. Do đú theo Hệ
quả 2.2.6, ta thấy số nguyờn tố 19 cú ϕ(18) = 6 căn nguyờn thủy 2k, với
(k, 18) = 1 và 0 < k ≤ 18. Vỡ vậy cỏc số k lần lượt là 1, 5, 7, 11, 13 và
17. Ta tớnh 2k modulo 19 ứng với cỏc số k nờu trờn, thu được cỏc giỏ trị
thặng dư modulo 19 theo tứ tự tăng dần là 2, 3, 10, 13, 14 và 15. Như vậy
cỏc căn nguyờn thủy modulo 19 lần lượt là 2, 3, 10, 13, 14 và 15.
2.3 Cấp cho số nguyờn theo modulo và ứng dụng để kiểm tra
tớnh nguyờn tố
Ta cú thể sử dụng khỏi niệm cấp cho số nguyờn theo modulo để phỏt
triển cỏc tiờu chuẩn kiểm tra số nguyờn tố. Lucas, năm 1876, đó cung cấp
một tiờu chuẩn như vậy; nú dựa trờn một thực tế là “một số nguyờn dương
n là số nguyờn tố khi và chỉ khi ϕ(n) = n−1” (Thật vậy, nếu n nguyờn tố
thỡ rừ ràng ϕ(n) = n− 1; ngược lại, nếu ϕ(n) = n− 1 thỡ n > 1 và mọi số
nguyờn dương bộ hơn n đều nguyờn tố cựng nhau với n; suy ra n khụng
chia hết cho bất kỡ số nguyờn dương nào khỏc 1 và nhỏ hơn n. Chứng tỏ
n là số nguyờn tố).
24
Định lý 2.3.1 (Định lý Lucas). Cho n là một số nguyờn dương. Nếu
cú một số nguyờn dương x sao cho xn−1 ≡ 1 (mod n) và x(n−1)/q 6≡ 1
(mod n) với mọi thừa số nguyờn tố q của (n− 1) thỡ n là nguyờn tố.
Chứng minh. Giả sử ordn x = e. Vỡ x
n−1 ≡ 1 (mod n) nờn theo Định lý
2.1.3 ta cú e | (n−1). Ta cần chứng minh rằng e = n−1. Giả sử ngược lại
rằng e 6= n− 1. Khi đú vỡ e | n− 1 nờn tồn tại k > 1 sao cho n− 1 = ke.
Gọi q là một ước số nguyờn tố của k. Khi đú
x(n−1)/q = xke/q = (xe)k/q
≡ 1 (mod n),
điều này mõu thuẫn với giả thiết x(n−1)/q 6≡ 1 (mod n). Do đú e = n− 1,
tức là ordn x = n − 1. Ta lại cú ϕ(n) ≤ n − 1 với mọi n ≥ 2. Do đú
n− 1 = ordn x | ϕ(n) ≤ n− 1, điều này dẫn đến n− 1 = ϕ(n). Vỡ vậy n
là số nguyờn tố.
Vớ dụ 2.3.2. Sử dụng Định lý Lucas (Định lý 2.3.1), hóy chứng minh rằng
n = 1117 là số nguyờn tố.
Giải. Ta chọn x = 2 để kiểm tra cỏc điều kiện xem n = 1117 cú là nguyờn
tố khụng.
Đầu tiờn, chỳ ý rằng
21116 = (2100)11 ã 216
≡ 29311 ã 750 ≡ 70 ã 750 ≡ 1 (mod 1117).
Vỡ 1116 = 22 ã 32 ã 31, nờn cỏc thừa số nguyờn tố của n− 1 = 1116 lần lượt
là 2, 3 và 31. Với q = 2, ta cú
2(n−1)/q = 2558 = (250)11 ã 28
≡ 6911 ã 256 ≡ 1069 ã 256 ≡ −1 (mod 1117);
Với q = 3, ta cú
2(n−1)/q = 2372 = (250)7 ã 222
≡ 697 ã 1086 ≡ 112 ã 1086 ≡ 996 (mod 1117);
Với q = 31,
2(n−1)/q = 236 = (210)3 ã 26
≡ (−93)3 ã 64 ≡ 1000 ã 64 ≡ 331 (mod 1117).
25
Do vậy 21116/q 6≡ 1 (mod 1117) với mọi thừa số nguyờn tố q của n− 1 =
1116. Do đú theo Định lý Lucas (Định lý 2.3.1), ta suy ra số 1117 là số
nguyờn tố.
Như vớ dụ trờn đó chỉ ra, một mỏy tớnh kĩ thuật thụng dụng, chẳng hạn
như loại FX570, kết hợp phộp toỏn mod lấy phần dư, người ta cú thể đẩy
nhanh tốc độ kiểm tra tớnh nguyờn tố của một số nào đú.
Ta cú thể hiệu chỉnh Định lý Lucas để thu được tiờu chuẩn kiểm tra
tớnh nguyờn tố hiệu quả hơn như sau.
Hệ quả 2.3.3. Cho n là một số nguyờn dương lẻ. Nếu cú một số nguyờn
dương x sao cho x(n−1)/2 ≡ −1 (mod n) và x(n−1)/q 6≡ 1 (mod n) với mọi
thừa số nguyờn tố lẻ q của (n− 1), thỡ n là số nguyờn tố.
Chứng minh. Vỡ x(n−1)/2 ≡ −1 (mod n), nờn xn−1 = (x(n−1)/2)2 ≡ 1
(mod n). Hơn nữa, x(n−1)/q 6≡ 1 (mod n) khi q = 2 hoặc q là thừa số
nguyờn tố lẻ bất kỳ nào của n − 1. Do vậy, cả hai điều kiện của Định lý
Lucas đều được thỏa món. Vỡ vậy n là số nguyờn tố.
Vớ dụ sau minh họa cho tiờu chuẩn cải thiện này.
Vớ dụ 2.3.4. Sử dụng Hệ quả 2.3.3, hóy chứng minh n = 1213 là một số
nguyờn tố.
Chứng minh. Ta chọn x = 5. Vỡ n− 1 = 1212 = 22 ã 3 ã 101, nờn cỏc thừa
số nguyờn tố lẻ của n− 1 là 3 và 101.
Ta cú
5(n−1)/2 = 5606 = (5100)6 ã 56
≡ (−252)6 ã 1069 ≡ 497 ã 1069 ≡ −1 (mod 1213).
Với q = 3, ta cú
5(n−1)/q = 5404 = (5100)4 ã 54
≡ (−252)4 ã 625 ≡ 21 ã 625 ≡ 995 (mod 1213).
Với q = 101, ta cú
5(n−1)/q = 512 = 510 ã 52
≡ (−238) ã 25 ≡ 115 (mod 1213).
Do vậy, trong cả hai trường hợp q = 3, q = 101, ta đều thấy 5(n−1)/q 6≡ 1
(mod 1213), vỡ thế suy ra 1213 là một số nguyờn tố.
26
2.4 Cấp cho số nguyờn theo modulo và ứng dụng nhận diện
cỏc căn nguyờn thủy của số nguyờn tố
Trong Hệ quả 2.2.6 ta đó tỡm ra rằng nếu một số nguyờn dương m cú
một căn nguyờn thủy, thỡ nú cú ϕ(ϕ(m)) căn nguyờn thủy. Tuy nhiờn Hệ
quả 2.2.6 khụng đảm bảo mọi số nguyờn dương m đều cú căn nguyờn thủy.
Chẳng hạn, số 8 khụng cú căn nguyờn thủy. Thật võy, vỡ ϕ(8) = 4. Với mỗi
số nguyờn dương a là một căn nguyờn thủy modulo 8, thỡ (a, 8) = 1, suy
ra a là số lẻ. Vỡ vậy a ≡ ±1 hoặc ±3 (mod 8). Khi đú a2 ≡ 1 (mod 8).
Do đú ord8 a ≤ 2. Từ đú suy ra hệ quả là ord8 a 6= ϕ(8), điều này mõu
thuẫn; 8 khụng cú căn nguyờn thủy.
Cú cõu hỏi đó được đặt ra là: Những số nguyờn dương m nào thỡ cú căn
nguyờn thủy? Đầu tiờn ta cần chỉ ra rằng mọi số nguyờn tố p đều cú một
căn nguyờn thủy. Và để làm điều này ta cần sử dụng một số kết quả từ
phương trỡnh đồng dư.
Nhắc lại rằng với f(x) ∈ Z[x]. Nếu số nguyờn α nghiệm đỳng phương
trỡnh đồng dư f(x) ≡ 0 (mod m) thỡ mọi số nguyờn β thỏa món β ≡ α
(mod m) cũng nghiệm đỳng phương trỡnh f(x) ≡ 0 (mod m).
Vớ dụ 2.4.1. Xột phương trỡnh đồng dư
f(x) = x2 − x+ 1 ≡ 0 (mod 13). (2.1)
Phương trỡnh này cú hai nghiệm là 4 (mod 13) và 10 (mod 13), bởi vỡ
f(4) ≡ 16− 4 + 1 ≡ 0 (mod 13)
f(10) ≡ 100− 10 + 1 ≡ 0 (mod 13).
Tuy nhiờn phương trỡnh
g(x) = 2x2 + 3x+ 4 ≡ 0 (mod 5) (2.2)
lại khụng cú nghiệm (Thật vậy, ta cú thay lần lượt cỏc giỏ trị trong một
hệ thặng dư đầy đủ modulo 5 (chẳng hạn cỏc giỏ trị 0, 1, 2, 3 và 4) vào
27
phương trỡnh (2.2) ta nhận được
g(0) ≡ 4 6≡ 0 (mod 5)
g(1) ≡ 2 + 3 + 4 = 9 6≡ 0 (mod 5)
g(2) ≡ 8 + 6 + 4 = 18 6≡ 0 (mod 5)
g(3) ≡ 31 6≡ 0 (mod 5)
g(4) ≡ 48 6≡ 0 (mod 5).
Rừ ràng khụng cú giỏ trị nào nghiệm đỳng phương trỡnh g(x) ≡ 0 (mod 5)).
Định lý sau đõy của Lagrange núi về số nghiệm của một phương trỡnh
đồng dư f(x) ≡ 0 (mod p) (với p là số nguyờn tố), nú đúng vai trũ quan
trọng trong việc chứng minh sự tồn tại của cỏc căn nguyờn thủy cho cỏc
số nguyờn tố.
Định lý 2.4.2 (Định lý Lagrange). Cho p là số nguyờn tố, f(x) =∑n
i=0 aix
i ∈ Z[x] cú bậc n ≥ 1 sao cho p - an. Khi đú phương trỡnh
đồng dư f(x) ≡ 0 (mod p) cú nhiều nhất n nghiệm.
Chứng minh. Chứng minh bằng quy nạp theo n. Khi n = 1 ta cú f(x) =
a1x+a0 với p - a1. Vỡ (p, a1) = 1 nờn phương trỡnh a1x+a0 ≡ 0 (mod m)
cú duy nhất một nghiệm (theo Định lý 1.2.23). Do đú định lý đỳng với
n = 1.
Giả sử định lý đỳng với cỏc đa thức cú bậc k−1. Cho f(x) =∑ki=0 aixi
là một đa thức cú bậc k, trong đú p - ak. Nếu f(x) ≡ 0 (mod p) khụng cú
nghiệm, thỡ kết quả là rừ ràng đỳng. Do đú ta giả sử rằng phương trỡnh
f(x) ≡ 0 (mod p) cú ớt nhất một nghiệm, suy ra nú cú ớt nhất một số
nguyờn dương α thỏa món f(α) ≡ 0 (mod p) với 0 ≤ α < p. Lấy q(x) là
thương và r ∈ Z là phần dư khi chia f(x) cho x− α, trong đú q(x) là đa
thức cú bậc k − 1 cú hệ số nguyờn. Khi đú
f(x) = (x− α)q(x) + r.
Do đú ta cú
f(α) = (α− α)q(α) + r
0 ≡ 0 + r (mod p)
r ≡ 0 (mod p).
28
Vỡ vậy
f(x) = (x− α)q(x) (mod p)
trong đú q(x) cú bậc k−1. Gọi β là một giỏ trị nghiệm đỳng của f(x) ≡ 0
(mod p) mà β 6≡ α (mod p) và 0 ≤ β < p. Khi đú
f(β) ≡ (β − α)q(β) (mod p)
0 ≡ (β − α)q(β) (mod p).
Từ đú vỡ β − α 6= 0 (mod p) nờn q(β) ≡ 0 (mod p). Do vậy, mọi giỏ trị
nghiệm đỳng của f(x) ≡ 0 (mod p), mà 6≡ α (mod p), cũng là giỏ trị
nghiệm đỳng của phương trỡnh q(x) ≡ 0 (mod p). Hiển nhiờn, mọi giỏ
trị nghiệm đỳng của q(x) ≡ 0 (mod p) đều là giỏ trị nghiệm đỳng của
phương trỡnh f(x) ≡ 0 (mod p). Vỡ deg q(x) = k − 1, nờn ỏp dụng giả
thiết quy nạp, ta suy ra phương trỡnh q(x) ≡ 0 (mod p) cú nhiều nhất
là k − 1 nghiệm. Do vậy phương trỡnh f(x) ≡ 0 (mod m) cú nhiều nhất
1 + (k − 1) = k nghiệm.
Từ đú theo quy nạp ta suy ra định lý trờn là đỳng với mọi đa thức cú
bậc n ≥ 1.
Chẳng hạn đa thức f(x) = x2 − x + 1 trong Vớ dụ 2.4.1 cú bậc hai và
phương trỡnh f(x) ≡ 0 (mod 13) cú nhiều nhất hai nghiệm modulo 13.
Đa thức g(x) = 2x2+3x+4 cũng cú bậc hai nhưng phương trỡnh g(x) ≡ 0
(mod 5) khụng cú nghiệm modulo 5; trong cả hai trường hợp rừ ràng là
chỳng cú khụng quỏ hai nghiệm.
Kết quả dưới đõy là một hệ quả quan trọng của Định lý 2.4.2. Nú cú vai
trũ chớnh yếu để chỉ ra sự tồn tại của căn nguyờn thủy cho cỏc số nguyờn
tố.
Hệ quả 2.4.3. Nếu p là một số nguyờn tố và d | (p− 1), thỡ phương trỡnh
đồng dư xd − 1 ≡ 0 (mod p) cú chớnh xỏc d nghiệm modulo p.
Chứng minh. Theo Định lý Fermat nhỏ, ta thấy phương trỡnh đồng dư
xp−1 − 1 ≡ 0 (mod p) cú chớnh xỏc p− 1 nghiệm modulo p, cụ thể là cỏc
lớp thặng dư modulo p cú đại diện là 1, 2, 3, . . . , p− 1. Vỡ d | (p− 1), nờn
xp−1 − 1 = (xd − 1)(xp−1−d + xp−1−2d + ã ã ã+ xd + 1)
= (xd − 1)g(x),
29
trong đú g(x) = xp−1−d + xp−1−2d + ã ã ã + xd + 1 là một đa thức cú bậc
p−1−d. Theo Định lý Lagrange, ta thấy phương trỡnh g(x) ≡ 0 (mod p)
cú nhiều nhất p− 1−d nghiệm modulo p. Do đú, phương trỡnh xd− 1 ≡ 0
(mod p) cú ớt nhất là (p− 1)− (p− 1− d) = d nghiệm modulo p. Nhưng,
cũng ỏp dụng Định lý Lagrange, ta thấy phương trỡnh xd−1 ≡ 0 (mod p)
cú nhiều nhất d modulo p. Do vậy, phương trỡnh xd − 1 ≡ 0 (mod p) cú
chớnh xỏc d nghiệm modulo p.
Vớ dụ sau cho ta minh họa kết quả trờn.
Vớ dụ 2.4.4. Tỡm cỏc nghiệm của phương trỡnh đồng dư x3 − 1 ≡ 0
(mod 13).
Giải. Vỡ x3−1 = (x−1)(x2+x+1), nờn phương trỡnh kộo theo x3−1 ≡ 0
(mod 13) kộo theo x − 1 ≡ 0 (mod 13) hoặc x2 + x + 1 ≡ 0 (mod 13).
Phương trỡnh x − 1 ≡ 0 (mod 13) cú một nghiệm là x ≡ 1 (mod 13).
Phương trỡnh x2+x+1 ≡ x2+x−12 ≡ (x−3)(x+4) ≡ 0 (mod 13) nờn
x ≡ 3 (mod 13) hoặc x ≡ −4 ≡ 9 (mod 13). Rừ ràng trong ba số 1, 3, 9
khụng cú cặp nào đồng dư nhau theo modulo 13; do đú phương trỡnh đó
cho cú đỳng 3 nghiệm 1 (mod 13), 3 (mod 13) và 9 (mod 13).
Định lý Wilson cú thể nhận được từ Hệ quả 2.4.3 như sau. Trước tiờn,
lưu ý rằng Định lý Lagrange cú thể được phỏt biểu lại như sau: Cho
f(x) =
∑n
i=0 aix
i ∈ Z cú bậc n. Nếu phương trỡnh đồng dư f(x) ≡ 0
(mod p) cú nhiều hơn n nghiệm thỡ ai ≡ 0 (mod p) với mọi i = 0, 1, . . . , n.
Hệ quả 2.4.5 (Định lý Wilson). Nếu p là số nguyờn tố, thỡ
(p− 1)! ≡ −1 (mod p).
Chứng minh. (Việc quan trọng nhất trong chứng minh định lý này phụ
thuộc vào việc lựa chọn đa thức f(x) phự hợp).
Chọn đa thức f(x) = (x−1)(x−2) . . . (x−p+1)−xp−1+1. Rừ ràng là
f(x) cú bậc p−2 và cú cỏc hệ số nguyờn. Theo định lý Fermat nhỏ, ta thấy
phương trỡnh xp−1− 1 ≡ 0 (mod p) cú p− 1 nghiệm. Mỗi một nghiệm đú
cũng là nghiệm của phương trỡnh (x−1)(x−2) . . . (x−p+1) ≡ 0 (mod p).
Do đú phương trỡnh f(x) ≡ 0 (mod p) cú p−1 nghiệm, vỡ thế nú cú nhiều
hơn một nghiệmso với bậc của f(x). Từ đú theo Định lý Lagrange, suy
30
ra cỏc hệ tử của f(x) phải đồng dư với 0 modulo p. Đặc biệt ta suy ra
f(0) ≡ 0 (mod p). Trong đú
f(0) = (−1)(−2) ã ã ã [−(p− 1)]− 0 + 1 = (−1)p−1(p− 1)! + 1.
Do đú, (−1)p−1(p−1)!+1 ≡ 0 (mod p); tức là (p−1)! ≡ (−1)p (mod p).
Nếu p = 2 thỡ (−1)p ≡ 1 ≡ −1 (mod p). Nếu p lẻ, thỡ (−1)p = −1. Vỡ
vậy, trong cả hai trường hợp, ta đều cú (p− 1)! ≡ −1 (mod p).
Tiếp theo, ta trở lại kết quả chớnh về số cỏc thặng dư cú cấp d theo
modulo p. Tuy nhiờn, trước khi ta thực hiện, ta hóy xột một vớ dụ mà sẽ
là minh họa cho chứng minh của định lý.
Vớ dụ 2.4.6. Cho p = 19 và d | (p − 1). Kớ hiệu ψ(d) số cỏc thặng
dư cú cấp d theo modulo p. Hóy tớnh ψ(d) và ϕ(d) cho mỗi d, và tớnh∑
d|(p−1) ψ(d).
Giải. Bởi vỡ d | 18 nờn d = 1, 2, 3, 6, 9 hoặc 18. Để tớnh ψ(d) số cỏc thặng
dư cú cấp d, ta liệt kờ cỏc thặng dư cấp d (tức là cỏc thặng dư a cú
ord19 a = d) và ϕ(d) trong Bảng 2.2.
d 1 2 3 6 9 18
thặng
dư cú
cấp d
1 18 7, 11 8, 12 4, 5, 6,
9, 16,
17
2, 3,
10, 13,
14, 15
ψ(d) 1 1 2 2 6 6
ϕ(d) 1 1 2 2 6 6
Bảng 2.2: Giỏ trị của ψ(d) và ϕ(d)
Từ bảng trờn ta thấy rằng∑
d|(p−1)
ψ(d) =
∑
d|18
ψ(d) = 1 + 1 + 2 + 2 + 6 + 6 = 18 = p− 1.
Ta sẽ tỡm hiểu thờm về vớ dụ trờn một chỳt. Chỳ ý rằng cỏc thặng dư
(modulo 19) cú cấp d tạo thành một phõn hoạch cho tập cỏc thặng dư
dương modulo 19, như ở Hỡnh 2.1 đó chỉ ra; ψ(d) là kớ hiệu cho số cỏc
phần tử trong mỗi lớp. Quả ngạc nhiờn là ψ(d) = ϕ(d) với mọi d|18.
31
Hỡnh 2.1: Phõn hoạch của tập cỏc số dư dương modulo 19.
Bõy giờ ta sẽ đề cập đến kết quả chớnh, được chứng minh bởi nhà toỏn
học Phỏp A. M. Legendre năm 1785.
Định lý 2.4.7. Cho p là một số nguyờn tố và d là ước số nguyờn dương
của p−1. Khi đú cú chớnh xỏc ϕ(d) cỏc thặng dư (modulo p) cú cấp d theo
modulo p.
Chứng minh. Với mỗi ước số dương d của p− 1, ta lấy ψ(d) kớ hiệu cho số
cỏc thặng dư dương modulo p cú cấp d. Bởi vỡ ta cú p− 1 thặng dư dương
và mỗi số đú cú duy nhất một cấp d, nờn cỏc dư dương cú cấp d lập thành
một phõn hoạch cho tập cỏc thặng dư dương. Do đú,∑
d|(p−1)
ψ(d) = p− 1.
Mặt khỏc theo cụng thức Gauss, ta cú∑
d|(p−1)
ϕ(d) = p− 1.
Do đú, ta thu được ∑
d|(p−1)
ψ(d) =
∑
d|(p−1)
ϕ(d). (2.3)
Tiếp theo, ta cần chỉ ra ϕ(d) = ψ(d) với mọi d|(p− 1). Để thực hiện điều
này, ta xột hai trường hợp.
Trường hợp 1: Cho ψ(d) = 0. Khi đú rừ ràng ψ(d) < ϕ(d), vỡ vậy ψ(d) ≤
ϕ(d).
32
Trường hợp 2: Cho ψ(d) 6= 0. Khi đú tồn tại một số nguyờn a cú cấp d
theo modulo p. Do đú, từ Hệ quả 2.1.6, ta suy ra d số nguyờn a, a2, . . . , ad
khụng đồng dư modulo p từng cặp. Bờn cạnh đú, mỗi số đú đều nghiệm
đỳng phương trỡnh xd − 1 ≡ 0 (mod p), vỡ (ak)d = (ad)k ≡ 1 (mod p),
trong đú 1 ≤ k ≤ d. Do đú theo Hệ quả 2.4.3, chỳng là đại diện cho d
nghiệm của phương trỡnh xd − 1 ≡ 0 (mod p) và ordp(ak) | d theo Định
lý 2.1.3.
Theo Hệ quả 2.1.10, ordp(a
k) = ordp a = d khi và chỉ khi (k, d) = 1. Vỡ
ta cú ϕ(d) số nguyờn dương≤ d
Các file đính kèm theo tài liệu này:
- luan_van_ung_dung_cua_cap_va_chi_so_cho_so_nguyen_theo_modul.pdf