I. Khái niệm về căn nguyên thủy.

Số nguyên dương $m$ gọi là có căn nguyên thủy khi và chỉ khi tồn tại số nguyên $a$ sao cho $a$ và $m$ nguyên tố cùng nhau và $$\text{ord}_{m}(a)=\varphi(m).$$

II. Điều kiện để có căn nguyên thủy.

Ta xét đến một ví dụ sau

Ví dụ. Xét $m=14$, có $\mathcal{R}_{14}={\rm{\{}}1,\,3,\,5,\,9,\,11,\,13{\rm{\} }}$ ta xét bảng sau

(Bảng tính cấp của các phần tử thuộc $\mathcal{R}_{14}$).

Vậy ta thấy rằng $14$ có hai căn nguyên thủy là $5,\,3$

Ta để ý rằng $14$ có hai căn nguyên thủy số lượng này vừa bằng $\varphi(\varphi(14))=2$ vậy ta có ngay định lý sau đây để tính số lượng căn nguyên thủy của một số nguyên dương $m$ có căn nguyên thủy.

Định Lý. Nếu $m$ có căn nguyen thủy thì trong $\mathcal{R}_{m}$ có đúng $\varphi(\varphi(m))$ căn nguyên thủy.

Chứng minh. Giả sử $m$ có căn nguyên thủy là $a$ đầu tiên ta cần chỉ ra \[R = {\rm{\{ }}a^1,\,a^2,\,\ldots,a^{\varphi(m)}{\rm{\} }}={\rm{\{ }}{{\rm{a}}^k}{\rm{: k}} \in {\mathbb{Z^+} },k \le \varphi \left( m \right){\rm{\} }}.\] là hệ thặng dư thu gọn mod $m$ muốn vậy ta cần chứng minh $3$ điều kiện sau

1. Tập $R$ có $\varphi \left( m \right)$ phần tử.
2. Các phần tử trong $R$ đôi một nguyên tố cùng nhau với $m$.
3. Các phần tử trong $R$ đôi một không cùng số dư khi chia $m$.

Ta thấy $1)$ là hiển nhiên, giờ ta chứng minh $2)$. Lấy một phần tử bất kì trong $R$ sẽ có dạng $a^k$ với $k$ là một số nguyên dương và $k\le\varphi \left( m \right)$. Vì $a$ là căn nguyên thủy mod $m$ nên $\gcd(a,\,m)=1$ dẫn đến $\gcd(a^k,\,m)=1$ nên $2)$ được chứng minh. Giờ ta đi chứng minh $3)$. Lấy ra hai phần tử bất kì trong $R$ sẽ có dạng $a^k,\,a^l$ với $k,\,l$ là những số nguyên dương và $k,\,l\le\varphi \left( m \right)$. Nếu chúng đồng dư với nhau mod $m$, wlog $k>l$, có \[a^k\equiv a^l\pmod m\] nên \[k\equiv l\pmod\varphi \left( m \right).\] Từ đó \[\varphi \left( m \right)\mid k-l\] mà vì $k-l\in\mathbb{Z^+}$ và $k-l<\varphi \left( m \right)$ nên không thể do đó $3)$ được chứng minh. Tiếp theo ta lấy ra số nguyên dương $r$ trong $\mathcal{R}_{m}$ lúc đó $r$ sẽ có dạng $a^k$ với $a^k\in R$.
-Nếu $\gcd\left( k,\,\varphi(m) \right)=1$ lúc đó $\text{ord}_{m}(r)=\text{ord}_{m}(a)=\varphi(m)$.
-Nếu
$\gcd\left( k,\,\varphi(m) \right)=d\in\mathbb{Z^+}\ne1$ thì ta có $\text{ord}_{m}(r)=\dfrac{\varphi(m)}{d}<\varphi(m)$ do $d\in\mathbb{Z^+}\ne1$.
Từ đó ta thấy với mỗi $k$ ta có một $r$ mà với $\gcd\left( k,\,\varphi(m) \right)=d$ thì $r$ không là $\Pr$ mod $m$ mà $\gcd\left( k,\,\varphi(m) \right)=1$ thì $r$ lại là là một $\Pr$ mod $m$. Vì vậy trong $\mathcal{R}_{m}$ sẽ có đúng $\varphi(\varphi(m))$ căn nguyên thủy.

$\square$

Ta xét số $15$ liệu số này có căn nguyên thủy không? Ta cùng đến với định lý sau

Định lý. Nếu $m$ có hai ước nguyên tố lẻ thì $m$ không có căn nguyên thủy

