Giáo trình Số học thuật toán - Chương 3: Các hàm số học

 các số nguyên, ta cũng có khái niệm hoàn toàn t−ơng tự về “căn” và “căn 
nguyên thuỷ” của đơn vị. 
 45
Định nghĩa 3.19. Giả sử a và m là các số nguyên d−ơng nguyên tố cùng nhau. Khi 
đó số nguyên nhỏ nhất x thoả mãn đồng d− ax≡ 1(mod m) đ−ợc gọi là bậc của a 
modulo m. Ta viết x= ordma . 
Ta chú ý rằng, số x nh− vậy tồn tại vì theo định lí Euler, aφ (m) ≡ 1(mod m). 
Định lí 3.20. Giả sử a và n là các số nguyên tố cùng nhau, n>0. Khi đó số nguyên x 
là nghiệm của đồng d− ax≡ 1(mod m) khi và chỉ khi x là một bội của bậc của a 
modulo n. 
Chứng minh. Giả sử x thoả mãn đồng d− trên. Ta viết x=q ordna+r, trong đó 0≤ r<x. 
Từ đó ta có ar≡ 1(mod m). Vì ordna là số d−ơng nhỏ nhất có tính chất đó nên r=0: x 
là một bội của bậc của a modulo n. Điều ng−ợc lại là rõ ràng. 
Hệ quả 3.21. Nếu a và n là các số nguyên tố cùng nhau, n>0, thì ordna |φ (n). 
Hệ quả 3.22. Nếu a và n là các số nguyên tố cùng nhau, n>0, thì ai≡ aj(mod n) khi 
và chỉ khi i≡ j(mod n). 
Chứng minh các hệ quả trên đ−ợc dành cho độc giả. 
Do hệ quả 3.21, nếu r và n là nguyên tố cùng nhau thì bậc của r không v−ợt quá 
φ (n). Các số có bậc đúng bằng φ (n) giữ vai trò quan trọng trong nhiều vấn đề khác 
nhau của số học. Ta có định nghĩa sau. 
Định nghĩa 3.23. Nếu r và n là các số nguyên tố cùng nhau, n>0, và nếu 
ordnr =φ (n) thì r đ−ợc gọi là căn nguyên thuỷ modulo n. 
Chú ý rằng không phải mọi số đều có căn nguyên thuỷ. Chẳng hạn, xét n=8. Các số 
nhỏ hơn 8 và nguyên tố cùng nhau với 8 là 1, 3, 5, 7, đồng thời ta có ord81=1, bậc 
của các số còn lại bằng 2, trong khi φ (8)=4. Vấn đề những số nguyên nào thì có căn 
nguyên thuỷ sẽ đ−ợc xét về sau. 
Định lí 3.24. Nếu r, n nguyên tố cùng nhau, n>0, và nếu r là căn nguyên thuỷ 
modulo n, thì các số sau đây lập thành hệ thặng d− thu gọn modulo n: 
r1,r2,...,rφ (n). 
Chứng minh. Vì (r,n)=1, các số trên nguyên tố cùng nhau với n. Ta chỉ cần chứng tỏ 
rằng, không có hai số nào đồng d− với nhau modulo n. Giả sử ri≡ rj(mod n). Theo hệ 
quả 3.22, i≡ j(mod φ (n)). Từ đó suy ra i=j, vì i, j không v−ợt quá φ (n). Định lí đ−ợc 
chứng minh. 
Định lí 3.25. Nếu ordma=t và u là số nguyên d−ơng, thì ordm(au)= t / (t,u). 
Chứng minh. Đặt v=(t,u), t=t1v, u=u1v, s= ordm(a
u). Ta có 
(au)t 1 =(au1v)t/v=(at)u1≡ 1(mod m). 
Do đó, s|t1. Mặt khác, (au)s=aus≡ 1(mod m) nên t|su. Nh− vậy, t1v | u1vs, do đó, t1|u1s. 
Vì (u1, t1)=1, ta có t1|s. Cuối cùng, vì s|t1, t1|s nên s=t1=t/v=t/(t, u), chứng minh 
xong. 
 46
