Một số kiến thức cơ bản về số học
Trong phần này, chúng tôi sẽ giới thiệu những kiến thức cơ bản về số học, được tham khảo từ các tài liệu [1], [2], [4] Định lý 1.1.1 nêu rõ rằng, với hai số nguyên a và b (với b khác 0), tồn tại duy nhất các số nguyên q và r sao cho a = bq + r, trong đó r nằm trong khoảng từ 0 đến |b|.
Số r trong định lý trên được gọi là phần dư của phép chia a cho b Nếu r = 0 thì ta nói b là một ước của a, và ký hiệu là b | a.
Cho a và b là hai số nguyên, số nguyên d được gọi là ước chung lớn nhất của a và b nếu d là một ước chung của a và b, và mọi ước chung bất kỳ d0 của a và b đều chia hết cho d Ký hiệu (a, b) được sử dụng để chỉ ước chung lớn nhất dương của a và b.
Mệnh đề 1.1.2 Cho a, b, c là các số nguyên khác 0.
(ii) Nếu b | a, c | a và (b, c) = 1 thì bc | a.
(iii) Nếu c | ab và (b, c) = 1 thì c | a.
Mệnh đề 1.1.3 Cho u và v là các số nguyên Nếu d = (u, v) thì tồn tại các số nguyên x và y sao cho d = xu + yv.
Số tự nhiên p lớn hơn 1 được gọi là số nguyên tố nếu nó chỉ có hai ước là 1 và chính nó Theo Định lý cơ bản của số học, mọi số tự nhiên lớn hơn 1 đều có thể phân tích thành tích của các số nguyên tố, và sự phân tích này là duy nhất, không tính đến thứ tự của các nhân tử.
Theo Định lý cơ bản của số học, mọi số nguyên n > 1 có thể được biểu diễn dưới dạng n = p₁^α₁ * p₂^α₂ * * pₖ^αₖ, trong đó p₁, p₂, , pₖ là các số nguyên tố phân biệt và α₁, α₂, , αₖ là các số nguyên dương Biểu diễn này được gọi là biểu diễn chính tắc của n Định nghĩa 1.1.5 nêu rõ rằng, với m là một số nguyên dương, hai số nguyên a và b được gọi là đồng dư theo môđun m, ký hiệu là a ≡ b (mod m), nếu a − b chia hết cho m.
Tính chất 1.1.6 Cho a, b, c, d, m, nlà các số nguyên dương Nếu a ≡ b (mod m) và c ≡ d (mod m) thì:
Nếu \( d \) là ước chung của \( a, b \) và \( m \), thì \( a \, d \equiv b \, d \, (\text{mod} \, m \, d) \) Định lý 1.1.7 chỉ ra rằng phương trình đồng dư bậc nhất \( ax + b \equiv 0 \, (\text{mod} \, m) \) có nghiệm nếu và chỉ nếu \( d | b \) với \( d = (a, m) \); nếu có nghiệm, phương trình sẽ có \( d \) nghiệm theo môđun \( m \) dưới dạng \( x_0, x_0 + m/d, x_0 + 2m/d, \ldots, x_0 + (d-1)m/d \) Định lý 1.1.8, hay Định lý Thặng dư Trung Hoa, khẳng định rằng hệ phương trình đồng dư \( x \equiv a_i \, (\text{mod} \, m_i) \) với \( i = 1, 2, \ldots, k \) có nghiệm duy nhất theo môđun \( m_1 m_2 \ldots m_k \) khi các \( m_i \) là các số nguyên dương nguyên tố cùng nhau Định lý 1.1.9 cho biết nếu \( p \) là số nguyên tố và \( f(x) = a_n x^n + \ldots + a_1 x + a_0 \) là đa thức với hệ số nguyên, thì phương trình \( f(x) \equiv 0 \, (\text{mod} \, p) \) có không quá \( n \) nghiệm (kể cả bội) Cuối cùng, định nghĩa 1.1.10 ghi nhận rằng \( \phi(m) \) là số các lớp thặng dư nguyên tố cùng nhau với \( m \), và hàm \( \phi(m) \) được gọi là Hàm Euler.
Ta có thể hiểuϕ(m)như là số các số nguyênk với1 ≤ k < msao cho(k, m) = 1. Nếu p là một số nguyên tố thì rõ ràng ϕ(p) = p − 1.
Tính chất 1.1.11 Nếu (m 1 , m 2 ) = 1 thì ϕ(m 1 m 2 ) = ϕ(m 1 )ϕ(m 2 ). Định lý 1.1.12 Với m là một số nguyên dương lớn hơn 1 ϕ(m) = mY p|m
1 − 1 p trong đó p là các ước nguyên tố của m. Định lý 1.1.13 (Định lý Euler) Cho m và a là các số nguyên dương Nếu (a, m) = 1 thì a ϕ(m) ≡ 1 (mod m).
Trong trường hợp đặc biệt, Định lý Fermat (Định lý 1.1.14) khẳng định rằng với p là một số nguyên tố và a là một số nguyên bất kỳ, ta có a^p ≡ a (mod p) Hơn nữa, định nghĩa 1.1.15 chỉ ra rằng tập A = {a1, a2, , an} là một tập hợp chứa n số nguyên.
A là một hệ thặng dư đầy đủ theo môđun n khi và chỉ khi a i 6≡ a j (mod n) với
1 ≤ i < j ≤ n. Định nghĩa 1.1.16 Cho tập B = {b 1 , b 2 , , b k } là tập hợp có k số nguyên, B là một hệ thặng dư thu gọn theo môđun n khi thỏa mãn ba điều kiện sau (i) k = ϕ(n);
Nếu \( b_i \equiv b_j \, (\text{mod} \, n) \) với \( 1 \leq i < j \leq k \), thì theo Định nghĩa 1.1.17, cho \( m \) là một số tự nhiên lớn hơn 1 và \( a \) là một số nguyên sao cho \( (a, m) = 1 \), nếu tồn tại số nguyên \( x \) sao cho \( x^k \equiv a \, (\text{mod} \, m) \), thì \( a \) được gọi là một thặng dư bậc \( k \) theo môđun \( m \); ngược lại, \( a \) là một bất thặng dư bậc \( k \) theo môđun \( m \) Thêm vào đó, theo Định nghĩa 1.1.18, với \( p > 2 \) là một số nguyên tố và \( a \in \mathbb{Z} \) sao cho \( p \nmid a \), ta ký hiệu là \( a \, p \).
1 nếu a là một thặng dư bậc hai theo môđun p
−1 nếu a là một bất thặng dư bậc hai theo môđun p
Rõ ràng là nếu a ≡ b (mod p) thì a p
Định lý 1.1.19 Cho p > 2 là một số nguyên tố Có đúng p − 1
2 thặng dư bậc hai theo môđun p, và p − 1
2 bất thặng dư bậc hai theo môđun p Hơn nữa, các phần tử 1 2 , 2 2 , , p − 1 2
Định lý Euler (1.1.20) khẳng định rằng với một số nguyên tố p lớn hơn 2, mọi số nguyên a thỏa mãn điều kiện p - a sẽ có tính chất a^(p-1)/2 ≡ a^p Điều này cho thấy mối quan hệ giữa các thặng dư bậc hai theo môđun p.
Từ Định lý 1.1.20 ta có kết quả sau.
Mệnh đề 1.1.21 Nếu p- ab thì ab p
Mệnh đề 1.1.22 Cho p là một số nguyên tố lẻ.
Mệnh đề 1.1.23 Cho p là một số nguyên tố Số 2 là một thặng dư bậc hai theo môđun p khi và chỉ khi p ≡ ±1 (mod 8).
Mệnh đề 1.1.24 Cho p là một số nguyên tố Số −2 là một thặng dư bậc hai theo môđun p khi và chỉ khi p ≡ 1 (mod 8) hoặc p ≡ 3 (mod 8).
Một số kết quả chuẩn bị
Trong mục này chúng tôi trình bày một số kết quả được sử dụng trong luận văn Các kết quả trong mục này được tham khảo từ tài liệu [5].
Mệnh đề 1.2.1 Nếu p = 2 α + 1 là số nguyên tố thì α = 2 n với n là số nguyên không âm.
Chứng minh Giả sử trái lại, đặt α = 2 n m với n, m là các số nguyên không âm,trong đó m lẻ và m ≥ 3 Khi đó p = 2 α +1 = 2 2 n m +1 = (2 m +1)2 (2 n −1)m −(2 m +1)2 (2 n −2)m + .−(2 m +1)2 m +(2 m +1)
Vì 1 < 2 m + 1 < p nên p không là số nguyên tố, mâu thuẫn với giả thiết Vậy ta có điều phải chứng minh.
Ký hiệu F n = 2 2 n + 1 với n ≥ 0 Fermat đưa ra giả thiết rằng F n là số nguyên tố với mọi n Tuy nhiên, vào năm 1732, Euler đã chỉ ra rằng F 5 =
2 2 5 +1 = 641.6700417phủ nhận giả thiết của Fermat Cho đến nay (tháng 07 năm
2021) các số nguyên tố Fermat được biết chỉ gồm năm số đầu tiên làF 0 = 3, F 1 =
F 3 = 257, F 4 = 65537 Người ta giả thiết rằng chỉ có hữu hạn số nguyên tố Fermat.
Mệnh đề 1.2.2 Cho p là một số nguyên tố Khi đó
C p k ≡ 0 (mod p) với mọi số nguyên k sao cho 1 ≤ k ≤ p − 1.
Chứng minh Với 1 ≤ k ≤ p − 1, ta có
Vìp là số nguyên tố và C p k nguyên nên p, (p − 1)! k!(p − k)!
= 1 Do đó p | C p k Vậy ta có điều phải chứng minh.
Mệnh đề 1.2.3 Cho p là một số nguyên tố và α là một số nguyên dương Nếu a ≡ b (mod p α ) thì a p ≡ b p (mod p α+1 ).
Chứng minh Giả sử a = kp α + b với k ∈Z Khi đó a p − b p = (kp α + b) p − b p = k p p pα + C p 1 k p−1 p (p−1)α + + C p p−2 k 2 p α+1 + C p p−1 kp α
Vì p | C p k với mọi k = 1, 2, , p − 1 theo Mệnh đề 1.2.2, cho nên từ đó suy ra a p − b p chia hết cho p α+1 , hay a p ≡ b p (mod p α+1 ) Vậy ta có điều phải chứng minh.
Mệnh đề 1.2.4 Cho p là một số nguyên tố lẻ, α ≥ 2 là một số nguyên Khi đó với a là một số nguyên bất kỳ thì (1 + ap) p α−2
Chúng ta sẽ chứng minh đồng dư thức bằng phương pháp quy nạp với α = 2, trong đó đồng dư thức là hiển nhiên Giả sử đồng dư thức đúng với mọi α ≥ 2, nhiệm vụ của chúng ta là chứng minh rằng đồng dư thức cũng đúng với α + 1.
(1 + ap) p α−1 ≡ 1 + ap α (mod p α+1 ). Thật vậy, theo giả thiết quy nạp ta có
(1 + ap) p α−2 ≡ 1 + ap α−1 (mod p α ). Áp dụng Mệnh đề 1.2.3, từ đó suy ra
Do p ≥ 3 và α ≥ 2cho nên p(α − 1) − α ≥ 3(α − 1) − α = 2α − 3 ≥ 1 Vì p | C p k với mọi k = 1, 2, , p − 1 theo Mệnh đề 1.2.2, cho nên từ đó suy ra
(1 + ap α−1 ) p ≡ 1 + ap α (mod p α+1 ). Vậy ta có điều phải chứng minh.
Mệnh đề 1.2.5 Với α ≥ 3, các số (−1) a 5 b với 0 ≤ a ≤ 1 và 0 ≤ b ≤ 2 α−2 lập thành một hệ thặng dư thu gọn theo môđun 2 α
Chứng minh Bằng phép chứng minh quy nạp ta có thể chứng tỏ được rằng
5 2 α−3 ≡ 1 + 2 α−1 (mod 2 α ) Do đó 5 2 α−2 ≡ 1 + 2 α (mod 2 α+1 ) Cho nên
5 2 α−2 ≡ 1 (mod 2 α ) Từ đó suy ra cấp của 5 theo môđun 2 α là 2 α−2
Chúng ta sẽ chứng minh rằng các số (−1) a 5 b với 0 ≤ a ≤ 1 và 0 ≤ b ≤ 2 α−2 là không đồng dư với nhau theo môđun 2 α Giả sử (−1) a 5 b ≡ (−1) a 0 5 b 0 (mod 2 α), khi đó a và a 0 có cùng tính chẵn lẻ, dẫn đến a = a 0 Điều này suy ra 5 b ≡ 5 b 0 (mod 2 α) Vì cấp của 5 theo môđun 2 α là 2 α−2, nên b ≡ b 0 (mod 2 α−2), từ đó suy ra b = b 0 Vậy ta đã chứng minh được điều cần chứng minh.
Mệnh đề 1.2.6 Với α ≥ 3, các số (−1) a (5 7 ) b với 0 ≤ a ≤ 1 và 0 ≤ b ≤ 2 α−2 lập thành một hệ thặng dư thu gọn theo môđun 2 α
Chứng minh Bằng phép chứng minh quy nạp ta có thể chứng tỏ được rằng
(5 7 ) 2 α−3 ≡ 1 + 2 α−1 (mod 2 α ) Do đó (5 7 ) 2 α−2 ≡ 1 + 2 α (mod 2 α+1 ) Cho nên
(5 7 ) 2 α−2 ≡ 1 (mod 2 α ) Từ đó suy ra cấp của 5 7 theo môđun 2 α là 2 α−2
Chúng ta sẽ chứng minh rằng các số (−1) a (5 7 ) b với 0 ≤ a ≤ 1 và 0 ≤ b ≤ 2 α−2 là không đồng dư với nhau theo môđun 2 α Giả sử rằng (−1) a (5 7 ) b ≡ (−1) a 0 (5 7 ) b 0 (mod 2 α) Khi đó, a và a 0 phải cùng tính chẵn lẻ, dẫn đến kết luận a = a 0.
Do đó (5 7 ) b ≡ (5 7 ) b 0 (mod 2 α ) Vì cấp của 5 7 theo môđun 2 α là 2 α−2 , nên từ đó suy ra b ≡ b 0 (mod 2 α−2 ), do đó b = b 0 Vậy ta có điều phải chứng minh.
Chương này khám phá các vấn đề liên quan đến căn nguyên thủy theo môđun cho các số nguyên dương, bao gồm các tính chất cơ bản, điều kiện tồn tại, và số lượng căn nguyên thủy Ngoài ra, chương cũng đề cập đến mối liên hệ giữa thặng dư bậc hai và căn nguyên thủy, cũng như các điều kiện để xác định một số cho trước là căn nguyên thủy theo môđun của một số nguyên tố Cuối cùng, chương trình bày một thuật toán để tìm căn nguyên thủy theo môđun cho một số nguyên dương đã cho.
Cấp của phần tử
Trong mục này, chúng tôi giới thiệu một số tính chất của cấp một phần tử theo môđun nhất định, nhằm chuẩn bị cho việc nghiên cứu các vấn đề về căn nguyên thủy Các kết quả được tham khảo từ tài liệu [1], [2], [4] Đối với một số nguyên dương m và một số nguyên a, theo Định lý 1.1.13, nếu (a, m) = 1 thì a ϕ(m) ≡ 1 (mod m) Số nguyên dương l nhỏ nhất thỏa mãn a l ≡ 1 (mod m) được gọi là cấp của a theo môđun m, ký hiệu là ord m (a).
Ví dụ 2.1.1 Cho m = 10, a = 7 Tính toán trực tiếp ta có được
Trong định nghĩa của cấp một phần tử a theo môđun m, điều kiện (a, m) = 1 là cần thiết Ví dụ, với m = 10 và a = 4, phương trình đồng dư 4l ≡ 1 (mod 10) không có nghiệm Do đó, không tồn tại cấp của 4 theo môđun 10.
Mệnh đề 2.1.3 Chom là một số nguyên dương, a là một số nguyên, (a, m) = 1. Với t là một số nguyên bất kỳ, a t ≡ 1 (mod m) khi và chỉ khi ord m (a) | t.
Chứng minh Đặt l = ord m (a) Giả sử l | t, hay t = ql với q ∈ Z Khi đó a t ≡ (a l ) q ≡ 1 (mod m).
Ngược lại, giả sử a t ≡ 1 (mod m), và t = ql + r với q, r ∈ Z, 0 ≤ r < l Khi đó 1 ≡ a t ≡ a ql+r ≡ (a l ) q a r ≡ a r (mod m) Mà l = ord m (a) cho nên từ đó suy ra r = 0, hay l | t Vậy ta có điều phải chứng minh.
Mệnh đề 2.1.4 Chom là một số nguyên dương, a là một số nguyên, (a, m) = 1. Với k là một số nguyên dương bất kỳ thì ord m (a k ) = ord m (a)
(ord m (a), k) Chứng minh Vì (a, m) = 1 cho nên (a k , m) = 1 Ký hiệu l = ord m (a), d = (k, l). Giả sử k = dk 0 , l = d.l 0 với k 0 , l 0 ∈ Z Ta sẽ chứng minh ord m (a k ) = l 0 Thật vậy, ta có
Cho t ∈ Z bất kỳ sao cho (a k ) t ≡ 1 (mod m), từ đó suy ra 1 ≡ (a k ) t ≡ a kt (mod m) Với ord m (a) = l, ta có l | kt, dẫn đến dl 0 | dk 0 t, và do đó l 0 | k 0 t Vì (k 0 , l 0 ) = 1, suy ra l 0 | t Điều này chứng minh rằng ord m (a k ) = l 0, hoàn thành điều cần chứng minh.
Mệnh đề 2.1.5 Cho m là một số nguyên dương, a và b là các số nguyên,
(a, m) = (b, m) = 1 Nếu (ord m (a), ord m (b)) = 1 thì ord m (ab) = ord m (a)ord m (b).
Chứng minh Vì (a, m) = 1 và (b, m) = 1 nên (ab, m) = 1 Đặt l = ord m (a), k = ord m (b), e = ord m (ab) Vì (ab) lk = a l k b k l
Theo điều kiện \(1 \equiv (mod \, m)\), ta có \(e | lk\) Đồng thời, từ \(a ke \equiv a ke b ke \equiv (ab) ke \equiv 1 (mod \, m)\), suy ra \(l | ke\) Vì \((l, k) = 1\), nên từ đó suy ra \(r | e\) Lập luận tương tự cho thấy \(k | e\), và từ đó suy ra \(lk | e\) Do đó, \(e = lk\), điều này chứng minh được yêu cầu.
Kết quả sau đây sẽ được sử dụng về sau.
Theo mệnh đề 2.1.6, với p là một số nguyên tố lẻ, q là một số nguyên tố, và h là một số nguyên dương thỏa mãn điều kiện q h | p − 1, thì tồn tại một số nguyên a sao cho ord p (a) = q h.
Chứng minh Theo Định lý 1.1.9 phương trình đồng dư x p−1 q ≡ 1 (mod p) có không quá p − 1 q nghiệm Vì p − 1 q < p − 1 cho nên tồn tại số nguyên u với
1 ≤ u ≤ p − 1 sao cho u p−1 q 6≡ 1 (mod p) Đặt a = u p−1 qh Ta sẽ chứng minh rằng ord p (a) = q h
Vì \( a^{q h} \equiv u^{p-1} \equiv 1 \mod p \), suy ra \( \text{ord}_p(a) \) chia hết cho \( q h \) Nếu \( \text{ord}_p(a) \neq q h \), thì \( \text{ord}_p(a) \) sẽ chia hết cho \( q h - 1 \) Khi đó, ta có \( u^{p-1} q \equiv a^{q h - 1} \equiv 1 \mod p \), điều này mâu thuẫn với tính chất của \( u \) Do đó, kết luận rằng \( \text{ord}_p(a) = q h \) là đúng.
Căn nguyên thủy theo môđun m
Trong phần này, chúng tôi sẽ trình bày những tính chất cơ bản của căn nguyên thủy và các kết quả chính liên quan đến điều kiện tồn tại căn nguyên thủy theo môđun m với m là một số nguyên dương Các kết quả này được tham khảo từ các tài liệu [1], [2], [4] Định nghĩa 2.2.1 nêu rõ rằng, cho m là một số nguyên dương và g là một số nguyên sao cho (g, m) = 1, thì g được gọi là căn nguyên thủy theo môđun m nếu ord m (g) = ϕ(m), trong đó ϕ là hàm Euler.
Ví dụ 2.2.2 Cho m = 9 Rõ ràng ϕ(9) = 6 và (2, 9) = 1 Ta thấy rằng
2 4 ≡ 7 (mod 9), 2 5 ≡ 5 (mod 9), 2 6 ≡ 1 (mod 9). Cho nên 2 là một căn nguyên thủy theo môđun 9.
Mệnh đề 2.2.3 nêu rõ rằng, với m là một số nguyên dương, số nguyên g có (g, m) = 1 sẽ là một căn nguyên thủy theo môđun m nếu và chỉ nếu tập hợp {1, g, g^2, , g^(ϕ(m)−1)} tạo thành một hệ thặng dư thu gọn theo môđun m.
Để chứng minh rằng {1, g, g², , g^(ϕ(m)-1)} là hệ thặng dư thu gọn theo môđun m, ta cần chỉ ra rằng g là một căn nguyên thủy theo môđun m Ngược lại, nếu g được xác định là căn nguyên thủy theo môđun m, thì ta có thể chứng minh rằng hệ {1, g, g², , g^(ϕ(m)-1)} cũng sẽ là hệ thặng dư thu gọn theo môđun m Do (g, m) = 1, dẫn đến (g^k, m) = 1 với mọi k.
Chúng ta cần chứng minh rằng g i 6≡ g j (mod m) với mọi 0 ≤ i ≤ ϕ(m) − 1 Giả sử ngược lại rằng tồn tại i, j với 0 ≤ i < j ≤ ϕ(m) − 1 sao cho g i ≡ g j (mod m) Khi đó, từ g i (g j−i − 1) ≡ 0 (mod m) và (g i , m) = 1, suy ra g i−j ≡ 1 (mod m) là điều không thể xảy ra vì 0 < i − j < ϕ(m) và g có cấp là ϕ(m) Do đó, các phần tử trong hệ {1, g, g 2 , , g ϕ(m−1) } là đôi một không đồng dư theo môđun m, dẫn đến hệ này có ϕ(m) phần tử Theo Định nghĩa 1.1.16, hệ đã cho là một hệ thặng dư thu gọn theo môđun m.
Từ Mệnh đề 2.2.3, ta có ngay kết quả sau.
Mệnh đề 2.2.4 Cho m là một số nguyên dương, g là một căn nguyên thủy theo môđun m Với k là một số nguyên bất kỳ, ord m (g k ) = ϕ(m) d với d = (ϕ(m), k).
Từ đó ta có hệ quả sau.
Hệ quả 2.2.5 Cho g là một căn nguyên thủy theo môđun m Với k nguyên bất kỳ, g k là căn nguyên thủy theo môđun m khi và chỉ khi (k, ϕ(m)) = 1.
Từ Hệ quả 2.2.5 và định nghĩa của hàm Euler ta có kết quả sau.
Hệ quả 2.2.6 Cho m là một số nguyên dương Nếu m có căn nguyên thủy thì có đúng ϕ(ϕ(m)) căn nguyên thủy theo môđun m trong phạm vi từ 1 đến m.
Ví dụ 2.2.7 Tìm tất cả các căn nguyên thủy theo môđun m = 22.
Rõ ràng ϕ(22) = ϕ(2)ϕ(11) = 10 Tính toán trực tiếp ta thấy rằng
Căn nguyên thủy theo môđun 22 là 7, cùng với các số 7^3, 7^7 và 7^9 Theo Mệnh đề 2.2.6, các căn nguyên thủy trong khoảng từ 1 đến 22 bao gồm các số 7, 13, 17 và 19 Qua tính toán trực tiếp, ta xác định được các căn nguyên thủy này.
Theo quy ước 2.2.8, số căn nguyên thủy theo môđun m sẽ được gọi tắt là số căn nguyên thủy trong khoảng từ 1 đến m.
Phần còn lại của bài viết sẽ trình bày các điều kiện cần thiết để tồn tại căn nguyên thủy trong một môđun là số nguyên dương đã cho Đối với môđun nguyên tố, chúng ta có những kết quả cụ thể như sau.
Mệnh đề 2.2.9 Nếu p là một số nguyên tố thì tồn tại căn nguyên thủy theo môđun p.
Nếu p = 2, thì 1 là căn nguyên thủy theo môđun 2 Do đó, giả thiết p là một số nguyên tố lẻ, và ta có thể biểu diễn p − 1 một cách chính xác dưới dạng p − 1 = k.
Xét biểu thức Y = ∏(p_i^α_i) với p_1, p_2, , p_k là các số nguyên tố phân biệt và α_1, α_2, , α_k là các số nguyên dương Theo Mệnh đề 2.1.6, với mỗi i = 1, 2, , k, tồn tại một số nguyên a_i có cấp p^α_i Đặt a = a_1 * a_2 * * a_k, khi đó theo Mệnh đề 2.1.6, cấp của a là p - 1, chứng minh rằng a là một căn nguyên thủy theo môđun p Do đó, điều cần chứng minh đã được xác nhận Đối với môđun lũy thừa của một số nguyên tố, chúng ta có hai kết quả quan trọng.
Mệnh đề 2.2.10 Cho plà một số nguyên tố lẻ Khi đó tồn tại căn nguyên thủy theo môđun p α với mọi α nguyên dương.
Chứng minh Theo Mệnh đề 2.2.9, luôn tồn tại căn nguyên thủy theo môđun p, ký hiệu là g Khi đó g + p cũng là một căn nguyên thủy theo môđun p Nếu g p−1 ≡ 1 (mod p 2 ) thì
Do đó, ngay từ đầu ta có thể giả thiết rằng g p−1 6≡ 1 (mod p 2 ) Ta sẽ chứng tỏ rằng g cũng là một căn nguyên thủy theo môđun p α với mọi α ≥ 2.
Vì g p−1 ≡ 1 (mod p) và g p−1 6≡ 1 (mod p 2 ) nên ta có thể biểu diễn g p−1 = 1 + kp với k nguyên và p- k Áp dụng Mệnh đề 2.3.1, ta có g (p−1)p α−2 = (1 + kp) p α−2 ≡ 1 + kp α−1 6≡ 1 (mod p α ).
Gọi e là cấp của g theo môđun p α, ta có p − 1 | e | ϕ(p α ) = (p − 1)p α−1 Từ đẳng thức này, suy ra e = ϕ(p α), chứng tỏ rằng g là căn nguyên thủy theo môđun p α Do đó, điều cần chứng minh đã được xác nhận.
Mệnh đề 2.2.11 Với α là một số nguyên dương, tồn tại căn nguyên thủy theo môđun 2 α khi và chỉ khi α = 1 hoăc α = 2.
Chứng minh rằng 1 là căn nguyên thủy theo môđun 2 và −1 là căn nguyên thủy theo môđun 4 Giả sử α ≥ 3, ta nhận thấy rằng với x là số nguyên lẻ bất kỳ, x² ≡ 1 (mod 2³) Áp dụng Mệnh đề 1.2.3 và sử dụng phép quy nạp, ta có x²α−2 ≡ (x²)²α−3 ≡ 1 (mod 2α).
Vì ϕ(2 α ) = 2 α−1 , cho nên từ đó suy ra không tồn tại căn nguyên thủy theo môđun 2 α
Trong trường hợp tổng quát, Định lý 2.2.12 chỉ ra rằng tồn tại căn nguyên thủy theo môđun m khi và chỉ khi m bằng 2, 4, p^α hoặc 2p^α, với p là một số nguyên tố lẻ và α ≥ 1 Để chứng minh định lý này, cần phải sử dụng một bổ đề liên quan.
Bổ đề 2.2.13 Cho m ≥ 2 là một số nguyên và m = m 1 m 2 với (m 1 , m 2 ) = 1 Nếu (ϕ(m 1 ), ϕ(m 2 )) 6= 1 thì không tồn tại căn nguyên thủy theo môđun m.
Để chứng minh, giả sử a là một số nguyên bất kỳ với (a, m) = 1 Khi đó, ta có (a, m₁) = 1 và (a, m₂) = 1 Từ đó suy ra a^ϕ(m₁) ≡ 1 (mod m₁) và a^ϕ(m₂) ≡ 1 (mod m₂) Đặt l = [ϕ(m₁), ϕ(m₂)], ta có a^l ≡ 1 (mod m) Do (ϕ(m₁), ϕ(m₂)) ≠ 1, nên l < ϕ(m₁)ϕ(m₂) = ϕ(m) Điều này dẫn đến kết luận rằng không tồn tại căn nguyên thủy theo môđun m.
Định lý 2.2.12 chứng minh rằng nếu \( m \) là một số nguyên tố lẻ, thì \( \phi(p^\alpha) \) với \( \alpha \geq 1 \) là số chẵn Điều này dẫn đến việc nếu \( m \) có hơn một ước nguyên tố lẻ, theo Bổ đề 2.2.13, sẽ không tồn tại căn nguyên thủy theo môđun \( m \) Do đó, \( m \) chỉ có thể có các dạng \( 2^\alpha \), \( p^\alpha \), hoặc \( 2^\alpha p^\beta \) với \( p \) là số nguyên tố lẻ và \( \alpha, \beta \) là các số nguyên dương Cụ thể, nếu \( m = 2^\alpha \), theo Mệnh đề 2.2.11, căn nguyên thủy theo môđun \( m \) tồn tại khi và chỉ khi \( \alpha = 1 \) hoặc \( \alpha = 2 \) Nếu \( m = p^\alpha \), theo Mệnh đề 2.2.10, luôn tồn tại căn nguyên thủy theo môđun \( m \).
Trong trường hợp m = 2^α p^β, nếu α ≥ 2 thì ϕ(2^α) là số chẵn Do ϕ(p^β) cũng là số chẵn, theo Bổ đề 2.2.13, không tồn tại căn nguyên thủy theo môđun m.
Số nguyên tố với số căn nguyên thủy cho trước
Mục tiêu của bài viết này là xác định sự tồn tại của các số nguyên tố p sao cho số lượng căn nguyên thủy theo môđun p bằng một số nguyên dương t cho trước Nếu tồn tại, bài viết sẽ tìm ra tất cả các số nguyên tố p thỏa mãn điều kiện này Các kết quả được trình bày dựa trên tài liệu tham khảo từ các nguồn [1], [2], [4].
Trước tiên ta cần một kết quả chuẩn bị.
Mệnh đề 2.3.1 ϕ(m) là số chẵn với mọi số nguyên m, m > 2 Hơn nữa, nếu r là số các ước nguyên tố lẻ phân biệt của m thì 2 r là ước của ϕ(m).
Q i=1 p α i i với p i là các ước số nguyên tố phân biệt, α 1 , α 2 , , α k là các số nguyên dương Khi đó ϕ(m) = k
(p i − 1)p i α i −1 là số chẵn, từ đó suy ra ϕ(m) là số chẵn.
Vì 2 | p i − 1 với mỗi p i lẻ, 1 ≤ i ≤ k nên
(p i − 1)p i α 1 −1 do m có r ước nguyên tố lẻ phân biệt Do đó 2 r | ϕ(m) Vậy ta có điều phải chứng minh.
Trường hợp số căn nguyên thủy bằng 1 ta có kết quả sau.
Mệnh đề 2.3.2 Với p là một số nguyên tố, số căn nguyên thủy theo môđun p bằng 1 khi và chỉ khi p = 2 hoặc p = 3.
Chứng minh Nếu p = 2 thì rõ ràng 1 là căn nguyên thủy duy nhất theo môđun
2 Nếup lẻ thìp = 2 α k + 1với α và k là các số nguyên dương, trong đó k lẻ Theo
Hệ quả 2.2.6, số căn nguyên thủy theo môđun p bằng ϕ(ϕ(p)) = ϕ(p − 1) = ϕ(2 α )ϕ(k).
Nếu số căn nguyên thủy theo môđun p là 1, thì ϕ(2α) = 1 và ϕ(k) = 1, suy ra α = 1 và k = 1 theo Mệnh đề 2.3.1, do k lẻ nên p = 3 Ngược lại, với p = 3, 2 là căn nguyên thủy duy nhất theo môđun 3, từ đó ta có điều cần chứng minh.
Kết quả sau chỉ ra rằng ta chỉ cần xét trường hợp số căn nguyên thủy là một số chẵn.
Mệnh đề 2.3.3 Nếu p là một số nguyên tố lớn hơn 3 thì số căn nguyên thủy theo môđun p là số chẵn.
Chứng minh Vìp > 3 nênp − 1 > 2 Do đó, theo Hệ quả 2.2.6 và Mệnh đề 2.3.1, số căn nguyên thủy theo môđun p là ϕ(ϕ(p)) = ϕ(p − 1) là số chẵn.
Trường hợp số căn nguyên thủy bằng t = 2 r với r ≥ 1 ta có các kết quả sau.
Mệnh đề 2.3.4 Với p là một số nguyên tố, số căn nguyên thủy theo môđun p bằng 2 khi và chỉ khi p = 5 hoặc p = 7.
Chúng ta có thể giả thiết rằng p là số lẻ, với p = 2αk + 1, trong đó α và k là các số nguyên dương và k là số lẻ Theo Hệ quả 2.2.6, số căn nguyên thủy theo môđun p được tính bằng ϕ(ϕ(p)) = ϕ(p - 1) = ϕ(2α)ϕ(k) Do đó, nếu số căn nguyên thủy theo môđun p là 2, thì ϕ(2α) = 2 và ϕ(k) = 1, hoặc ngược lại, ϕ(2α) = 1 và ϕ(k) = 2.
Nếu ϕ(2 α ) = 2 và ϕ(k) = 1, ta suy ra α = 2 và k = 1, do k lẻ, nên p = 5 Nếu ϕ(2 α ) = 1 và ϕ(k) = 2, ta có α = 1 và k = 3, do k lẻ, do đó p = 7 Đối với p = 5, số căn nguyên thủy theo môđun 5 là ϕ(ϕ(5)) = ϕ(4) = 2; với p = 7, số căn nguyên thủy theo môđun 7 là ϕ(ϕ(7)) = ϕ(6) = 2 Điều này chứng minh tính đúng đắn của giả thuyết.
Mệnh đề 2.3.5 Với p là một số nguyên tố, số căn nguyên thủy theo môđun p bằng 4 khi và chỉ khi p = 11 hoặc p = 13.
Có thể giả thiết p là một số lẻ, với p = 2αk + 1, trong đó α và k là các số nguyên dương và k là số lẻ Theo Hệ quả 2.2.6, số căn nguyên thủy theo môđun p được tính bằng ϕ(ϕ(p)) = ϕ(p − 1) = ϕ(2α)ϕ(k) Nếu số căn nguyên thủy theo môđun p bằng 4, thì theo Mệnh đề 2.3.1, sẽ có ba trường hợp xảy ra.
Trong bài viết này, chúng ta xem xét ba trường hợp liên quan đến hàm số phi Trường hợp 1 chỉ ra rằng nếu ϕ(2 α ) = 1 và ϕ(k) = 4, thì α = 1 và số ước nguyên tố lẻ phân biệt của k không vượt quá hai, dẫn đến k = 5 và p = 11 Trường hợp 2 cho thấy nếu ϕ(2 α ) = 2 và ϕ(k) = 2, thì α = 2 và k = 3, từ đó p = 13 Cuối cùng, trong trường hợp 3, khi ϕ(2 α ) = 4 và ϕ(k) = 1, ta suy ra α = 3 và k = 1, nhưng điều này mâu thuẫn với giả thiết ban đầu.
Ngược lại, với p = 11 rõ ràng số căn nguyên thủy theo môđun p là ϕ(ϕ(11)) = ϕ(10) = ϕ(2)ϕ(5) = 4, với p = 13 rõ ràng số căn nguyên thủy theo môđun p là ϕ(ϕ(13)) = ϕ(12) = ϕ(4)ϕ(3) = 2.2 = 4 Vậy ta có điều phải chứng minh.
Bằng cách áp dụng các lập luận tương tự như trong các Mệnh đề 2.3.4 và 2.3.5, chúng ta có thể chứng minh rằng luôn tồn tại số nguyên tố p sao cho số căn nguyên thủy theo môđun p bằng 2^r với 3 ≤ r ≤ 9 Ví dụ, với p = 31, ta có ϕ(ϕ(31)) = ϕ(30) = ϕ(2^3) = 2^3; với p = 41, ϕ(ϕ(41)) = ϕ(40) = ϕ(2^4) = 2^4; với p = 97, ϕ(ϕ(97)) = ϕ(96) = ϕ(2^5) = 2^5; với p = 193, ϕ(ϕ(193)) = ϕ(192) = ϕ(2^6) = 2^6; với p = 409, ϕ(ϕ(409)) = ϕ(408) = ϕ(2^3) = 2^7; với p = 769, ϕ(ϕ(769)) = ϕ(768) = ϕ(2^8) = 2^8; và với p = 1361, ϕ(ϕ(1361)) = ϕ(1360) = ϕ(2^4) = 2^9.
Tuy nhiên với t = 2 10 ta có kết quả sau.
Mệnh đề 2.3.6 khẳng định rằng không có số nguyên tố nào có số căn nguyên thủy là 2^10 Để chứng minh, giả sử tồn tại một số nguyên tố p thỏa mãn điều kiện này và giả thiết p là số lẻ, tức p = 2^α k + 1 với α và k là các số nguyên dương, trong đó k lẻ Theo Hệ quả 2.2.6, số căn nguyên thủy theo môđun p sẽ là ϕ(ϕ(p)) = ϕ(p - 1) = ϕ(2^α)ϕ(k) Do đó, theo Mệnh đề 2.3.1, nếu số căn nguyên thủy theo môđun p là 2^10 thì sẽ có mười trường hợp phát sinh.
Trường hợp 1: ϕ(2 α ) = 1 và ϕ(k) = 2 10 = 4.256, từ đó suy ra α = 1 và k = 5.257 = 1285 Do đó p = 2571, mâu thuẫn với giả thiết p là số nguyên tố.
Trong trường hợp 2, ta có ϕ(2 α ) = 2 và ϕ(k) = 2^9 = 2.256, từ đó suy ra α = 2 và k = 3.257 = 771, dẫn đến p = 3085, điều này mâu thuẫn với giả thiết p là số nguyên tố Trong trường hợp 3, ϕ(2 α ) = 2^2 và ϕ(k) = 2^8 = 256, suy ra α = 3 và k = 257, do đó p = 2057, cũng mâu thuẫn với giả thiết p là số nguyên tố.
Trường hợp 4: ϕ(2 α ) = 2 3 và ϕ(k) = 2 7 = 2.4.16, từ đó suy ra α = 4 và k = 3.5.17 = 255 Do đó p = 4081, mâu thuẫn với giả thiết p là số nguyên tố.
Trường hợp 5: ϕ(2 α ) = 2 4 vàϕ(k) = 2 6 = 4.16, từ đó suy raα = 5và k = 5.17 = 51.
Do đó p = 2721, mâu thuẫn với giả thiết p là số nguyên tố.
Trường hợp 6: ϕ(2 α ) = 2 5 vàϕ(k) = 2 5 = 2.16, từ đó suy raα = 6và k = 3.17 = 51.
Do đó p = 3265, mâu thuẫn với giả thiết p là số nguyên tố.
Trường hợp 7: ϕ(2 α ) = 2 6 và ϕ(k) = 2 4 = 16, từ đó suy ra α = 7 và k = 17 Do đó p = 2177, mâu thuẫn với giả thiết p là số nguyên tố.
Trường hợp 8: ϕ(2 α ) = 2 7 và ϕ(k) = 2 3 = 2.4, từ đó suy ra α = 8 và k = 3.5 = 15.
Do đó p = 3841, mâu thuẫn với giả thiết p là số nguyên tố.
Trường hợp 9: ϕ(2 α ) = 2 8 và ϕ(k) = 2 2 = 4, từ đó suy ra α = 9 và k = 5 Do đó p = 2561, mâu thuẫn với giả thiết p là số nguyên tố.
Trong trường hợp 10, ta có ϕ(2 α ) = 2 9 và ϕ(k) = 2, từ đó suy ra α = 10 và k = 3, dẫn đến p = 3073, điều này mâu thuẫn với giả thiết p là số nguyên tố Do đó, kết luận này xác nhận điều cần chứng minh Đối với các số nguyên tố Fermat, ta có kết quả như sau.
Mệnh đề 2.3.7 Cho số chẵn k = 2 2 n −1 với 1 ≤ n ≤ 4 Khi đó số nguyên tố Fermat p = F n = 2 2 n + 1 có số căn nguyên thủy là k.
Chứng minh Với 1 ≤ n ≤ 4 ta có ϕ(ϕ(F n )) = ϕ(ϕ(2 2 n + 1)) = ϕ(2 2 n ) = 2 2 n −1 = k.
Do đó, theo Hệ quả 2.2.6, số nguyên tố p = F n = 2 2 n + 1 có số căn nguyên thủy là k.
Bây giờ ta xét trường hợp số căn nguyên thủy bằng t = 2q r với r nguyên dương và q là một số nguyên tố lẻ.
Mệnh đề 2.3.8 Với p là một số nguyên tố, số căn nguyên thủy theo môđun p bằng 6 khi và chỉ khi p = 19.
Chứng minh rằng nếu p là số nguyên tố lẻ, ta có thể giả thiết p = 2αk + 1 với α và k là số nguyên dương, trong đó k lẻ Theo Hệ quả 2.2.6, số căn nguyên thủy theo môđun p bằng ϕ(ϕ(p)) = ϕ(p − 1) = ϕ(2α)ϕ(k) Nếu số căn nguyên thủy theo môđun p là 6, thì ϕ(2α) = 1 và ϕ(k) = 6 = 2.3, dẫn đến α = 1 và k có duy nhất một ước nguyên tố lẻ, suy ra k = 7 hoặc k = 9 Do đó, p có thể là 15 hoặc 19, nhưng p = 15 mâu thuẫn với giả thiết p là số nguyên tố Ngược lại, với p = 19, số căn nguyên thủy theo môđun p là ϕ(ϕ(19)) = ϕ(18) = ϕ(2)ϕ(3²) = 6, từ đó hoàn tất chứng minh.
Mệnh đề 2.3.9 Không tồn tại số nguyên tố p nào có số căn nguyên thủy theo môđun p bằng 18.
Giả sử tồn tại một số nguyên tố p thỏa mãn điều kiện đề bài và giả định p là số lẻ, ta có p = 2αk + 1 với α và k là số nguyên dương, trong đó k lẻ Theo Hệ quả 2.2.6, số căn nguyên thủy theo môđun p bằng ϕ(ϕ(p)) = ϕ(p − 1) = ϕ(2α)ϕ(k) Nếu số căn nguyên thủy theo môđun p là 18, thì ϕ(2α) = 1 và ϕ(k) = 18 = 2.3^2, dẫn đến α = 1 và k có duy nhất một ước nguyên tố do k lẻ, suy ra k = 19 hoặc k = 27 Từ đó, p = 39 hoặc p = 55, mâu thuẫn với giả thiết p là số nguyên tố Vậy ta đã chứng minh điều cần chứng minh.
Theo mệnh đề 2.3.10, nếu q là một số nguyên tố có dạng q = 3m + 1 với m là một số nguyên dương, thì không tồn tại số nguyên tố nào có căn nguyên thủy là 2q^α, trong đó α là một số nguyên dương.
Giả sử tồn tại số nguyên tố lẻ p thỏa mãn điều kiện đề bài, ta có thể viết p = 2βk + 1 với β và k là các số nguyên dương, trong đó k lẻ Theo Hệ quả 2.2.6, số căn nguyên thủy theo môđun p là ϕ(ϕ(p)) = ϕ(p − 1) = ϕ(2β)ϕ(k) Nếu số căn nguyên thủy theo môđun p là 2qα, thì từ Mệnh đề 2.3.1, ta có ϕ(2β) = 1 và ϕ(k) = 2qα, dẫn đến β = 1 và k chỉ có duy nhất một ước nguyên tố lẻ.
Giả sử k không phải là số nguyên tố, thì k có thể biểu diễn dưới dạng k = n γ, với n là một số nguyên tố lẻ và γ là một số nguyên dương lớn hơn hoặc bằng 2 Từ đó, ta tính được ϕ(k) = (n − 1)n γ−1, dẫn đến q = n = 3, điều này mâu thuẫn với q = 3m + 1 Do đó, k phải là một số nguyên tố, suy ra k = 2q α + 1 Hơn nữa, vì q ≡ 1 (mod 3), nên q α cũng tương đương 1 (mod 3), dẫn đến 2q α ≡ 2 (mod 3) Kết quả là k ≡ 0 (mod 3), điều này mâu thuẫn với việc k là một số nguyên tố Vì vậy, điều cần chứng minh đã được xác nhận.
Mối liên hệ giữa thặng dư bậc hai với căn nguyên thủy
Trong phần này, chúng tôi trình bày một số kết quả liên quan đến mối liên hệ giữa thặng dư bậc hai và căn nguyên thủy theo môđun của một số nguyên tố Các kết quả này được tham khảo từ các tài liệu [1], [2], [4].
Mệnh đề 2.4.1 Chop là một số nguyên tố lẻ Các căn nguyên thủy theo môđun p là các bất thặng dư bậc hai theo môđun p.
Chứng minh Lấy g là một căn nguyên thủy theo môđun p Khi đó g p−1 2 6≡ 1 (mod p).
Mặt khác, theo Định lý 1.1.20 ta có g p
Do đó g là bất thặng dư bậc hai theo môđun p.
Từ Mệnh đề 2.4.1, ta thấy rằng số các căn nguyên thủy theo môđun p không vượt quá p − 1
2 Sau đây là một số trường hợp đặc biệt.
Mệnh đề 2.4.2 Cho p là một số nguyên tố lẻ Số căn nguyên thủy theo môđun p bằng p − 1
2 khi và chỉ khi p = 2 α + 1 với α là một số nguyên dương.
Chứng minh Vì p lẻ nên p = 2 α k + 1 với α và k là các số nguyên dương, trong đó k lẻ Nếu k = 1 thì p = 2 α + 1 Theo Hệ quả 2.2.6, số căn nguyên thủy theo môđun p bằng ϕ(ϕ(p)) = ϕ(p − 1) = ϕ(2 α ) = 2 α−1 = p − 1
2 Nếu k ≥ 3 thì số căn nguyên thủy theo môđun p bằng ϕ(ϕ(p)) = ϕ(p − 1) = ϕ(2 α )ϕ(k) ≤ 2 α−1 (k − 1) < 2 α−1 k = p − 1
2 Vậy ta có điều phải chứng minh.
Theo Mệnh đề 1.2.1, nếu p = 2 α + 1 là một số nguyên tố thì α = 2 n với n là một số nguyên không âm Khi đó p = F n là một số nguyên tố Fermat.
Mệnh đề 2.4.3 Cho p là một số nguyên tố lẻ Số căn nguyên thủy theo môđun p bằng p − 1
2 − 1 khi và chỉ khi p = 2q + 1 với q là một số nguyên tố lẻ.
Chứng minh Nếu p = 2q + 1 với q là một số nguyên tố lẻ thì theo Hệ quả 2.2.6 số căn nguyên thủy theo môđun p bằng ϕ(ϕ(p)) = ϕ(p − 1) = ϕ(2q) = ϕ(2)ϕ(q) = q − 1 = p − 1
Vì p là một số nguyên tố lẻ, nên p có thể được biểu diễn dưới dạng p = 2αk + 1, với α và k là các số nguyên dương và k là số lẻ Khi k = 1, theo Mệnh đề 2.4.2, số căn nguyên thủy modulo p - 1 sẽ được xác định.
2 Do đó k ≥ 3 Khi đó theo Mệnh đề 2.4.2, số căn nguyên thủy theo môđun p bằng ϕ(ϕ(p)) = ϕ(p − 1) = ϕ(2 α k) = ϕ(2 α )ϕ(k) ≤ 2 α−1 (k − 1) = p − 1
Vì số căn nguyên thủy theo môđun p bằng p − 1
2 − 1 cho nên từ đó suy ra α = 1 và k là số nguyên tố Do đó p = 2q + 1 với q là một số nguyên tố lẻ Vậy ta có điều phải chứng minh.
Mệnh đề 2.4.4 chỉ ra rằng với p là một số nguyên tố và p = 2q + 1, trong đó q là một số nguyên tố lẻ, thì số -1 là một bất thặng dư bậc hai theo môđun p nhưng không phải là căn nguyên thủy theo môđun p.
= (−1) p−1 2 = (−1) q = −1 do q là số lẻ cho nên −1 là một bất thặng dư bậc hai theo môđun p Vì (−1) 2 ≡ 1 (mod p)và 2 < p − 1 (do p ≥ 7) nên−1 không là căn nguyên thủy theo môđun p.
Mệnh đề 2.4.5 Cho p là một số nguyên tố lẻ Số căn nguyên thủy theo môđun p bằng p − 1
2 − 2 khi và chỉ khi p = 4q + 1 với q là một số nguyên tố lẻ.
Chứng minh Nếu p = 4q + 1 với q là một số nguyên tố lẻ thì theo Hệ quả 2.2.6 số căn nguyên thủy theo môđun p bằng ϕ(ϕ(p)) = ϕ(p − 1) = ϕ(4q) = ϕ(4)ϕ(q) = 2(q − 1) = p − 1
Vì p là một nguyên tố lẻ, ta có thể biểu diễn p dưới dạng p = 2αk + 1, với α và k là các số nguyên dương và k là số lẻ Nếu k = 1, theo Mệnh đề 2.4.2, số căn nguyên thủy theo môđun p sẽ bằng p - 1.
2 Do đó k ≥ 3 Khi đó theo Mệnh đề 2.4.2, số căn nguyên thủy theo môđun p bằng ϕ(ϕ(p)) = ϕ(p − 1) = ϕ(2 α k) = ϕ(2 α )ϕ(k) ≤ 2 α−1 (k − 1) = p − 1
Vì số căn nguyên thủy theo môđun p bằng p − 1
2 − 2 cho nên từ đó suy ra α = 2 và k là số nguyên tố Do đó p = 4q + 1 với q là một số nguyên tố lẻ Vậy ta có điều phải chứng minh.
Mệnh đề 2.4.6 nêu rằng nếu p là một số nguyên tố có dạng p = 4q + 1, với q là một số nguyên tố lẻ, thì số 2q là một bất thặng dư bậc hai theo môđun p, nhưng không phải là căn nguyên thủy theo môđun p.
8 = (−1) q 2 (2q+1) = −1 do q là số lẻ nên 2 q là một bất thặng dư bậc hai theo môđun p Vì
(2 q ) 4 ≡ 2 p−1 ≡ 1 (mod p) và 4 < p − 1 (do p ≥ 13) nên 2 q không là căn nguyên thủy theo môđun p Vậy ta có điều phải chứng minh.
Mệnh đề 2.4.7 chỉ ra rằng với p là một số nguyên tố có dạng p = 4q + 1, trong đó q là một số nguyên tố lẻ, thì số −2q sẽ là một bất thặng dư bậc hai theo môđun p, nhưng không phải là căn nguyên thủy theo môđun p.
Để chứng minh rằng −2 q không phải là căn nguyên thủy theo môđun p, ta bắt đầu từ phương trình 8 = (−1) q 3 (2q+1) = −1, với q là số lẻ Do đó, −2 q là một bất thặng dư bậc hai theo môđun p Ta có (−2 q ) 4 ≡ 2 p−1 ≡ 1 (mod p) và vì 4 < p − 1 (với p ≥ 13), điều này dẫn đến kết luận rằng −2 q không thể là căn nguyên thủy theo môđun p.
Vìplẻ cho nên rõ ràng 2 q 6≡ −2 q (mod p) Như vậy, số nguyên tốp = 4q + 1 với q là một số nguyên tố lẻ có p − 1
2 bất thặng dư bậc hai theo môđun pnhưng chỉ có p − 1
2 − 2 căn nguyên thủy theo môđun p, và hai số không phải căn nguyên thủy là 2 q và −2 q
Điều kiện để một số là căn nguyên thủy
Trong phần này, chúng tôi đề cập đến các điều kiện cần thiết để xác định một số nguyên cho trước là một căn nguyên thủy theo môđun của một số nguyên tố Các kết quả được trình bày dựa trên tài liệu tham khảo [1], [2], [4].
Mệnh đề 2.5.1 Cho p = 2q + 1 là một số nguyên tố với q là một số nguyên tố. Nếu q có dạng 4k + 1 với k ≥ 1 thì 2 là một căn nguyên thủy theo môđun p.
Chứng minh rằng t là cấp của 2 theo môđun p, tức là 2^t ≡ 1 (mod p) Theo định lý Fermat, ta có 2^ϕ(p) ≡ 1 (mod p), từ đó suy ra t phải chia hết cho ϕ(p) = p - 1 = 2q Điều này dẫn đến kết luận rằng t thuộc tập hợp {1, 2, q, 2q}.
Nếu t = 1 thì khi đó 2 ≡ 1 (mod p), điều này không thể xảy ra Nếu t = 2 thì khi đó 4 ≡ 1 (mod p), điều này không thể xảy ra Nếu t = q thì khi đó
Theo định lý, nếu 2q ≡ 1 (mod p) và 2 p−1 2 ≡ 1 (mod p), với p = 2q + 1 = 2(4k + 1) + 1 = 8k + 3, thì theo Mệnh đề 1.1.23, số 2 là một bất thặng dư bậc hai theo môđun p Tuy nhiên, theo Định lý 1.1.20, ta có 2 p−1 2 6≡ 1 (mod p), điều này dẫn đến mâu thuẫn Kết luận, t = 2q = p − 1 = ϕ(p) cho thấy 2 là một căn nguyên thủy theo môđun p.
Một số trường hợp số nguyên tố p thỏa mãn điều kiện của Mệnh đề 2.5.1 là p = 11, 59, 83,
Mệnh đề 2.5.2 Cho p = 2q + 1 là một số nguyên tố với q là một số nguyên tố.Nếu q có dạng 4k + 3 với k ≥ 1 thì −2 là một căn nguyên thủy theo môđun p.
Chứng minh Gọitlà cấp của −2theo môđunp Khi đó (−2) t ≡ 1 (mod p) Theo định lý Fermat, ta luôn có (−2) ϕ(p) ≡ 1 (mod p) Do đó, theo Mệnh đề 2.1.3 ta có t | ϕ(p) = p − 1 = 2q từ đó suy ra t ∈ {1, 2, q, 2q}.
Nếu t = 1 hoặc t = 2, thì −2 không thể đồng dư với 1 theo môđun p Khi t = q, ta có (−2) q ≡ 1 (mod p), dẫn đến (−2) p−1 2 ≡ 1 (mod p) Với p = 2q + 1 = 8k + 7, theo Mệnh đề 1.1.23, −2 là bất thặng dư bậc hai theo môđun p Tuy nhiên, theo Định lý 1.1.20, (−2) p−1 2 6≡ 1 (mod p), gây ra mâu thuẫn Do đó, t = 2q = p − 1 = ϕ(p), chứng tỏ −2 là căn nguyên thủy theo môđun p.
Một số trường hợp số nguyên tố p thỏa mãn điều kiện của Mệnh đề 2.5.2 là p = 23, 47, 87,
Mệnh đề 2.5.3 nêu rõ rằng, với p là một số nguyên tố có dạng 4k + 1 (với k là số nguyên dương), nếu g là một căn nguyên thủy theo môđun p thì −g cũng sẽ là một căn nguyên thủy theo môđun p.
Chứng minh Giả sử trái lại,−g không là căn nguyên thủy theo môđun p Gọi t là cấp của −g theo môđun p Khi đó t | ϕ(p) = 4k và 1 ≤ t < 4k Khi đó
Nếu t là số chẵn thì 1 ≡ g t (mod p), điều này dẫn đến mâu thuẫn vì cấp của g là 4k > t.
Nếu t là số lẻ thì 1 ≡ −g t (mod p) hay 1 ≡ (−g t ) 2 = g 2t (mod p) từ đó suy ra 4k | 2t hay 2k | t, điều này mâu thuẫn vì t lẻ Vậy ta có điều phải chứng minh.
Thuật toán tìm căn nguyên thủy
Các kết quả trong mục này được tham khảo từ các tài liệu [1], [2], [4].
Thuật toán vét cạn, hay còn gọi là thuật toán "ngây thơ", là một phương pháp tính toán dựa trên định nghĩa căn nguyên thủy, không loại trừ bất kỳ trường hợp nào trong quá trình thực hiện Các bước thực hiện của thuật toán này rất đơn giản và dễ hiểu.
Bước 2: Với mỗi số g với 2 ≤ g ≤ m − 1, (g, m) = 1, tính i r = g r (mod m) với
Bước 3: Số g nào không cho kết quải r = 1thì số g đó là một căn nguyên thủy theo môđun m.
Thuật toán vét cạn có thể được cải tiến dựa vào kết quả sau.
Mệnh đề 2.6.1 nêu rõ rằng với m là một số nguyên dương và g là một số nguyên sao cho (g, m) = 1, thì g được coi là một căn nguyên thủy theo môđun m nếu và chỉ nếu g ϕ(m) p 6≡ 1 (mod m) với mọi p là ước nguyên tố của ϕ(m).
Chứng minh Giả sử g là một căn nguyên thủy theo môđun m Khi đó với p là một ước nguyên tố bất kỳ của ϕ(m) ta có ϕ(m) p < ϕ(m) Cho nên g ϕ(m) p 6≡ 1 (mod m).
Nếu g không phải là căn nguyên thủy theo môđun m, thì l là cấp của g và là một ước thực sự của ϕ(m) theo Mệnh đề 2.1.3 Giả sử ϕ(m) = lq với q ≥ 2, trong đó p là một ước nguyên tố của q Nếu k là một số nguyên, ta có g ϕ(m) p ≡ g lk ≡ g l k.
≡ 1 (mod m), trái giả thiết Vậy ta có điều phải chứng minh.
Trong thuật toán cải tiến từ thuật toán vét cạn số phép tính được giảm bớt nhờ vào Mệnh đề 2.6.1 Các bước thực hiện như sau.
Bước 1: Ta tính ϕ(m) rồi phân tích thành tích các thừa số nguyên tố ϕ(m) = k
Bước 2: Với mỗi số nguyên dương 1 < g < m và nguyên tố cùng nhau với m, tính g ϕ(m) pi (mod m) với i = 1, , k.
Theo Mệnh đề 2.6.1, nếu số g cho k kết quả đều khác 1, thì g được xem là căn nguyên thủy Số căn nguyên thủy theo môđun m, nếu tồn tại, sẽ là ϕ(ϕ(m)) trong hệ thặng dư thu gọn {1, g, g², , g^(ϕ(m)−1)} theo môđun m.
Hiện nay, thuật toán này được xem là nhanh nhất để tìm căn nguyên thủy, nhưng số lượng phép tính cần thực hiện vẫn lớn, dẫn đến việc thuật toán sẽ mất nhiều thời gian khi giá trị m tăng cao.
Sau đây là bảng căn nguyên thủy dương bé nhất của 229 số tự nhiên đầu tiên, trong đó g là căn nguyên thủy dương bé nhất của số nguyên dương m. m g m g m g m g m g m g m g m g
Bảng căn nguyên thủy dương bé nhất của 229 số tự nhiên đầu tiên.
MỘT SỐ ỨNG DỤNG CỦA CĂN NGUYÊN THỦY
Chương này khám phá ứng dụng của căn nguyên thủy trong nghiên cứu các phương trình đồng dư bậc cao và trong lĩnh vực mã khóa công khai Bên cạnh đó, chương cũng trình bày các giải pháp cho một số bài toán số học thường gặp trong các đề thi học sinh giỏi thông qua việc sử dụng căn nguyên thủy.
Chỉ số
Các kết quả trong mục này được tham khảo từ các tài liệu [1], [2], [4].
Cho m là một số nguyên dương với căn nguyên thủy g Theo Mệnh đề 2.2.3, tập hợp {1, g, g², , g^(ϕ(m)−1)} tạo thành một hệ thặng dư thu gọn theo môđun m Với a là một số nguyên bất kỳ thỏa mãn (a, m) = 1, tồn tại một số nguyên r sao cho a ≡ g^r (mod m) với 0 ≤ r ≤ ϕ(m) − 1 Số r này được gọi là chỉ số của a theo cơ số g theo môđun m, ký hiệu là ind_g(a).
Sau đây là một số tính chất cơ bản của chỉ số.
Mệnh đề 3.1.2 Cho m là một số nguyên dương có căn nguyên thủy là g Khi đó
(i) ind g (ab) ≡ ind g (a) + ind g (b) (mod ϕ (m)) với (a, m) = 1 và (b, m) = 1. (ii) ind g a k
≡ k ind g (a) (mod ϕ (m)) với (a, m) = 1 và k nguyên tùy ý.
(iii) (Công thức đổi cơ số) Với h là một căn nguyên thủy tùy ý theo môđun m ind g (a) ≡ ind g (h) ind h (a) (mod ϕ (m)) với (a, m) = 1.
(i) Giả sử (a, m) = 1 và (b, m) = 1 Đặt r = ind g (a) và s = ind g (b) Khi đó ta có ab ≡ g r g s ≡ g r+s (mod m) Từ đó suy ra r + s ≡ ind g (ab) (mod ϕ (m)), hay ind g (ab) ≡ ind g (a) + ind g (b) (mod ϕ (m)).
(ii) Giả sử (a, m) = 1 Đặt r = ind g (a) Khi đó ta có a k ≡ g rk (mod m) Từ đó suy ra rk ≡ ind g a k
Giả sử h là căn nguyên thủy theo môđun m, với r = ind h (a) và s = ind g (h) Ta có a ≡ h r ≡ g rs (mod m), từ đó suy ra rs ≡ ind g (a) (mod ϕ (m)) Điều này dẫn đến ind g (a) ≡ ind g (h) ind h (a) (mod ϕ (m)).
Điều kiện để một số là thặng dư bậc k
Trong phần này, chúng tôi giới thiệu ứng dụng của căn nguyên thủy và chỉ số để xác định điều kiện cho một số trở thành thặng dư bậc k theo một môđun nhất định Ứng dụng này được áp dụng vào nghiên cứu các phương trình đồng dư bậc cao Các kết quả trong phần này được tham khảo từ tài liệu [1], [2], [4].
Mệnh đề 3.2.1 nêu rõ rằng, với m là một số nguyên dương, g là căn nguyên thủy theo môđun m, và a là số nguyên với điều kiện (a, m) = 1, ta ký hiệu d = (k, ϕ(m)) Khi đó, a được coi là thặng dư bậc k theo môđun m nếu và chỉ nếu d chia hết cho chỉ số ind g (a).
Giả sửa là một thặng dư bậc theo môđun m, tồn tại số nguyên x sao cho x k ≡ a (mod m) Từ đó suy ra a ϕ(m) d ≡ x ϕ(m)k d ≡ 1 (mod m) Đặt r = ind g (a), chúng ta có các kết luận quan trọng liên quan đến tính chất của số nguyên này.
Vì g có cấp ϕ(m) theo môđun m, suy ra ϕ(m) | ϕ(m)r d, hay d | r = ind g (a) Ngược lại, nếu d | ind g (a), tức là ind g (a) = td với t nguyên, thì d = (k, ϕ(m)), do đó d = uk + vϕ(m) với u, v là các số nguyên Từ đó, ta có a ≡ g td ≡ g tuk + tvϕ(m) ≡ g tuk g ϕ(m) tv.
(mod m). Điều này chứng tỏ rằnga là một thặng dư bậck theo môđun m Ta có điều phải chứng minh.
Số thặng dư bậc k theo môđun m được xác định là ϕ(m) d, với d = (k, ϕ(m)) Theo Mệnh đề 3.2.1, số a được coi là thặng dư bậc k theo môđun m nếu và chỉ nếu tồn tại một số nguyên dương t sao cho ind g (a) = td.
1 ≤ t = ind g (a) d ≤ ϕ(m) d cho nên có ϕ(m) d thặng dư bậc k theo môđun m Vậy ta có điều phải chứng minh.
Mệnh đề 3.2.3 nêu rằng, với m là một số nguyên dương và g là một căn nguyên thủy theo môđun m, nếu a là một thặng dư bậc k theo môđun m và (a, m) = 1, thì phương trình đồng dư x^k ≡ a (mod m) có đúng d nghiệm, với d = (k, ϕ(m)) Chứng minh cho thấy, do a là thặng dư bậc k theo môđun m, tồn tại số nguyên x sao cho (x, m) = 1 và x^k ≡ a (mod m) Từ đó, tồn tại số nguyên u.
Để giải phương trình x k ≡ a (mod m), ta có 1 ≤ u ≤ ϕ(m) sao cho x ≡ g u (mod m) Theo Mệnh đề 3.2.1, tồn tại số nguyên t với 1 ≤ t ≤ ϕ(m) d, dẫn đến a ≡ g td (mod m) Từ đó, ta có g ku ≡ x k ≡ a ≡ g td (mod m), suy ra ku ≡ td (mod ϕ(m)) Theo Định lý 1.1.7, phương trình này có đúng d nghiệm theo môđun ϕ(m) Do đó, x k ≡ a (mod m) có đúng d nghiệm.
Trao đổi khóa Diffie - Hellman
Các kết quả trong mục này được tham khảo từ các tài liệu [1], [2], [3], [4], [7].
Mã hóa khóa công khai là phương pháp bảo mật thông tin sử dụng một cặp khóa, trong đó một khóa được công khai và một khóa được giữ kín Khi gửi thông tin mật, bên gửi mã hóa dữ liệu bằng khóa công khai của bên nhận, và bên nhận sẽ giải mã bằng khóa riêng của mình Hệ thống mã hóa này được giới thiệu lần đầu tiên vào năm 1976 bởi Whitfield Diffie và Martin Hellman thông qua phương pháp trao đổi khóa Diffie - Hellman.
Quá trình trao đổi khóa Diffie - Hellman được xây dựng dựa vào lý thuyết về căn nguyên thủy, và diễn ra như sau.
Bước 1: Người A và người B cùng chọn một số chung là p và một căn nguyên thủy theo môđun p là g Hai con số này là khóa công khai.
Bước 2: Người A chọn một số a bất kỳ và tính α ≡ g a (mod p) rồi gửi cho người
B số α này Số a này là khóa bí mật của riêng người A.
Bước 3: Người B chọn số b và tính một số β ≡ g b (mod p) rồi gửi cho người A số β này Số b này là khóa bí mật của riêng người B.
Bước 4: Người A tính được β a ≡ (g b ) a ≡ γ (mod p), đồng thời người B cũng tính được α b ≡ (g a ) b ≡ γ (mod p).
Hai người A và B đã thành công trong việc thu được khóa bí mật chung là γ Để minh chứng cho nguyên tắc bảo mật trong quá trình trao đổi khóa này, chúng ta cần xem xét bảng thông tin liên quan.
Biết biết Biết biết Biết biết p, g - p, g - p, g - a α ≡ g a (mod p) - α a α a b β b β ≡ g b (mod p) - β b γ ≡ β a (mod p) - γ ≡ α b (mod p) - - γ
Ví dụ 3.3.1 Người A và người B cùng chọn một số chung làp = 59 và một căn nguyên thủy theo môđun 59 là g = 13.
Người A bí mật chọn số a = 3 và gửi cho người B số α = 14 (vì 13 3 ≡ 14 (mod 59)).
Người B bí mật chọn số b = 10 và gửi cho người A số β = 36 (vì 13 10 ≡ 36 (mod 59)).
Từ đó, người A tính được γ ≡ 36 3 ≡ 46 (mod 59), người B cũng tính được γ ≡ 14 10 ≡ 46 (mod 59) Vậy hai người A và B thu được khóa bí mật chung là
Để xác định khóa bí mật γ, bên thứ ba chỉ có thể truy cập bốn thông tin là p, q, α và β Do đó, cần tìm chỉ số của α và β theo cơ số g trong môđun p bằng cách giải phương trình đồng dư g^x ≡ α (mod p), đây chính là bài toán logarit rời rạc.
Sau đây là một số thuật toán để giải bài toán logarit rời rạc.
Thuật toán vét cạn là phương pháp tìm nghiệm của phương trình g x ≡ α (mod p) với g là căn nguyên thủy theo môđun p Cấp của g theo môđun p là p − 1, điều này cho phép suy ra rằng phương trình có nghiệm trong khoảng từ 1 đến p − 2 Để tìm nghiệm, ta sẽ thử các giá trị x từ 1 đến p − 2, và cần thực hiện ít nhất p − 2 phép tính để giải quyết phương trình này.
Thuật toán Baby-step Giant-step do Daniel Shanks phát triển nhằm tối ưu hóa phương pháp vét cạn trong việc tìm nghiệm của phương trình Thay vì quét toàn bộ p giá trị, thuật toán tách x thành i + jm với m = [(p − 1) 1/2] Các giá trị i và j được gán từ 0 đến m, sau đó so sánh g^mj với αg^−i theo mô-đun p Nếu hai giá trị này bằng nhau, ta có thể tính được nghiệm x cần tìm từ i và j tương ứng Để giải phương trình, thuật toán yêu cầu thực hiện 2[(p − 1) 1/2 + 1] phép tính, chưa tính đến thao tác so sánh.
Thuật toán Pohlig - Hellman: Vì p là số nguyên tố nên p − 1 có thể phân tích thành tích các thừa số nguyên tố như sau p − 1 =
Xét phương trình đồng dư Y = ∏ (q_i^α_i) với q_i là các ước nguyên tố phân biệt và a_i là các số nguyên dương Dựa vào định lý Trung Hoa về phần dư, nếu ta tính được x_i (mod q_i^α_i) với 1 ≤ i ≤ S, thì có thể suy ra x (mod p - 1).
Trước tiên, lập bảng giá trị của g k(p−1) qi (mod p) với k = 0, 1, , q − 1 Tiếp theo, tính x 0i + x 1i q + + x (α−1)i q α−1 ≡ log g b (mod q i α i ) với 1 ≤ x ji ≤ q i − 1 Khi đó g p−1 qi x 0i
≡ α p−1 qi (mod p) từ đó suy ra g p−1 qi x 1i
Do đó ta tính được các giá trị x i mod q i α i với 1 ≤ i ≤ S Ta cần tính ít nhất
(α i q i + q i ) phép tính, chưa bao gồm các bước nâng bậc, tìm phần tử nghịch đảo, nhân và lập bảng.
Các thuật toán được đánh giá chỉ khả thi với số p không quá lớn Tuy nhiên, nếu p - 1 có thể phân tích thành các thừa số nguyên tố nhỏ, thuật toán Pohlig - Hellman sẽ là giải pháp hiệu quả.
Người ta thường chọn số nguyên tố p có dạng 2q + 1, với q là số nguyên tố rất lớn Thực tế, số p thường có hơn 300 chữ số, trong khi số a và b có trên 100 chữ số Ngay cả với những máy tính hiện đại nhất hiện nay, việc giải quyết bài toán này trong thời gian ngắn vẫn là một thách thức lớn.
Một số bài toán
Mục này trình bày giải pháp cho một số bài toán số học trong các đề thi học sinh giỏi, áp dụng phương pháp căn nguyên thủy Các kết quả được tham khảo từ tài liệu [1], [2], [4], [6].
Bài 1 (Romania TST 1996) Tìm các số nguyên tố p, q thỏa mãn α 3pq ≡ α (mod 3pq) với mọi số nguyên α.
Lời giải Xét số nguyên α với (3pq, α) = 1, ta có α 3pq−1 ≡ 1 (mod 3pq).
Nếu α = 2 là một căn nguyên thủy theo môđun 3 thì
2 2 ≡ 1 (mod 3) và 2 3pq−1 ≡ 1 (mod 3) từ đó suy ra 2 | 3pq − 1 Do đó p, q là số lẻ.
Nếu α là một căn nguyên thủy theo môđun p (do p là một số nguyên tố) thì α p−1 ≡ 1 (mod p) và α 3pq−1 ≡ 1 (mod p) từ đó suy ra p − 1 | 3pq − 1.
Nếu α là căn nguyên thủy theo môđun q, với q là số nguyên tố, thì có hai điều kiện: α q−1 ≡ 1 (mod q) và α 3pq−1 ≡ 1 (mod q), từ đó suy ra rằng q − 1 chia hết cho 3pq − 1 Điều này dẫn đến việc 3qp − 1 chia cho q − 1, cho thấy rằng 3p − 1 cũng là một số nguyên Giả sử không mất tính tổng quát, ta có thể đặt p ≤ q.
Nếu p = q thì 3p − 1 q − 1 = 3 + 2 q − 1 Vậy p = q = 3 Thử lại, với α = 2, ta có
2 9 ≡ 8 6≡ 2(mod9), điều này mâu thuẫn với giả thiết Như vậyp < q Vìp ≤ q − 2 cho nên
Vậy 3p − 1 q − 1 = 1 hoặc 3p − 1 q − 1 = 2 Tuy nhiên rõ ràng 3p − 1 q − 1 6= 1 Thật vậy vì
3p − 1 = q − 1nên q = 3p, trái với giả thiết q là số nguyên tố Khi đó, 3p − 1 q − 1 = 2 hay q = 3p + 1
3qp − 1 p − 1 = 3q + 3q − 1 p − 1 là số nguyên từ đó suy ra 3q − 1 p − 1 cũng là số nguyên Do đó
2 + 10 2(p − 1) là số nguyên Vì p − 1 | 10 cho nên p = 11, q = 17 hoặc p = 3, q = 5.
Với p = 11 và q = 17, ta tính được 3qp = 561 Xét số nguyên α sao cho (561, α) = 561, từ đó suy ra α phải chia hết cho 561, tức là α ≡ 0 (mod 561), đáp ứng yêu cầu đề bài Tiếp theo, xét số nguyên α với 1 < (561, α) = d < 561, ta có tổng cộng sáu trường hợp cần xem xét.
Trường hợp 1: Nếu d = 3 thì (11.17, α) = 1 Khi đó α 10 ≡ 1 (mod 11) và α 16 ≡ 1
(mod 17) từ đó suy ra α 80 ≡ 1 (mod 11.17) hay α 560 ≡ 1 (mod 11.17) Do đó α 561 ≡ α (mod 11.17) và α 561 ≡ 0 ≡ α (mod 3) Vậy α 561 ≡ α (mod 561).
Trường hợp 2: Nếu d = 11 thì (3.17, α) = 1 Khi đó α 2 ≡ 1 (mod 3) và α 16 ≡ 1 (mod 17)từ đó suy raα 16 ≡ 1 (mod 3.17)hayα 560 ≡ 1 (mod 3.17) Do đóα 561 ≡ α (mod 3.17) và α 561 ≡ 0 ≡ α (mod 11) Vậy α 561 ≡ α (mod 561).
Trường hợp 3: Nếu d = 17 thì (3.11, α) = 1 Khi đó α 2 ≡ 1 (mod 3) và α 10 ≡ 1 (mod 11)từ đó suy raα 10 ≡ 1 (mod 3.11)hayα 560 ≡ 1 (mod 3.11) Do đóα 561 ≡ α (mod 3.11) và α 561 ≡ 0 ≡ α (mod 17) Vậy α 561 ≡ α (mod 561).
Trường hợp 4: Nếu d = 3.11 thì (17, α) = 1 Khi đó α 16 ≡ 1 (mod 17) từ đó suy ra α 560 ≡ 1 (mod 17) Do đó α 561 ≡ α (mod 17) và α 561 ≡ 0 ≡ α (mod 3.11) Vậy α 561 ≡ α (mod 561).
Trường hợp 5: Nếu d = 3.17 thì (11, α) = 1 Khi đó α 10 ≡ 1 (mod 11) từ đó suy ra α 560 ≡ 1 (mod 11) Do đó α 561 ≡ α (mod 11) và α 561 ≡ 0 ≡ α (mod 3.17) Vậy α 561 ≡ α (mod 561).
Trường hợp 6: Nếu d = 11.17 thì (3, α) = 1 Khi đó α 2 ≡ 1 (mod 3) từ đó suy ra α 560 ≡ 1 (mod 3) Do đó α 561 ≡ α (mod 3) và α 561 ≡ 0 ≡ α (mod 11.17) Vậy α 561 ≡ α (mod 561) Vậy cặp số p, q thỏa mãn yêu cầu đề bài.
Xét số nguyên α với (561, α) = 1 Khi đó α 560 = (α 2 ) 280 ≡ 1 (mod 3), α 560 = (α 10 ) 56 ≡ 1 (mod 11)và α 560 = (α 16 ) 35 ≡ 1 (mod 17) Từ đó suy raα 560 ≡ 1 (mod 561) hay α 561 ≡ α (mod 561), thỏa mãn yêu cầu đề bài.
Nếu p = 3 và q = 5, thì 3qp = 45 Khi xét α = 2, ta có 2 45 ≡ 17 (mod 45), điều này mâu thuẫn với giả thiết ban đầu Do đó, đáp án của bài toán là p = 11 và q = 17 Việc áp dụng căn nguyên thủy vào bài toán này giúp tìm ra các đặc trưng của p và q một cách nhanh chóng và hiệu quả.
Bài 2 (Putnam 1994) Cho số nguyên không âm a bất kỳ, đặt n a = 101a − 100.2 a
Chứng minh rằng với 0 ≤ a, b, c, d ≤ 99 và n a + n b ≡ n c + n d (mod 10100) thì
Lời giải Theo giả thiết, ta có n a + n b ≡ n c + n d (mod 10100) từ đó suy ra
Khi đó a + b ≡ c + d (mod 100) và 2 a + 2 b ≡ 2 c + 2 d (mod 101) Mặt khác, vì 2 là một căn nguyên thủy theo môđun 101 cho nên 2 a+b ≡ 2 c+d (mod 101) Do đó
Vì 101 là một số nguyên tố cho nên 2 c ≡ 2 a (mod 101) hoặc 2 c ≡ 2 b (mod 101).
Do a và b có vai trò như nhau từ đó suy ra không mất tính tổng quát, giả sử
Nếu 2c ≡ 2a (mod 101) thì 2b ≡ 2d (mod 101), dẫn đến a ≡ c (mod 100) và b ≡ d (mod 100) Do đó, {a, b} = {c, d} với điều kiện 0 ≤ a, b, c, d ≤ 99 Tương tự, nếu 2c ≡ 2b (mod 101), ta cũng có {a, b} = {c, d} Điều này chứng minh được kết quả cần thiết.
Bình luận Từ giả thiết, ta thấy được mấu chốt của bài toán nằm ở 10100 = 101.100 và ϕ(101) = 100 Đặc biệt, số 2 là một căn nguyên thủy theo môđun 101.
Từ các dữ kiện này, dễ thấy việc áp dụng căn nguyên thủy là phương pháp nên được chọn để giải quyết bài toán.
Bài 3 (USEMO lần thứ nhất) Chứng minh rằng với mọi số nguyên tố p, tồn tại số nguyên dương n sao cho:
Lời giải Theo Định lý Euler, với mọi số nguyên tố p và số nguyên a, (a, p) = 1 ta có a p−1 ≡ 1 (mod p) từ đó suy ra a p(p−1)−a+1 ≡ a p−a (mod p) Khi đó p
Vìp là một nguyên tố, nên tồn tại số nguyên theo môđun p với hệ thặng dư {1, g, g², , g^(p−2)} Điều này có nghĩa là với mọi số nguyên a trong khoảng 1 ≤ a ≤ p − 1, luôn tồn tại một số nguyên j (1 ≤ j ≤ p − 1) sao cho a ≡ g^j (mod p).
Vậy ta chọn n = −2020p(p − 1) khi đó 1 n + 2 n−1 + + n 1 ≡ 2020 (mod p) theo yêu cầu của đề bài.
Bài toán gặp khó khăn do số liệu lớn và phức tạp, nhưng việc áp dụng căn nguyên thủy, cụ thể là ứng dụng chỉ số, đã giúp đơn giản hóa đáng kể các số liệu ban đầu.
Bài 4 (Hungary - Israel Math Competition 2009) Cho số nguyên tố p. Tìm tất cả các số nguyên dương k sao cho
Vì p là một số nguyên tố, tồn tại g là một căn nguyên thủy theo môđun p, dẫn đến g^(p−1) ≡ 1 (mod p) Tập hợp {1, g, g², , g^(p−2)} tạo thành một hệ thặng dư thu gọn theo môđun p Từ đó, ta suy ra rằng S_k ≡ 1 + g^k + + g^((p−2)k) (mod p).
Nếu p − 1 | k thì g k ≡ 1 (mod p) Do đó S k ≡ 1 + 1 + + 1 = p − 1 (mod p), điều này mâu thuẫn với giả thiết.
Nếu p − 1- k thì g k 6≡ 1 (mod p) và g (p−1)k ≡ 1 (mod p) Khi đó
S k ≡ g (p−1)k − 1 g k − 1 ≡ 0 (mod p), thỏa mãn yêu cầu đề bài.
Như vậy, k là các số nguyên dương không chia hết cho p − 1.
Bài toán số 4 đã giúp chúng tôi giải quyết bài toán số 3 một cách hiệu quả Việc áp dụng căn nguyên thủy, đặc biệt là ứng dụng chỉ số, đã làm cho số liệu ban đầu trở nên đơn giản hơn rất nhiều.
Bài 5 (Iran TST 2013) Cho p là một số nguyên tố lẻ, cần chứng minh rằng tồn tại một số tự nhiên x sao cho x và 4x đều là căn nguyên thủy theo môđun p Do p là nguyên tố, tồn tại số nguyên dương g là căn nguyên thủy theo môđun p, với (g, p) = 1 và {1, g, g², , g^(p−2)} là hệ thặng dư thu gọn theo môđun p Có số nguyên dương r, 0 ≤ r ≤ p − 2 sao cho g^r ≡ 2 (mod p), từ đó suy ra 2r ≡ 4 (mod p) Gọi p₁, p₂, , pₗ là các ước nguyên tố phân biệt của p − 1 Đối với mỗi số k nguyên dương với 1 ≤ k ≤ l, đặt mₖ là số nguyên dương sao cho mₖ 6≡ 0 (mod pₖ) và mₖ 6≡ −2r (mod pₖ).
Theo Định lý phần dư Trung hoa, tồn tại một số tự nhiên m sao cho m ≡ m k (mod p k ), ∀1 ≤ k ≤ l.
Vì m và m + 2r không chia hết cho p, nên chúng là nguyên tố cùng nhau với p - 1 Điều này dẫn đến việc các số m, 2m, 3m, , (p - 2)m và (m + 2r), 2(m + 2r), 3(m + 2r), , (p - 2)(m + 2r) đều không chia hết cho p - 1 Hơn nữa, do g là căn nguyên thủy theo môđun p, ta có g^m, g^(2m), , g^((p−2)m) không đồng dư 1 (mod p) và g^(m + 2r), g^(2(m + 2r)), , g^((p−2)(m + 2r)) cũng không đồng dư 1 (mod p).
Do đóg m và g m+2r là các căn nguyên thủy theo môđunp Vậy chọn sốx = g m và 4x ≡ 4g m ≡ g m+2r (mod p) Khi đó, x và 4x là các căn nguyên thủy theo môđun p cần tìm.
Bài toán đề cập đến vấn đề căn nguyên thủy, yêu cầu sử dụng các tính chất liên quan đến căn nguyên thủy của x Đồng thời, cần áp dụng chỉ số để chứng minh rằng 4x cũng thỏa mãn điều kiện là một căn nguyên thủy.
Trong bài 6 của danh sách rút gọn IMO 1997, chúng ta cần chứng minh rằng nếu một cấp số cộng vô hạn với các số nguyên dương chứa ít nhất một số chính phương và một số lập phương, thì cấp số này cũng phải chứa một lũy thừa sáu của một số nguyên.
Trong bài toán này, chúng ta xem xét một cấp số cộng gồm các số nguyên dương có dạng a + qn, với a, q, n là các số nguyên, trong đó 0 ≤ a ≤ q − 1 và q, n là các số dương Theo giả thiết, tồn tại các số nguyên dương x và y sao cho x^2 = a + qn x và y^3 = a + qn y, với n x và n y là các số nguyên dương Do đó, ta có x^2 ≡ a (mod q) và y^3 ≡ a (mod q).
Xét a = 0 và chọn x^2 = q^2 với n_x = q, y^3 = q^3 với n_y = q^2, cùng với dãy số có z^6 = q^6 với n_z = q^5, ta cần chứng minh điều này Xem xét trường hợp 1 ≤ a ≤ q − 1, khi q = 1, dãy số nguyên sẽ vô hạn và trường hợp này là hiển nhiên đúng Nếu q = p^α với p là số nguyên tố và α là số nguyên dương, chúng ta sẽ có hai trường hợp cần phân tích.
