Xem mã nguồn của Căn nguyên thủy modulo n

'''Căn nguyên thủy modulo ''n''''' là một khái niệm trong [[số học modulo]] của [[lý thuyết số]].

== Khái niệm ==
Nếu ''n'' ≥ 1 là một [[số nguyên]] thì các số nguyên [[số nguyên tố cùng nhau|nguyên tố cùng nhau]] với ''n'' tạo thành một [[nhóm (đại số)|nhóm]] với phép nhân modulo ''n''; nhóm này được ký hiệu là ('''Z'''/''n'''''Z''')<sup>&times;</sup> hay '''Z'''<sub>n</sub><sup>*</sup>. Nhóm này là [[nhóm cyclic]] nếu và chỉ nếu ''n'' bằng 1, 2, 4, ''p''<sup>''k''</sup>, hoặc 2 ''p''<sup>''k''</sup> với một [[số nguyên tố]] ''p'' &ge; 3 và lũy thừa ''k'' &ge; 1. Một [[phần tử sinh]] của nhóm cyclic này được gọi là một '''căn nguyên thủy  modulo ''n''''', hay một '''phần tử nguyên thủy của Z<sub>n</sub><sup>*</sup>'''.

Nói cách khác, số nguyên dương ''a'' gọi là căn nguyên thủy của ''n'' khi và chỉ khi ''a'' và ''n'' nguyên tố cùng nhau, ''a < n,'' và <\ord_{n}(a)=<math>\varphi(n)</math>

== Ví dụ==
Ta lấy chẳng hạn  ''n'' = 14. Các phần tử của

:('''Z'''/14'''Z''')<sup>&times;</sup>

là các lớp đồng dư của

:1, 3, 5, 9, 11 và 13.
:(Mỗi số trên và n = 14 đều có ước chung lớn nhất là 1).

trong đó 3 là một căn nguyên thủy  modulo ''14'',và ta có 3<sup>2</sup>&nbsp;≡&nbsp;9, 3<sup>3</sup>&nbsp;≡&nbsp;13, 3<sup>4</sup>&nbsp;≡&nbsp;11, 3<sup>5</sup>&nbsp;≡&nbsp;5 và 3<sup>6</sup>&nbsp;≡&nbsp;1 (mod 14). Ngoài ra, còn một căn nguyên thủy modulo 14 khác là 5.<code>
  m     m<sup>k</sup> (mod 14) &ndash; (chỉ liệt kê khoảng đầu tiên của mỗi chu kỳ)
  1:   1
  3:   3,  9, 13, 11,  5,  1 
  5:   5, 11, 13,  9,  3,  1
  9:   9, 11,  1
 11:  11,  9,  1
 13:  13,  1</code>

Số các giá trị tính được bởi modulo của 14 với m = 1 là 1, m = 3 là 6, m = 5 là 6, m = 9 là 3, m = 11 là 3, m = 13 là 2. Ta thấy chỉ có 3 và 5 có số các giá trị tính được = φ(14) = 6 (số các lớp đồng dư). Vì thế 3 và 5 là căn nguyên thủy của 14.

Chỉ các số  ''m'' mà có thể nâng lên lũy thừa cho kết quả là 1 (mod 14) là nguyên tố cùng nhau với 14. 
Tập hợp các số đó là S&nbsp;=&nbsp;(1,&nbsp;3,&nbsp;9,&nbsp;13,&nbsp;11,&nbsp;5).

Từ công thức ''f''(''m'',&nbsp;''k'')&nbsp;=&nbsp;''m<sup>k</sup>''&nbsp;&minus;&nbsp;1&nbsp;≡&nbsp;0&nbsp;(mod&nbsp;14) chúng ta hiểu các ''căn'' (- nói rõ hơn là các căn của 1 theo modulo 14) là các số ''m'' thỏa mãn đồng dư thức trên với lũy thừa ''k''&nbsp;>&nbsp;0 nào đó.