Hệ quả 3.26. Giả sử r là căn nguyên thủy modulo m, trong đó m là số nguyên lớn 
hơn 1. Khi đó ru là căn nguyên thủy modulo m nếu và chỉ nếu (u,φ (m))=1. 
Thật vậy, ordmr
u=ord mr/(u, ordmr)= φ (m)/(u, φ (m)): hệ quả đ−ợc chứng minh. 
Định lí 3.27. Nếu số nguyên d−ơng m có căn nguyên thuỷ, thì nó có tất cả φ (φ (m)) 
căn nguyên thuỷ không đồng d− nhau. 
Thật vậy, nếu r là một căn nguyên thuỷ thì r, r2, ..., rφ( )m là một hệ đầy đủ các 
thặng d− thu gọn modulo m. Số căn nguyên thuỷ modulo m đúng bằng số các số u 
thoả mãn (u, φ (m))=1, và có đúng φ (φ (m)) số u nh− thế. Định lí đ−ợc chứng 
minh. 
Đ5. Sự tồn tại của căn nguyên thuỷ. 
Trong tiết này, ta sẽ xác định những số nguyên có căn nguyên thuỷ. Tr−ớc tiên ta sẽ 
chứng minh rằng mọi số nguyên tố đều có căn nguyên thuỷ. Để làm việc đó, ta cần 
một vài kiến thức về đồng d− đa thức. 
Giả sử f(x) là đa thức với hệ số nguyên. Số c đ−ợc gọi là nghiệm của đa thức f(x) 
modulo m nếu f(c) ≡ 0(mod m). Dễ thấy rằng, nếu c là một nghiệm thì mọi số đồng 
d− với c modulo m cũng là nghiệm. 
Đối với số nghiệm của một đa thức modulo một số nguyên, ta cũng có tính chất 
t−ơng tự nh− số nghiệm của một đa thức. 
Định lí Lagrange. Giả sử f(x)=anx
n+...+a1x+a0 là đa thức với hệ số nguyên, n>o, 
đồng thời an /≡ 0(mod p). Khi đó f(x) có nhiều nhất n nghiệm modulo p không đồng 
d− từng cặp. 
Chứng minh. Ta chứng minh bằng qui nạp. Khi n=1, định lí là rõ ràng. Giả sử định lí 
đã chứng minh với đa thức bậc n-1 có hệ số của luỹ thừa cao nhất không chia hết cho 
p, và giả sử rằng đa thức f(x) có n+1 nghiệm modulo p không đồng d− từng cặp 
c0,c1,...,cn. Ta có f(x)-f(c0)=(x-x0)g(x), trong đó g(x) là đa thức bậc n-1 với hệ số cao 
nhất là an. Vì với mọi k, 0≤k≤n, ck-c0 /≡ 0 (mod p), trong khi đó f(ck)-f(c0)= 
(ck-c0)g(ck) ≡ 0(mod p), nên ck là nghiệm của g(x) modulo p: trái với giả thiết quy 
nạp. Định lí đ−ợc chứng minh. 
 Định lí 3.28. Giả sử p là số nguyên tố và d là một −ớc của p-1. Khi đó đa thức xd-1 
có đúng d nghiệm modulo p không đồng d− từng cặp. 
Chứng minh. Thật vậy, giả sử p-1=de. Ta có xp-1-1=(xd-1)g(x). Theo định lí Fermat 
bé, xp-1-1 có p-1 nghiệm modulo p không đồng d− từng cặp. Mặt khác, mỗi một 
nghiệm đó phải là nghiệm của xd-1 hoặc là của g(x). Theo định lí Lagrange, g(x) có 
nhiều nhất p-d-1 nghiệm không đồng d− từng cặp, vì thế xd-1 phải có ít nhất 
(p-1)-(p-d-1)=d nghiệm. Lại theo định lí Lagrange, xd-1 có không quá d nghiệm, vậy 
nó có đúng d nghiệm modulo p không đồng d− từng cặp. Định lí d−ợc chứng minh. 
 47
