BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC QUY NHƠN

NGUYỄN THIÊN THỦY

MỘT SỐ VẤN ĐỀ VỀ CĂN NGUYÊN THỦY
VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ PHƯƠNG PHÁP TỐN SƠ CẤP

Bình Định - 2021


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC QUY NHƠN

NGUYỄN THIÊN THỦY

MỘT SỐ VẤN ĐỀ VỀ CĂN NGUYÊN THỦY
VÀ ỨNG DỤNG

Chuyên ngành

:

Phương pháp toán sơ cấp

Mã số

:

8460113

Người hướng dẫn: TS. TRẦN ĐÌNH LƯƠNG


i

Lời cam đoan
Tôi xin cam đoan mọi kết quả của đề tài “MỘT SỐ VẤN ĐỀ VỀ CĂN
NGUYÊN THỦY VÀ ỨNG DỤNG ” là cơng trình nghiên cứu của tơi dưới
sự hướng dẫn của TS. Trần Đình Lương và chưa từng được cơng bố trong bất
cứ cơng trình khoa học nào khác cho tới thời điểm này.
Các nội dung và kết quả sử dụng trong luận văn đều có trích dẫn và chú thích
nguồn gốc. Nếu có điều gì gian lận, tơi xin chịu trách nhiệm về luận văn của
mình.

Bình Định, ngày 26 tháng 07 năm 2021
Học viên thực hiện đề tài

Nguyễn Thiên Thủy


ii

Mục lục

Mở đầu

1


1 KIẾN THỨC CHUẨN BỊ

4

1.1

Một số kiến thức cơ bản về số học . . . . . . . . . . . . . . . . . .

4

1.2

Một số kết quả chuẩn bị . . . . . . . . . . . . . . . . . . . . . . . .

8

2 CĂN NGUYÊN THỦY

12

2.1

Cấp của phần tử . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.2

Căn nguyên thủy theo môđun m . . . . . . . . . . . . . . . . . . . 14

2.3


Số nguyên tố với số căn nguyên thủy cho trước . . . . . . . . . . . 19

2.4

Mối liên hệ giữa thặng dư bậc hai với căn nguyên thủy . . . . . . 27

2.5

Điều kiện để một số là căn nguyên thủy . . . . . . . . . . . . . . . 31

2.6

Thuật tốn tìm căn ngun thủy . . . . . . . . . . . . . . . . . . . 33

3 MỘT SỐ ỨNG DỤNG CỦA CĂN NGUYÊN THỦY

36

3.1

Chỉ số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.2

Điều kiện để một số là thặng dư bậc k . . . . . . . . . . . . . . . . 37

3.3

Trao đổi khóa Diffie - Hellman . . . . . . . . . . . . . . . . . . . . 39


3.4

Một số bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

Kết luận

60


iii

Danh mục tài liệu tham khảo

60


1

Mở đầu

Vào năm 1801, nhà toán học người Đức Carl Friedrich Gauss đưa ra khái niệm
căn nguyên thủy trong cuốn sách Những nghiên cứu số học, tên tiếng Latinh là
Disquisitiones Arithmeticae, ở Đề mục số 57. Đây là phần mà ông đúc kết và
phát triển từ một số kết quả nghiên cứu của nhà toán học L. Euler và bản thân.
Từ Đề mục số 56, ơng nói rằng hai nhà toán học J. H. Lambert và L. Euler đều
biết đến căn nguyên thủy, nhưng ông là người đầu tiên đưa ra bằng chứng chặt
chẽ về sự tồn tại của các căn nguyên thủy theo môđun nguyên tố n.
Khái niệm căn nguyên thủy phải trải qua một quãng đường dài mới được
hình thành. Mở đầu là sự xuất hiện của Định lý Fermat nhỏ, tiếp đó Định lý
Euler được đưa ra, tổng quát cho Định lý Fermat nhỏ trước đó. Từ đây, nhờ

có sự tồn tại của hàm phi Euler, khái niệm cấp của phần tử được hình thành.
Cuối cùng, dựa trên mối tương quan giữa cấp của phần tử và hàm phi Euler,
định nghĩa về căn nguyên thủy chính thức được xây dựng. Sự xuất hiện của căn
nguyên thủy đóng góp vơ cùng lớn khơng chỉ cho tốn học mà còn ứng dụng
vào thực tiễn, đặc biệt là lĩnh vực mật mã học.
Luận văn này nhằm nghiên cứu một số vấn đề về căn nguyên thủy như: số
nguyên tố với số căn nguyên thủy cho trước, mối liên hệ giữa thặng dư bậc hai
với căn nguyên thủy, điều kiện để một số là căn ngun thủy và thuật tốn tìm
căn ngun thủy. Bên cạnh đó, luận văn cịn đưa ra một số ứng dụng của căn
nguyên thủy vào việc nghiên cứu các phương trình đồng dư bậc cao và vấn đề