Chứng minh. Gỉa sử $m$ có $r$ là $\Pr$ và $m=p^kq^lM$ với $k,\,l,\,M$ là những số nguyên dương $p,\,q$ là những số nguyên tố và $p\ne q$. Có $\text{ord}_{m}(r)=\varphi(m)=(p-1)(q-1)p^{k-1}q^{l-1}\varphi(m)$.Mà \[{r^{\dfrac{{\varphi \left( m \right)}}{2}}} = {\left( {{r^{\varphi \left( {{p^k}} \right)}}} \right)^L} \equiv 1\quad \left( {\bmod {p^k}} \right)\text{với}\left( L = \frac{{q – 1}}{2}\varphi \left( M \right){q^{l – 1}}\in\mathbb{Z^+} \right).\] Tương tự \[{r^{\dfrac{{\varphi \left( m \right)}}{2}}}\equiv 1\pmod q^l,\] còn \[{r^{\dfrac{{\varphi \left( m \right)}}{2}}}=\left( r^{\varphi(m)}\right)^T\equiv 1\pmod M,\text{với} T=\dfrac{(p-1)(q-1)}{2}p^{k-1}q^{l-1}\in\mathbb{Z^+}.\] Vậy \[p^kq^lM\mid{r^{\dfrac{{\varphi \left( m \right)}}{2}}}-1\] tức \[{r^{\dfrac{{\varphi \left( m \right)}}{2}}}\equiv 1\pmod m.\] Vậy $\varphi(m)\mid\varphi(m)\dfrac{1}{2}$.

$\square$

Quay ví dụ ở đầu định lý ta dễ thấy $15$ không có căn nguyên thủy vì $3,\,5$ là hai ước nguyên tố lẻ của $15$.
Ta có thêm một định lý sau để xác định những số không có căn nguyên thủy

Định lý. Nếu $m=2^kp^l$ với $k,\,l\in\mathbb{Z}$ và $k\ge 2$, thì $m$ không có căn nguyên thủy.

Định lý sau sẽ là một phương pháp để chỉ ra sự tồn tại của căn nguyên thủy.

Định lý. Nếu $L$ lẻ và $L$ có căn nguyên thủy thì $2L$ cũng thế.

Chứng minh. Giả sử $r$ là $\Pr$ của $L$, xét
-Nếu $r$ lẻ và $\text{ord}_{2L}(r)=h$ có $r^h\equiv 1\pmod{2L}$ nên \[r^h\equiv 1\pmod L.\] Nên $\text{ord}_{L}(2)\mid h$ mà $\text{ord}_{L}(r)=\varphi(L)$ nên $\varphi(L)$;(1).\\
Mặt khác \[r^h\equiv 1\pmod L\] tức $h\mid\varphi(2L)$ nhưng $\varphi(2L)=\varphi(2)$;(2).
Từ (1) và (2) có $h=\varphi(2L)=\varphi(2)$ nên $r$ là căn nguyên thủy mod $2L$
-Nếu $r$ chẵn. Xét $r’=r+L$ khi đó $r’$ là căn nguyên thủy mod $L$ và $r’$ lẻ rơi vào trường hợp trên.

$\square$

Ta dễ dàng thấy được là $2,\,3,\,5,\,7,\,9,\,11$ là các số nguyên tố và chúng đều có căn nguyên thủy vậy liệu có phải tất cả các số nguyên tố đều có căn nguyên thủy ta cùng đi đến định lý sau đây để làm rõ vấn đề đó.

Định lý.  Mọi số nguyên tố đều có căn nguyên thủy.

Chứng minh. Nếu $p=2$ thì tầm thường giờ ta xét $r\ge 3$ và $p-1=q_1^{k_1}q_2^{k_2}\ldots q_n^{k_n}$ với $q_i\in\mathbb{\mathcal{P}}$ và $q_i\ne q_j\forall i\ne j$.

Bổ Đề. Hễ $d\in\mathbb{Z^+}$ và $d\mid p-1$ thì phương trình \[x^d\equiv 1\pmod p\] có đúng $d$ nghiệm.

Xét 2 phương trình sau \[x^{q^{k-1}}\equiv 1 \pmod p,(I)\] \[x^{q^{k}}\equiv 1 \pmod p,(II)\] với $q$ là số nguyên tố, $q\mid p-1, k\in\mathbb{Z^+}$ $\forall$ nghiệm của (I) là nghiệm của (II). Theo bổ đề sẽ có đúng $q^k-q^{k-1}=\varphi\left(q^k\right)$ là nghiệm của của (II) nhưng không là nghiệm của (I), một như thỏa $r^{q^{k}}\equiv 1\pmod p$ và $r^{q^{k-1}}\not\equiv 1\pmod p$, nên $\text{ord}_{p}(r)=h_r\mid q^h$ tức $h_r=q^t$ với $t\in\mathbb{N}, t\le k$. Do $r^{q^{k-1}}\equiv -1\pmod p$ và $p\ne 2$, nên $t=k$ kẻo không hễ $t<k$ thì $h_r\mid q^{k-1}$. Chứng tỏ $\text{ord}_{p}(r)=q^k$. Vậy sẽ tồn tại $r_i\in\mathcal{R}_{p}$ sao cho $\text{ord}_{p}\left(r_i\right)=q_i^{k_i} \forall i \in \{1;\,2;\,\ldots ;\,n\}$. Khi đó $\text{ord}_{p}\left(r_1r_2\ldots r_n\right)=\prod\limits_{1\le i\le n} {\text{ord}_{ p}(r_i)}= p-1$. Vậy $r_1r_2\ldots r_n$ là căn nguyên thủy mod $p$.

$\square$

Định lý. Với $p$ là một số nguyên tố lẻ và $k$ là một số nguyên dương thì $p^k$ có căn nguyên thủy.