Định lí trên đây sẽ đ−ợc sử dụng trong ch−ơng 5 khi xây dựng các tr−ờng hữu hạn. 
Định lí 3.29. Giả sử p là số nguyên tố, d là −ớc d−ơng của p-1. Khi đó, số các số 
nguyên không đồng d− bậc d modulo p là φ (d). 
Chứng minh. Giả sử F(d) là số các số nguyên d−ơng bậc d modulo p và bé hơn p. Ta 
cần chứng tỏ rằng F(d)= φ (d). Vì φ (d)=p-1 nên d|p-1, từ đó ta có 
p-1= F d
d p
( )
| −
∑
1
Mặt khác ta có: 
p-1= φ( )
|
d
d p−
∑
1
theo công thức của Phi-hàm. Nh− vậy định lí sẽ đ−ợc chứng minh nếu ta chứng tỏ 
đ−ợc rằng F(d)≤ φ (d) nếu d|p-1. 
Khi F(d)=0, điều nói trên là tầm th−ờng. Giả sử F(d)≠ 0, tức là tồn tại số nguyên a 
bậc d modulo p. Khi đó, các số nguyên a, a2,...,ad không đồng d− modulo p. Rõ ràng 
rằng, mỗi luỹ thừa của a là một nghiệm của xd-1≡ 0(mod p), mà số nghiệm không đồng 
d− đúng bằng d, nên mỗi nghiệm modulo p đồng d− với một trong các luỹ thừa của 
a. Do đó, vì phần tử tuỳ ý bậc d là một nghiệm của ph−ơng trình xd-1 ≡ 0(mod p) nên 
phải đồng d− với một trong các luỹ thừa của a. Mặt khác, theo định lí 3.24, luỹ thừa 
k của a có bậc d khi và chỉ khi (k,d)=1. Có đúng φ (d) số k nh− vậy, và do đó suy ra 
F(d) )≤ φ (d), định lí đ−ợc chứng minh. 
Hệ quả 3.30. Mọi số nguyên tố đều có căn nguyên thuỷ. 
Thật vậy, giả sử p là số nguyên tố. Khi đó có φ (p-1) số nguyên bậc p-1 modulo p 
(Định lí 3.28) không đồng d− từng cặp. Theo định nghĩa, mỗi số đó là một căn 
nguyên thuỷ: p có φ (p-1) căn nguyên thuỷ. 
Phần còn lại của ch−ơng đ−ợc giành để tìm tất cả các số nguyên d−ơng có căn 
nguyên thuỷ. 
Định lí 3.31. Nếu p là một số nguyên tố lẻ với căn nguyên thuỷ r, thì hoặc r, hoặc 
r+p là căn nguyên thuỷ modulo p2. 
Chứng minh. Vì r là căn nguyên thuỷ modulo p nên ta có 
ordpr=φ (d)=p-1. 
Giả sử n=ord p2 r. Ta có r
n≡ 1(mod p2), và do đó rn≡ 1(mod p). Nh− vậy, bậc p-1 của 
r là một −ớc của n. Mặt khác, n là bậc của r modulo p2 nên n là −ớc của φ (p2)=p(p-1). Vì n|p(p-1) và p-1|n nên dễ dàng suy ra rằng, hoặc n=p-1, hoặc 
n=p(p-1). Nếu n=p(p-1) thì r là căn nguyên thuỷ modulo p2, vì ord p2 r=φ (p2). Trong 
tr−ờng hợp còn lại, n=p-1, ta có rp-1≡ 1(mod p2). Đặt s=r+p. Cần phải chứng minh 
rằng s là căn nguyên thuỷ modulo p2. Vì s≡ r(mod p), s cũng là căn nguyên thuỷ 
 48