2

mã khóa cơng khai. Ngồi ra, luận văn cũng trình bày lời giải một số bài toán
số học xuất hiện trong các đề thi học sinh giỏi bằng cách sử dụng căn nguyên
thủy.
Luận văn "Một số vấn đề về căn nguyên thủy và ứng dụng" bao gồm: Mở
đầu, Nội dung, Kết luận và Tài liệu tham khảo. Nội dung của luận văn gồm ba
chương.
Chương 1: Kiến thức chuẩn bị
Chương này trình bày một số kiến thức cơ bản về số học như: quan hệ chia
hết, đồng dư thức và một số kết quả chuẩn bị được dùng trong luận văn.
Chương 2: Căn nguyên thủy
Chương này trình bày một số vấn đề về căn nguyên thủy theo môđun là một
số nguyên dương như: các tính chất cơ bản, điều kiện tồn tại căn nguyên thủy,
vấn đề số căn nguyên thủy, mối liên hệ giữa thặng dư bậc hai và căn nguyên
thủy, điều kiện để một số cho trước là căn nguyên thủy theo môđun là một số
nguyên tố. Trong chương này cũng trình bày một thuật tốn tìm căn ngun
thủy theo môđun là một số nguyên dương cho trước.

Chương 3: Một số ứng dụng của căn nguyên thủy
Chương này trình bày ứng dụng của căn nguyên thủy vào việc nghiên cứu
các phương trình đồng dư bậc cao, ứng dụng của căn ngun thủy vào vấn đề
mã khóa cơng khai. Trong chương này cũng trình bày lời giải một số bài tốn
số học xuất hiện trong các đề thi học sinh giỏi bằng cách sử dụng căn nguyên
thủy.
Luận văn được hoàn thành nhờ sự hướng dẫn và giúp đỡ tận tình của thầy
hướng dẫn TS. Trần Đình Lương, Trường Đại học Quy Nhơn. Nhân dịp này
tơi xin bày tỏ sự kính trọng và lòng biết ơn sâu sắc đến Thầy đã giúp đỡ tôi


3

trong suốt quá trình học tập và thực hiện luận văn. Chúng tôi xin gửi lời cảm
ơn đến quý Ban lãnh đạo Trường Đại học Quy Nhơn, Phòng Đào tạo Sau Đại
học, Khoa Toán và Thống kê cùng quý Thầy Cơ giáo giảng dạy lớp Cao học
Phương pháp tốn sơ cấp Khóa 22 đã dày cơng giảng dạy trong suốt khóa học,
tạo điều kiện thuận lợi cho tơi trong q trình học tập và thực hiện đề tài.
Nhân đây chúng tôi cũng xin chân thành cảm ơn sự hỗ trợ về mặt tinh thần
của gia đình, bạn bè đã ln tạo mọi điều kiện giúp đỡ để tơi hồn thành tốt
khóa học và luận văn này.
Mặc dù luận văn được thực hiện với sự nỗ lực cố gắng hết sức của bản thân,
nhưng do điều kiện thời gian có hạn, trình độ kiến thức và kinh nghiệm nghiên
cứu cịn hạn chế nên luận văn khó tránh khỏi những thiếu sót. Chúng tơi rất
mong nhận được những góp ý của q Thầy Cơ để luận văn được hồn thiện
hơn.


4


Chương 1

KIẾN THỨC CHUẨN BỊ
Chương này trình bày một số kiến thức cơ bản về số học như: quan hệ chia
hết, đồng dư thức và một số kết quả chuẩn bị được dùng trong luận văn.

1.1

Một số kiến thức cơ bản về số học

Mục này trình bày một số kiến thức cơ bản về số học. Các kết quả trong mục
này được tham khảo từ các tài liệu [1], [2], [4].
Định lý 1.1.1. Cho a và b là hai số nguyên với b 6= 0. Khi đó tồn tại duy nhất
các số nguyên q và r sao cho a = bq + r trong đó 0 ≤ r < |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à một ướ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à với d0 là một ước chung bất kỳ
của a và b thì d0 | d. Ta quy ước dùng ký hiệu (a, b) để 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.
(i) Nếu b | a, c | b thì c | a.
(ii) Nếu b | a, c | a và (b, c) = 1 thì bc | a.