Tập hợp ''S''&nbsp;=&nbsp;{1,&nbsp;3,&nbsp;9,&nbsp;13,&nbsp;11,&nbsp;5} chứa tất cả các căn,  tập hợp ''R''&nbsp;=&nbsp;{3,&nbsp;5} là tập hợp các  "căn nguyên thủy", mà các lũy thừa (mod 14) trong một chu kỳ phải trải qua tất cả các căn có thể được, hay, nói cách khác, tập R "sinh ra " tập hợp S.
---

Bảng dưới đây là bảng chỉ ra các căn nguyên thủy nhỏ nhất của một số giá trị modulo n. Có thể tìm thấy nhiều hơn trong {{OEIS|id=A046145}}:
{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
! ''n''
| 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13 || 14
|-
! căn nguyên thủy mod ''n''  nhỏ nhất
| 1 || 2 || 3 || 2 || 5 || 3 || - || 2 || 3 || 2 || - || 2 || 3
|}

==Tìm căn nguyên thủy modulo ''n''==
Chưa biết một công thức tổng quát cho các căn nguyên thủy modulo ''n''. Tuy thế có một số phương pháp tìm căn nguyên thủy đã được giới thiệu. Nếu bậc của một số ''m'' modulo ''n'' bằng [[phi hàm Euler|&phi;(''n'')]] (bậc của ('''Z'''/''n'''''Z''')<sup>&times;</sup>), thì ''m'' là một căn nguyên thủy của ''n''. Ngược lại: Nếu m là một căn nguyên thủy modulo n thì bậc (nhân) của m modulo n là [[phi hàm Euler|&phi;(''n'')]]. Chúng ta có thể sử dụng điều này để kiểm tra các căn nguyên thủy.

Trước hết, tính φ(''n''). Sau đó kiểm tra các ước nguyên tố khác nhau của φ(''n'') chẳng hạn là  ''p''<sub>1</sub>,...,''p''<sub>''k''</sub>. Với mỗi ''m'' of ('''Z'''/''n'''''Z''')<sup>&times;</sup>, tính 
:<math>m^{\phi(n)/p_i} \mod n \qquad\mbox {cho}\  i=1,\ldots,k</math>
bằng cách dùng [[thuật toán bình phương và nhân]]. Nếu với một số ''m'' nào đó cho ''k'' kết quả khác 1 thì nó là căn nguyên thủy.

Số các căn nguyên thủy modulo ''n'', nếu có là

:&phi;(&phi;(''n''))

vì, trong tường hợp tổng quát, một nhóm cyclic với ''r'' phần tử có  φ(''r'') phần tử sinh.

Một số người quan tâm đến các căn nguyên thủy nhỏ. Chúng ta có kết quả sau đây:

*Với mọi số ε>0 tồn tại hằng số dương ''C'' và ''p''<sub>0</sub> sao cho, với mọi [[số nguyên tố]] ''p'' ≥ ''p''<sub>0</sub>, tồn tại một căn nguyên thủy  modulo ''p'' nhỏ hơn

:''C'' ''p''<sup>1/4+&epsilon;</sup>.

*Nếu [[Giả thuyết Riemann|giả thiết Riemann]] là đúng, thì với mọi số nguyên tố ''p'', tồn tại một căn nguyên thủy modulo ''p'' nhỏ hơn

:70 ([[natural logarithm|ln]](''p''))<sup>2</sup>.

== Sử dụng ==

Căn nguyên thủy modulo n được sử dụng thường xuyên trong [[mật mã học]], trong hệ mật [[Diffie-Hellman Key Exchange]].

==Xem thêm==
* [[Artin's conjecture on primitive roots]]
* [[Dirichlet character]]
* [[Wilson's theorem#Generalization|Gauss' generalization of Wilson's theorem]]

==Tham khảo==
{{tham khảo}}
*{{chú thích sách|last = Ore|first = Oystein|title = Number Theory and Its History|url = https://archive.org/details/numbertheoryitsh0000orey|publisher = Dover|date = 1988|pages =  [https://archive.org/details/numbertheoryitsh0000orey/page/284 284]-302|isbn = 0-486-65620-9}}

[[Thể loại:Số học modulo]]