Luận văn Ứng dụng của cấp và chỉ số cho số nguyên theo modulo

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