5

(iii) Nếu c | ab và (b, c) = 1 thì c | a.
(iv) Nếu c | a và c | b thì c | a ± b.


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 6= 1 được gọi là số nguyên tố nếu nó chỉ có hai ước là 1 và chính
nó.
Định lý 1.1.4. (Đị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 được thành một tích các số nguyên tố, và sự phân tích này là duy
nhất nếu khơng kể đến thứ tự các nhân tử.
Theo Định lý cơ bản của số học mọi số nguyên n > 1 đều có thể biểu diễn
được dưới dạng
n = pα1 1 pα2 2 · · · pαk k

trong đó p1 , p2 , . . . , pk là các số nguyên tố phân biệt, và α1 , α2 , . . . , αk 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. Cho m là một số nguyên dương. Hai số nguyên a và b được
gọi là đồng dư với nhau theo môđun m, và 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, n là các số nguyên dương. Nếu a ≡ b (mod m)
và c ≡ d (mod m) thì:
(i) a ± c ≡ b ± d (mod m).
(ii) ac ≡ bd (mod m).
(iii) an ≡ bn (mod m).
(iv) (a + b)n ≡ bn (mod m).
(v) Nếu d là một ước chung của a, b và m thì

a
b
m
≡ (mod ).
d
d

d


6

Định lý 1.1.7. Cho m là một số nguyên dương. Phương trình đồng dư bậc nhất
ax + b ≡ 0 (mod m), trong đó a, b là các số nguyên, có nghiệm khi và chỉ khi d | b

với d = (a, m). Trong trường hợp phương trình có nghiệm, nó có d nghiệm theo
mơđun m là
m
m
m
, x0 + 2 , . . . , x0 + (d − 1)
d
d
d
a
b
m
trong đó x0 là một nghiệm của phương trình đồng dư x + ≡ 0 (mod ).
d
d
d
x0 , x0 +

Định lý 1.1.8. (Định lý Thặng dư Trung Hoa). Cho m1 , m2 , . . . , mk là các số
nguyên dương ngun tố cùng nhau từng đơi một. Khi đó hệ phương trình đồng
dư
x ≡ ai (mod mi ) với i = 1, 2, . . . , k


có nghiệm duy nhất theo môđun m1 m2 · · · mk .
Định lý 1.1.9. Cho p là một số nguyên tố, và f (x) = an xn + . . . + a1 x + a0 , n ≥ 0,
là một đa thức với hệ số nguyên với p - an . Khi đó phương trình f (x) ≡ 0 (mod p)
có khơng q n nghiệm (kể cả bội).
Định nghĩa 1.1.10. Ta ký hiệu ϕ(m) là số các lớp thặng dư (theo môđun m)
nguyên tố cùng nhau với m. Hàm ϕ(m) được gọi là Hàm Euler.
Ta có thể hiểu ϕ(m) như là số các số nguyên k với 1 ≤ k < m sao 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 (m1 , m2 ) = 1 thì ϕ(m1 m2 ) = ϕ(m1 )ϕ(m2 ).
Định lý 1.1.12. Với m là một số nguyên dương lớn hơn 1

Y
1−

ϕ(m) = m

p|m

trong đó p là các ước nguyên tố của m.

1
p


7

Đị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, ta có kết quả sau.
Định lý 1.1.14. (Định lý Fermat) Cho p là một số nguyên tố. Nếu a là một số
nguyên bất kỳ thì ap ≡ a (mod p).
Định nghĩa 1.1.15. Cho tập A = {a1 , a2 , . . . , an } là tập hợp có n số nguyên,
A là một hệ thặng dư đầy đủ theo môđun n khi và chỉ khi ai 6≡ aj (mod n) với
1 ≤ i < j ≤ n.

Định nghĩa 1.1.16. Cho tập B = {b1 , b2 , . . . , bk } 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);
(ii) (bi , n) = 1 với 1 ≤ i ≤ k ;
(iii) bi 6≡ bj (mod n) với 1 ≤ i < j ≤ k .

Định nghĩa 1.1.17. Cho m là một số tự nhiên lớn hơn 1. Với a là một số
nguyên, (a, m) = 1, nếu tồn tại số nguyên x sao cho xk ≡ a (mod m) thì ta gọi a
là một thặng dư bậc k theo môđun m; trái lại, ta gọi a là một bất thặng dư bậc
k theo môđun m.