modulo p. Nh− vậy, theo chứng minh trên ord
p2
s hoặc bằng p-1, hoặc bằng p(p-1). 
Ta sẽ chứng tỏ rằng, bậc đó không thể là p-1. Ta có 
sp-1=(r+p)p-1≡ rp-1+(p-1)prp-2(mod p2) ≡ 1+(p-1)prp-2≡ 1-prp-2(mod p2) 
Từ đó ta có thể thấy rằng, sp-1 /≡ 1(mod p2). Thật vậy, nếu ng−ợc lại thì prp-
2≡ 0(mod p2), nên rp-2≡ 0(mod p). Điều này không thể có, vì p /| r do r là căn nguyên 
thuỷ modulo p. Nh− vậy ord
p2
s=p(p-1)=φ (p2), tức s=r+p là căn nguyên thuỷ 
modulo p2. 
Bây giờ ta xét luỹ thừa tuỳ ý của số nguyên tố 
Định lý 3.32. Giả sử p là một số nguyên tố lẻ, khi đó pk có căn nguyên thuỷ với mọi 
số nguyên d−ơng k. Hơn nữa, nếu n là căn nguyên thuỷ modulo p2 thì r là căn nguyên 
thuỷ modulo pk với mọi số ngyên d−ơng k. 
Chứng minh. Từ Định lí 3.31, p có căn nguyên thuỷ r sao cho đó cũng là căn nguyên 
thuỷ modulo p2, và do đó 
rp-1 /≡ 1 (mod p2). 
Ta sẽ chứng minh r cũng là căn nguyên thuỷ modulo pk với mọi số nguyên d−ơng k. 
Bằng quy nạp có thể thấy rằng 
r p p
k − −1 1( ) /≡ 1 (mod pk) (*) 
với mọi số nguyên d−ơng k. Giả sử 
n=ord rpk 
Ta có n |ϕ (pk)=pk-1(p-1). Mặt khác 
rn /≡ 1 (mod pk), 
và rn /≡ 1 (mod p). 
Do đó p-1=ϕ (p) |n (Định lí 3.30). Vì (p-1) |n và n|pk-1(p-1) nên n=pt(p-1), trong 
đó t là số nguyên d−ơng 0≤ t≤k-1. Nếu n=pt(p-1) với t≤k-2 thì 
r r pp p p p p k
k t k t− − −− −= ≡2 21 1 1( ) ( )( ) (mod ) , 
mâu thuẫn. Vậy ord rpk =p
k-1(p-1)= ϕ (pk), r cũng là cũng nguyên thuỷcủa pk. 
Chứng minh (*): k=2: đúng. Giả sử (*) đúng với số nguyên d−ơng k≥2. Khi đó 
r pp p k
k − − /≡2 1 1( ) (mod ) . 
Vì (r,p)=1, ta thấy (r,pk-1)=1. Do đó, từ Định lí Euler ta có 
r rp p p
k k− −− ≡2 11( ) ( )ϕ 
Vậy tồn tại số nguyên d sao cho 
 49
r p p
k − −2 1( ) =1+dpk-1, 
trong đó p /| d, vì theo giả thiết r pp p kk − − /≡2 1 1( ) (mod ) . 
Ta lấy luỹ thừa bậc p của hai vế ph−ơng trình trên và nhận đ−ợc 
r dp p dp
p
p dp dp
dp p
p p k p k k k p
k k
k − − − − − −
+
= + = + + 

 + +
≡ +
1 1 1 1 2 1 2 1
1
1 1
2
1
( ) ( ) ( ) ( ) ... ( )
(mod ).
Vì p /| d nên ta có 
r p p
k − −1 1( ) /≡ +1 1(mod )pk , 
chứng minh xong. 
Ví dụ: r=3 là căn nguyên thuỷ modulo 7k với mọi số nguyên d−ơng k. 
Định lí 3.33: Nếu số nguyên d−ơng n không phải là luỹ thừa của một số nguyên tố 
hoặc hai lần luỹ thừa một số nguyên tố, thì n không có căn nguyên thuỷ. 
Chứng minh. Giả sử n là số nguyên d−ơng với phân tích ra thừa số nguyên tố nh− sau 
n p p pt t m
tm= 1 21 2 ... . 
Giả sử n có căn nguyên thuỷ r, tức là (n,r)=1 và ordnr=ϕ (n). Vì (r,n)=1 nên 
(r,pt)=1 trong đó pt là một trong các luỹ thừa nguyên tố có mặt trong phân tích trên. 
Theo Định lý Euler, 
r pp t
tϕ ( ) (mod ).≡ 1 
Giả sử U là bội chung nhỏ nhất của ϕ ϕ ϕ( ), ( ),