Định nghĩa 1.1.18. (Ký hiệu Legendre). Cho p > 2 là một số nguyên tố, và
a ∈ Z với p - a. Ta đặt

 
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
   
a
b
Rõ ràng là nếu a ≡ b (mod p) thì
=
.
p

p

p−1
thặng dư bậc
2
p−1
hai theo mơđun p, và
bất thặng dư bậc hai theo môđun p. Hơn nữa, các
2

Định lý 1.1.19. Cho p > 2 là một số nguyên tố. Có đúng


8

phần tử

12 , 22 , . . . ,


 p − 1 2
2

tạo thành một tập đầy đủ các thặng dư bậc hai theo

môđun p.
Định lý 1.1.20. (Tiêu chuẩn Euler). Cho p > 2 là một số nguyên tố. Khi đó
với mọi số nguyên a với p - a,
a

p−1
2

 
a
p

≡

(mod p).

Từ Định lý 1.1.20 ta có kết quả sau.
    
ab
a
b
=
.
Mệnh đề 1.1.21. Nếu p - ab thì
p


p

p

Mệnh đề 1.1.22. Cho p là một số nguyên tố lẻ.
 
p−1
−1
= (−1) 2 .
 p
p2 −1
2
(ii)
= (−1) 8 .
p

(i)

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).

1.2

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ì α = 2n với n là số nguyên
không âm.
Chứng minh. Giả sử trái lại, đặt α = 2n m với n, m là các số ngun khơng âm,
trong đó m lẻ và m ≥ 3. Khi đó


9
n

p = 2α +1 = 22

m +1

n

= (2m +1)2(2

n

= (2m + 1)(2(2

−1)m −(2m +1)2(2n −2)m +. . .−(2m +1)2m +(2m +1)

−1)m

n

− 2(2

−2)m


+ . . . − 2m + 1)

Vì 1 < 2m + 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.
n

Ký hiệu Fn = 22 + 1 với n ≥ 0. Fermat đưa ra giả thiết rằng Fn là số
nguyên tố với mọi n. Tuy nhiên, vào năm 1732, Euler đã chỉ ra rằng F5 =
5

22 +1 = 641.6700417 phủ 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à F0 = 3, F1 =
5, F2

17,

=

F3 = 257, F4 = 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 đó
Cpk ≡ 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ó

Cpk =

p!
p(p − 1)!
=
.
k!(p − k)!
k!(p − k)!

Vì p là số nguyên tố và Cpk nguyên nên



(p − 1)!
p,
k!(p − k)!



= 1. Do đó p | Cpk . 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ì ap ≡ bp (mod pα+1 ).

Chứng minh. Giả sử a = kpα + b với k ∈ Z. Khi đó
ap − bp = (kpα + b)p − bp = k p ppα + Cp1 k p−1 p(p−1)α + . . . + Cpp−2 k 2 pα+1 + Cpp−1 kpα
=

pα




k p p(p−1)α

+ Cp1 k p−1 p(p−2)α

+ . . . + Cpp−2 k 2 p + Cpp−1 k



.


10

Vì p | Cpk với mọi k = 1, 2, . . . , p − 1 theo Mệnh đề 1.2.2, cho nên từ đó suy ra
ap − bp chia hết cho pα+1 , hay ap ≡ bp (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

≡ 1 + apα−1 (mod pα ).

Chứng minh. Ta chứng minh đồng dư thức bằng cách quy nạp theo α. Với α = 2,
đồng dư thức là hiển nhiên. Giả sử đồng dư thức đúng với α ≥ 2, ta chứng minh
đồng dư thức đúng với α + 1, nghĩa là

(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
(1 + ap)p

α−1

≡ (1 + apα−1 )p (mod pα+1 ).

Ta lại có
(1 + apα−1 )p = 1 + Cp1 apα−1 + Cp2 a2 p2(α−1) + . . . + ap pp(α−1)
=

1 + apα

+ pα




Cp2 a2 p2(α−1)−α

+ . . . + Cpp−1 ap−1 p(p−1)(α−1)−α

+ ap pp(α−1)−α



≡ 1 + apα (mod pα+1 ).

Do p ≥ 3 và α ≥ 2 cho nên p(α − 1) − α ≥ 3(α − 1) − α = 2α − 3 ≥ 1. Vì p | Cpk 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 5b 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α .


11

Chứng minh. Bằng phép chứng minh quy nạp ta có thể chứng tỏ được rằng
α−3

52

α−2

52


≡ 1 + 2α−1 (mod 2α ). Do đó 52

α−2

≡ 1 + 2α (mod 2α+1 ). Cho nên

≡ 1 (mod 2α ). Từ đó suy ra cấp của 5 theo môđun 2α là 2α−2 .

Bây giờ ta chứng minh rằng các số (−1)a 5b với 0 ≤ a ≤ 1 và 0 ≤ b ≤ 2α−2
là không đồng dư với nhau từng đôi một theo môđun 2α . Thật vậy, giả sử
0

0

(−1)a 5b ≡ (−1)a 5b (mod 2α ). Khi đó a và a0 cùng tính chẵn lẻ, nên a = a0 . Do
0

đó 5b ≡ 5b (mod 2α ). Vì cấp của 5 theo mơđun 2α là 2α−2 , nên từ đó suy ra
b ≡ b0 (mod 2α−2 ), do đó b = b0 . Vậy ta có điều phải chứng minh.

Mệnh đề 1.2.6. Với α ≥ 3, các số (−1)a (57 )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
(57 )2

α−3

(57 )2

α−2


≡ 1 + 2α−1 (mod 2α ). Do đó (57 )2

α−2

≡ 1 + 2α (mod 2α+1 ). Cho nên

≡ 1 (mod 2α ). Từ đó suy ra cấp của 57 theo mơđun 2α là 2α−2 .

Bây giờ ta chứng minh rằng các số (−1)a (57 )b với 0 ≤ a ≤ 1 và 0 ≤ b ≤ 2α−2
là không đồng dư với nhau từng đôi một theo môđun 2α . Thật vậy, giả sử
0

0

(−1)a (57 )b ≡ (−1)a (57 )b (mod 2α ). Khi đó a và a0 cùng tính chẵn lẻ, nên a = a0 .
0

Do đó (57 )b ≡ (57 )b (mod 2α ). Vì cấp của 57 theo mơđun 2α là 2α−2 , nên từ đó
suy ra b ≡ b0 (mod 2α−2 ), do đó b = b0 . Vậy ta có điều phải chứng minh.


12

Chương 2

CĂN NGUYÊN THỦY
Chương này trình bày một số vấn đề về căn nguyên thủy theo môđun là một
số nguyên dương như: các tính chất cơ bản, điều kiện tồn tại căn nguyên thủy,
vấn đề số căn nguyên thủy, mối liên hệ giữa thặng dư bậc hai và căn nguyên

thủy, điều kiện để một số cho trước là căn nguyên thủy theo môđun là một số
nguyên tố. Trong chương này cũng trình bày một thuật tốn tìm căn ngun
thủy theo môđun là một số nguyên dương cho trước.

2.1

Cấp của phần tử

Trong mục này chúng tơi trình bày một số tính chất của cấp một phần tử theo
một môđun cho trước 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ả 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, a là một số nguyên. Theo Định lý 1.1.13,
ta có aϕ(m) ≡ 1 (mod m), (a, m) = 1. Số nguyên dương l bé nhất sao cho
al ≡ 1 (mod m) được gọi là cấp của a theo mơđun m, và kí hiệu là ordm (a).

Ví dụ 2.1.1. Cho m = 10, a = 7. Tính tốn trực tiếp ta có được
71 ≡ 7 (mod 10), 72 ≡ 9 (mod 10), 73 ≡ 3 (mod 10), 74 ≡ 1 (mod 10).

Do đó ord10 (7) = 4.


13

Nhận xét 2.1.2. Ta có nhận xét rằng điều kiện (a, m) = 1 trong định nghĩa của
cấp một phần tử a theo môđun m là cần thiết. Thật vậy, cho m = 10, a = 4. Khi
đó phương trình đồng dư 4l ≡ 1 (mod 10) rõ ràng là vô nghiệm. Cho nên không
tồn tại cấp của 4 theo môđun 10.
Mệnh đề 2.1.3. Cho m 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ỳ, at ≡ 1 (mod m) khi và chỉ khi ordm (a) | t.
Chứng minh. Đặt l = ordm (a). Giả sử l | t, hay t = ql với q ∈ Z. Khi đó

at ≡ (al )q ≡ 1 (mod m).

Ngược lại, giả sử at ≡ 1 (mod m), và t = ql + r với q, r ∈ Z, 0 ≤ r < l. Khi
đó 1 ≡ at ≡ aql+r ≡ (al )q ar ≡ ar (mod m). Mà l = ordm (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. Cho m 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ì
ordm (ak ) =

ordm (a)
.
(ordm (a), k)

Chứng minh. Vì (a, m) = 1 cho nên (ak , m) = 1. Ký hiệu l = ordm (a), d = (k, l).
Giả sử k = dk 0 , l = d.l0 với k 0 , l0 ∈ Z. Ta sẽ chứng minh ordm (ak ) = l0 . Thật vậy,
ta có
0

0

0

0

(ak )l ≡ (adk )l ≡ (al )k ≡ 1 (mod m).

Lấy t ∈ Z bất kỳ sao cho (ak )t ≡ 1 (mod m). Khi đó 1 ≡ (ak )t ≡ akt (mod m). Vì
ordm (a) = l cho nên từ đó suy ra l | kt, hay dl0 | dk 0 t. Do đó l0 | k 0 t. Vì (k 0 , l0 ) = 1


cho nên từ đó suy ra l0 | t. Điều này chứng tỏ rằng ordm (ak ) = l0 . Vậy ta có điều
phải 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,


14

(a, m) = (b, m) = 1. Nếu (ordm (a), ordm (b)) = 1 thì
ordm (ab) = ordm (a)ordm (b).

Chứng minh. Vì (a, m) = 1 và (b, m) = 1 nên (ab, m) = 1. Đặt l = ordm (a),

k k
l
k = ordm (b), e = ordm (ab). Vì (ab)lk = al
b
≡ 1 (mod m) cho nên e | lk . Mặt
khác ta có ake ≡ ake bke ≡ (ab)ke ≡ 1 (mod m) như vậy l | ke. Vì (l, k) = 1 nên từ
đó suy ra l | e. Lập luận tương tự ta cũng có k | e. Từ đó suy ra lk | e. Vậy e = lk ,
và ta có điều phải chứng minh.
Kết quả sau đây sẽ được sử dụng về sau.
Mệnh đề 2.1.6. Cho 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 sao cho q h | p − 1. Khi đó tồn tại một số nguyên a sao cho
ordp (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ó


p−1
p−1
nghiệm. Vì
< p − 1 cho nên tồn tại số nguyên u với
q
q
p−1
p−1
1 ≤ u ≤ p − 1 sao cho u q 6≡ 1 (mod p). Đặt a = u qh . Ta sẽ chứng minh rằng

không quá

ordp (a) = q h .
h

Thật vậy, vì aq ≡ up−1 ≡ 1 (mod p) cho nên từ đó suy ra ordp (a) | q h . Nếu
ordp (a) 6= q h thì ordp (a) | q h−1 . Khi đó ta có
u

p−1
q

≡ aq

h−1

≡ 1 (mod p),

điều này trái với tính chất của u. Do đó ordp (a) = q h , và ta có điều phải chứng
minh.


2.2

Căn ngun thủy theo mơđun m

Trong mục này chúng tơi trình bày một số tính chất cơ bản của căn nguyên
thủy và kết quả chính về điều kiện tồn tại căn nguyên thủy theo môđun là một


15

số nguyên dương cho trước. Các kết quả trong mục này được tham khảo từ các
tài liệu [1], [2], [4].
Định nghĩa 2.2.1. Cho m là một số nguyên dương và g là một số nguyên,
(g, m) = 1. Số nguyên g được gọi là một căn nguyên thủy theo môđun m nếu
ordm (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
21 ≡ 2 (mod 9), 22 ≡ 4 (mod 9), 23 ≡ 8 (mod 9),
24 ≡ 7 (mod 9), 25 ≡ 5 (mod 9), 26 ≡ 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. Cho m là một số nguyên dương. Số nguyên g với (g, m) = 1
là một căn nguyên thủy theo môđun m khi và chỉ khi {1, g, g 2 , . . . , g ϕ(m)−1 } lập
thành một hệ thặng dư thu gọn theo môđun m.
Chứng minh. Rõ ràng nếu {1, g, g 2 , . . . , g ϕ(m−1) } là hệ thặng dư thu gọn theo
mơđun m thì g là một căn ngun thủy theo môđun m. Ngược lại, giả sử g là một
căn nguyên thủy theo môđun m. Ta chứng minh rằng hệ {1, g, g 2 , . . . , g ϕ(m)−1 } là
hệ thặng dư thu gọn theo mơđun m. Vì (g, m) = 1 cho nên (g k , m) = 1 với mọi
0 ≤ i ≤ ϕ(m) − 1.


Bây giờ ta chứng minh rằng g i 6≡ g j (mod m) với mọi 0 ≤ i ≤ ϕ(m) − 1.
Thật vậy, giả sử trái 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 đó ta có g i (g j−i − 1) ≡ 0 (mod m). Vì (g i , m) = 1 cho nên

từ đó suy ra g i−j ≡ 1 (mod m). Điều này khơng thể xảy ra vì 0 < i − j < ϕ(m)
và g có cấp là ϕ(m). Do đó các phần tử của hệ {1, g, g 2 , . . . , g ϕ(m−1) } là đôi một
không đồng dư với nhau theo môđun m. Cho 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.


16

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ỳ,
ordm (g k ) =

ϕ(m)
với d = (ϕ(m), k).
d

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 ngun 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 tốn trực tiếp ta thấy rằng

71 ≡ 7 (mod 22), 72 ≡ 5 (mod 22), 73 ≡ 13 (mod 22), 74 ≡ 3 (mod 22),
75 ≡ 21 (mod 22), 76 ≡ 15 (mod 22), 77 ≡ 17 (mod 22), 78 ≡ 9 (mod 22),
79 ≡ 19 (mod 22), 710 ≡ 1 (mod 22).

Cho nên 7 là một căn nguyên thủy theo môđun 22. Theo Mệnh đề 2.2.6, các căn
nguyên thủy theo môđun 22 là 7, 73 , 77 , 79 và qua tính tốn trực tiếp như trên ta
thấy rằng các căn nguyên thủy theo môđun 22 trong phạm vi từ 1 đến 22 là các
số 7, 13, 17, 19.
Quy ước 2.2.8. Để cho gọn từ đây về sau ta quy ước gọi tắt số căn nguyên thủy
theo môđun m trong phạm vi từ 1 đến m là số căn nguyên thủy theo mơđun m.
Phần cịn lại của mục này trình bày điều kiện tồn tại căn nguyên thủy theo
môđun là một số nguyên dương cho trước.
Đối với môđun nguyên tố ta có kết quả sau.


17

Mệnh đề 2.2.9. Nếu p là một số nguyên tố thì tồn tại căn ngun thủy theo
mơđun p.
Chứng minh. Nếu p = 2 thì rõ ràng 1 là căn nguyên thủy theo môđun 2. Cho
nên ta giả thiết p là một số nguyên tố lẻ. Giả sử p − 1 có biểu diễn chính tắc
p−1=

k
Y

pαi i .

i=1


trong đó p1 , p2 , . . . , pk là các số nguyên tố phân biệt, α1 , α2 , . . . , αk 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 ai có cấp là
pαi i . Đặt a = a1 a2 · · · ak . Khi đó, theo Mệnh đề 2.1.6, ta có cấp của a là p − 1.

Điều này chứng tỏ rằng a là một căn nguyên thủy theo môđun p. Vậy ta có điều
phải chứng minh.
Đối với mơđun lũy thừa một số nguyên tố ta có hai kết quả sau.
Mệnh đề 2.2.10. Cho p là một số nguyên tố lẻ. Khi đó tồn tại căn ngun 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 p2 ) thì
(g + p)p−1 ≡ g p−1 + (p − 1)g p−2 p ≡ 1 + (p − 1)g p−2 p 6≡ 1 (mod p2 ).

Do đó, ngay từ đầu ta có thể giả thiết rằng g p−1 6≡ 1 (mod p2 ). 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 p2 ) 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α ).



18

Gọi e là cấp của g theo môđun pα . Khi đó ta có p − 1 | e | ϕ(pα ) = (p − 1)pα−1 .
Kết hợp với đẳng thức trên từ đó suy ra e = ϕ(pα ). Điều này chứng tỏ rằng g là
một căn nguyên thủy theo mơđun pα . Vậy ta có điều phải chứng minh.
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õ ràng 1 là một căn nguyên thủy theo môđun 2, và −1 là một
căn nguyên thủy theo môđun 4. Giả sử α ≥ 3. Ta có nhận xét rằng, với x là một
số nguyên lẻ bất kỳ, x2 ≡ 1 (mod 23 ). Áp dụng Mệnh đề 1.2.3 và bằng phép quy
nạp, ta có được
x2

α−2

≡ (x2 )2

α−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 ta có kết quả sau.
Định lý 2.2.12. Cho m ≥ 2 là một số nguyên. Tồn tại căn nguyên thủy theo
môđun m khi và chỉ khi
m = 2, 4, pα , 2pα

với p là một số nguyên tố lẻ và α ≥ 1.

Để chứng minh định lý ta cần bổ đề sau.
Bổ đề 2.2.13. Cho m ≥ 2 là một số nguyên và m = m1 m2 với (m1 , m2 ) = 1. Nếu
(ϕ(m1 ), ϕ(m2 )) 6= 1 thì khơng tồn tại căn nguyên thủy theo môđun m.

Chứng minh. Lấy a là số ngun bất kì với (a, m) = 1. Khi đó (a, m1 ) = 1 và
(a, m2 ) = 1. Do đó aϕ(m1 ) ≡ 1 (mod m1 ) và aϕ(m2 ) ≡ 1 (mod m2 ). Đặt
l = [ϕ(m1 ), ϕ(m2 )]. Khi đó ta có al ≡ 1 (mod m). Vì (ϕ(m1 ), ϕ(m2 )) 6= 1 cho


19

nên l < ϕ(m1 )ϕ(m2 ) = ϕ(m) . Từ đó suy ra khơng tồn tại căn ngun thủy theo
mơđun m.
Phép chứng minh Định lý 2.2.12. Trước tiên ta có nhận xét rằng nếu p là một số
nguyên tố lẻ thì ϕ(pα ) với α ≥ 1 là một số chẵn. Cho nên nếu m có hơn một ước
nguyên tố lẻ thì, theo Bổ đề 2.2.13, khơng tồn tại căn ngun thủy theo mơđun
m. Do đó nếu m có căn ngun thủy thì nó chỉ có một trong các dạng là 2α , pα ,

và 2α pβ trong đó p là một số nguyên tố lẻ, và α, β là các số nguyên dương.
Nếu m = 2α thì, theo Mệnh đề 2.2.11, tồn tại căn nguyên thủy theo môđun
m khi và chỉ khi α = 1 hoặc α = 2. Nếu m = pα thì, theo Mệnh đề 2.2.10, ln

tồn tại căn ngun thủy theo mơđun m.
Ta chỉ cịn xét trường hợp m = 2α pβ . Nếu α ≥ 2 thì ϕ(2α ) là số chẵn. Vì ϕ(pβ )
là số chẵn cho nên, theo Bổ đề 2.2.13, trong trường hợp này không tồn tại căn
nguyên thủy theo môđun m.
Giả sử α = 1. Gọi g là căn nguyên thủy theo mơđun pβ . Khi đó g + pβ cũng là
một căn ngun thủy theo mơđun pβ . Vì trong hai số g và g + pβ phải có một số
lẻ, cho nên ngay từ đầu ta có thể giả thiết g là lẻ. Ta sẽ chứng minh rằng g cũng
là một căn nguyên thủy theo môđun 2pβ . Thật vậy, ta có (g, 2pβ ) = (g, pβ ) = 1.

Với e là một số nguyên dương bất kỳ, ta thấy rằng đồng dư thức g e ≡ 1 (mod 2pβ )
xảy ra khi và chỉ khi g e ≡ 1 (mod pβ ). Điều này chứng tỏ rằng cấp của g theo
môđun 2pβ bằng cấp của g theo mơđun pβ , và bằng ϕ(pβ ). Vì ϕ(2pβ ) = ϕ(pβ ),
cho nên từ đó suy ra g là một căn nguyên thủy theo môđun 2pβ .

2.3

Số nguyên tố với số căn nguyên thủy cho trước

Vấn đề chính của mục này là với t là một số nguyên dương cho trước có tồn
tại hay khơng một số ngun tố p để số các căn nguyên thủy theo môđun p bằng


20

t, nếu có hãy tìm tất cả các số ngun tố p thỏa mãn điều kiện nà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].
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ì 2r là ước của ϕ(m).
Chứng minh. Giả sử m =

k
Q
i=1

pαi i với pi 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
Y

(pi − 1)pi αi −1

i=1

là số chẵn, từ đó suy ra ϕ(m) là số chẵn.
Vì 2 | pi − 1 với mỗi pi lẻ, 1 ≤ i ≤ k nên
r

2 |

k
Y

(pi − 1)pi α1 −1

i=1

do m có r ước nguyên tố lẻ phân biệt. Do đó 2r | ϕ(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ếu p lẻ thì 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 bằng
ϕ(ϕ(p)) = ϕ(p − 1) = ϕ(2α )ϕ(k).

Do đó, nếu số căn ngun thủy theo mơđun p là 1 thì ϕ(2α ) = 1 và ϕ(k) = 1. Từ
đó suy ra α = 1 và k = 1 theo Mệnh đề 2.3.1 và do k lẻ cho nên p = 3. Ngược lại,