Suốt dọc từ đây của bài giảng này đến hết, mỗi khi viết $\text{ord}_m(a)$ ta sẽ mặc định các điều kiện là $m\in\mathbb Z^+,\;a\in\mathbb Z$ và $\gcd(a;\,m)=1$. Tính chất đầu tiên của mục này, sẽ cho ta thấy ngay tác dụng của cấp trong việc tìm số dư của lũy thừa bậc cao.

Tính chất 1. Với các số mũ $k;\,l\in\mathbb N$ và $\text{ord}_m(a)=d$ khi đó đồng dư $a^k\equiv a^l\pmod m$ xảy ra khi và chỉ khi xảy ra đồng dư $k\equiv l\pmod d$.

Chứng minh. Không mất tính tổng quát, ta giả sử $k\ge l$. Trước tiên ta đi chứng minh rằng hễ $k\equiv l\pmod d$ thì $a^k\equiv a^l\pmod m$, thật vậy. Vì $k\equiv l\pmod d$ nên $k=l+qd$ với $q\in\mathbb N$ khi ấy do $a^d\equiv 1\pmod m$ nên\[{a^k} = {a^{l + qd}} = {\left( {{a^d}} \right)^q}{a^l} \equiv {1^q}{a^l} \equiv {a^l} {\pmod m};\;(1) \]
Giờ nếu như $a^k\equiv a^l\pmod m$, ta giả sử $k-l$ chia $d$ dư $r$, ta cần chứng tỏ $r=0$, thật vậy.

Nếu $r\ne 0$, thế thì $r\in\mathbb Z^+$ và $k-l=qd+r$ với $q\in\mathbb N$ từ $a^d\equiv 1\pmod m$ có\[0 \equiv {a^k} – {a^l} = {a^l}\left( {{a^{k – l}} – 1} \right) = {a^l}\left( {{a^{qd + r}} – 1} \right) = {a^l}\left( {{{\left( {{a^d}} \right)}^q}{a^r} – 1} \right) \equiv {a^l}\left( {{1^q}{a^r} – 1} \right)\pmod m\]Tức là $m\mid a^l\left(a^r-1\right)$, nhưng $\gcd\left(a^l;\,m\right)=1$ nên $a^r-1\;\vdots\;m$ hay\[a^r\equiv 1\pmod m\]Vì $r<d$ nên vi phạm vai trò của $d$ và dẫn đến mâu thuẫn. Vậy, $r=0$ nói khác đi\[k\equiv l\pmod d;\;(2)\]
Từ $(1)$ và $(2)$ ta có điều cần chứng minh.

$\square$

Từ tính chất này, cùng với bản chất của quan hệ đồng dư-chia hết mà chúng ta có ngay được ba hệ quả thường dùng sau đây.

Hệ quả 1.1. Nếu $\text{ord}_m(a)=d$ và $n$ chia $d$ dư $r$, khi đó số dư của $a^n$ trong phép chia cho $m$ chính là số dư của $a^r$ trong phép chia cho $m$.

Hệ quả 1.2. Với $\text{ord}_m(a)=d$, khi đó $a^n\equiv 1\pmod m$ nếu và chỉ nếu $d\mid n$.

Hệ quả 1.3. Nếu $a^p\equiv 1\pmod m$ (với $p$ là một số nguyên tố), và $p\nmid (a-1)$ thì $\text{ord}_m(a)=p$.

Chúng ta có thể quay lại ví dụ về tìm 5 chữ số tận cùng của $5^{2016}$ ở mục trước, để thấy các tính chất và hệ quả vừa nêu hiện hữu trong các động tác đã xử lý. Một ví dụ thêm nữa, là tìm số dư của $2^{2005^{2016}}$ khi chia cho $7$. Giờ đây, ta có thể xử lý chóng vánh như sau.

Ta có $\text{ord}_72=3$, và $2005^{2016}\equiv (-1)^{2016}\equiv 1\pmod 3$ nên\[2005^{2016}\equiv 1^{2016}\equiv 1\pmod 3\]Cho nên\[2^{2005^{2016}}\equiv 2^1\equiv 2\pmod 7\]Tức là số dư cần tìm là 2.

Một vấn đề đặt ra rất tự nhiên của bài toán tìm số dư của lũy thừa $a^n$ khi chia $m$, đó là sự phức tạp không chỉ đến từ số mũ $n$ lớn mà còn có thể do cơ số $a$ rất lớn gây ra sự phức tạp cả về việc tìm cấp và cả về tính toán số dư. Một hoàn cảnh kiểu thế, là bài toán tìm số dư của $2018^{2005^{2016}}$ khi chia cho $7$. Thoạt tiên, nếu vội vã và máy móc thì ta sẽ đi tìm $\text{ord}_7(2018)$. Việc đó, cũng không hẳn là không thể. Tuy nhiên, việc phải dò dẫm tính toán $2018^n$ với $n$ từ $1$ dần lên cao sẽ gây nên một cảm xúc đáng ngán. Giờ nếu ta để ý đến các tính chất đồng dư và việc $2018\equiv 2\pmod 7$ thì ta sẽ thấy kết quả hai bài toán vừa nói đến thực ra không khác gì nhau. Khái quát tư tưởng đó, ta có tính chất sau đây.

Tính chất 2. Nếu $a\equiv b\pmod m$ thì $\text{ord}_m(a)=\text{ord}_m(b)$.

Chứng minh. Giả sử $\text{ord}_m(a)=d;\,\text{ord}_m(b)=d’$, do $a\equiv b\pmod m$ nên $$b^d\equiv a^d\equiv 1\pmod m$$ cho nên theo tính chất 1 ta có $d’\mid d$. Tương tự từ $$a^{d’}\equiv b^{d’}\equiv 1\pmod m$$ sẽ có $d\mid d’$ do đó $d=d’$.

$\square$

Chú ý. Chiều đảo lại của khẳng định này nói chung là không đúng, một ví dụ để chứng tỏ điều đó là $\text{ord}_7(2)=\text{ord}_7(4)=3$ nhưng không có chuyện $2\equiv 4\pmod 7$.

Tiếp theo ta sẽ quan tâm đến vấn đề tính cấp của một tích, khi biết cấp của từng nhân tử. Trong trường hợp tổng quát, việc đưa ra cách tính $\text{ord}_m(ab)$ theo $\text{ord}_m(a)$ và $\text{ord}_m(b)$ rất phức tạp và vượt quá khuôn khổ bài giảng. Ta chỉ xét đến một trường hợp đặc biệt, như tính chất nêu sau đây.

Tính chất 3.  Hễ $\gcd\left(\text{ord}_m(a);\,\text{ord}_m(b)\right)=1$ thì $\text{ord}_m(ab)=\text{ord}_ma.\text{ord}_mb$.

Chứng minh. Giả sử $\text{ord}_m(a)=d;\,\text{ord}_m(b)=d’$ và $\text{ord}_m(ab)=D$, ta có $\gcd(d;\,d’)=1$ và ta cần chứng minh $D=dd’$. Ta có $D\mid dd’;\;(1)$ vì\[(ab)^{dd’}=\left(a^d\right)^{d’}\left(b^{d’}\right)^{d}\equiv 1^{d’}.1^d\equiv 1\pmod m\]
Lại thấy\[1\equiv 1^d\equiv \left(\left(ab\right)^{D}\right)^d\equiv (ab)^{dD}\equiv\left(a^d\right)^{D}b^{dD}\equiv 1^{D}b^{dD}\equiv b^{dD}\pmod m\]
Vậy $d’\mid dD$ nên $d’\mid D$ do $\gcd(d;\,d’)=1$, tương tự $d\mid D$ và ta có $dd’\mid D;\;(2)$ cũng vì $\gcd(d;\,d’)=1$.

Từ $(1)$ và $(2)$ ta có $D=dd’$.

$\square$

Chú ý. Nếu bỏ đi điều kiện $\gcd\left(\text{ord}_m(a);\,\text{ord}_m(b)\right)=1$ thì sẽ không có chuyện $\text{ord}_m(ab)=\text{ord}_ma.\text{ord}_mb$. Một ví dụ là $\text{ord}_7(2)=\text{ord}_7(4)=3$, nhưng $\text{ord}_7(6)=1\ne 9$. Tuy nhiên, nếu theo dõi chứng minh tính chất trên ta sẽ thấy là nếu bỏ đi ràng buộc $\gcd\left(\text{ord}_m(a);\,\text{ord}_m(b)\right)=1$ thì vẫn luôn có $\text{ord}_m(ab)$ là ước của $\text{ord}_ma.\text{ord}_mb$.

Ở những ví dụ phía trước, ta thấy rằng đôi lúc đối tượng phải tính cấp lại sẵn đã là một lũy thừa. Như vậy một công thức xử lý cấp của một lũy thừa hẳn là cần thiết, và nó chính là nội dung tính chất dưới đây.

Tính chất 4. $\text{ord}_m\left(a^k\right)=\dfrac{\text{ord}_m(a)}{\gcd\left(\text{ord}_m(a);\,k\right)}$

Chứng minh. Giả sử $\text{ord}_m(a)=d;\,\text{ord}_m\left(a^k\right)=d^*;\,(k;\,d)=t$, ta có $k=k’t;\,d=d’t$ với $k’;\,d’\in\mathbb Z^+$ và $\gcd(k’;\,d’)=1$. Ta cần chứng minh $d^*=d’$, từ $a^d\equiv 1\pmod m$ ta có
\[\left(a^k\right)^{d’}=a^{kd’}=a^{tk’d’}=\left(a^d\right)^{k’}\equiv 1^{k’}\equiv 1\pmod m\]
Vậy $d^*\mid d’;\;(1)$, mặt khác\[a^{kd^*}=\left(a^k\right)^{d^*}\equiv 1\pmod m\]Cho nên, $kd^*\;\vdots\;d$ tức là $k’td^*\;\vdots\;d’t$ để có\[k’d^*\;\vdots\;d’\]Nhưng do $(k’;\,d’)=1$ nên $d’\mid d^*;\;(2)$. Giờ, từ $(1)$ và $(2)$ ta có $d’=d^*$.

$\square$

Quay lại bài toán giờ đây đã trở nên đơn giản đó là tìm số dư của phép chia $2018^{2015^{2016}}$ khi chia cho $7$, ta nhận thấy\[k=2015^{2016}-1\equiv (-1)^{2016}-1\equiv 0\pmod 3\]Do vậy, $(k;\,3)=3$ và vì thế theo tính chất 3 cùng tính chất 2 thì thì\[\text{ord}_7\left(2018^k\right)=\dfrac{\text{ord}_7(2018)}{(k;\,\text{ord}_7(2018))}=\dfrac{\text{ord}_7(2)}{(k;\,\text{ord}_7(2))}=\dfrac{3}{(k;\,3)}=1\]Tức là $2018^k\equiv 1\pmod 7$, điều đó kết hợp\[2018^{2015^{2016}}=2018^{k+1}=2018.2018^k\equiv 2018\equiv 2\pmod 7\]Cho ta số dư cần tìm là 2.

Thực ra, vai trò của tính chất 4 không chỉ tầm thường như ở bài toán trên. Chúng ta thấy là nhờ tính chất 1 và các hệ quả, thì vấn đề tìm số dư của $a^n$ thông qua $\text{ord}_m(a)$ đã có những giải pháp hết sức thỏa đáng. Bây giờ là câu hỏi ngược cực kỳ khó khăn, nếu biết trước lũy thừa $n$ và số dư $r$ cũng như số chia $m$ liệu có tồn tại số nguyên $a$ để xảy ra đồng dư dưới đây hay không?\[a^n\equiv r\pmod m\]
Một câu trả lời kỹ lưỡng về điều kiện tồn tại, ắt hẳn không thể trình bày ở ngay mục này vì nó liên quan đến khái niệm thặng dư bậc cao. Tuy nhiên, nếu chấp nhận điều kiện hời hợt là $r$ phải là số dư của một lũy thừa bậc $n$ khi chia cho $m$, tức là tồn tại $a’\in\mathbb Z$ sao cho $r\equiv (a’)^n\pmod m$ thế thì nếu $(r;\,m)=1$ sẽ kéo theo $(a’;\,m)=1$ và do đó luôn tồn tại nghịch đảo modulo $a”$ theo mod $m$ của $a’$ (tức là số $a”$ thỏa $a”a’\equiv 1\pmod m$) vì thế đồng dư trên sẽ đưa về\[(aa”)^n\equiv 1\pmod m\]Đặt $aa”=a^*$, ta đưa về đồng dư\[\left(a^*\right)^n\equiv 1\pmod m\]Bài toán lúc này đây, hệt như bài toán khai căn trong đại số. Câu hỏi đặt ra, liệu có ngây thơ là đưa ngay về đồng dư đơn giản sau hay không?\[a^*\equiv 1\pmod m\]Tuy nhiên, khi xét $2^3\equiv 1\pmod 7$ ta thấy ngay là làm gì có chuyện “ngây thơ” rằng $2\equiv 1\pmod 7$. Như vậy trường hợp tổng quát rất đáng tiếc là không làm thế được. Dù vậy, cũng có trường hợp mà việc khai căn ngây thơ đó có thể thực hiện được như ở tính chất dưới đây

Tính chất 5.  Hễ $\gcd\left(\text{ord}_m(a);\,n\right)=1$ thì từ $a^n\equiv 1\pmod m$ ta sẽ có\[a\equiv 1\pmod m\]

Chứng minh.  Từ tính chất 4 kết hợp việc số $1$ là số nguyên dương bé nhất, để ta có\[1 =\text{ord}_m\left(a^n\right)=\dfrac{\text{ord}_ma}{\gcd\left(\text{ord}_ma;\,n\right)}=\text{ord}_m(a)\]Nên $a=a^1\equiv 1\pmod m$.

$\square$

Tính chất 6. Hễ $\text{ord}_m(a)=d$ và số nguyên $r$ thỏa mãn $\gcd(r;\,m)=1$, thì các phần tử ở trong tập hợp $\mathcal A_r=\left\{r;\,ra;\,\ldots ;\,ra^{d-1}\right\}$ sẽ nguyên tố cùng nhau với $m$ và đôi một không cùng số dư trong phép chia cho $m$. Đồng thời, với $n\in\mathbb N$ luôn $\exists \mathfrak a\in\mathcal A_r:\;ra^n\equiv\mathfrak a\pmod m$.

Chứng minh.  Với $n\in\mathbb N$ bất kỳ do $\gcd(a;\,m)=\gcd(r;\,m)=1$ nên $\gcd\left(ra^n;\,m\right)=1$, vì thế các số trong tập $\mathcal A_r$ đều nguyên tố cùng nhau với $m$.

Lấy $ra^k;\,ra^l$ bất kỳ trong $\mathcal A_r$ với $k>l$, do $k-l\in\mathbb Z^+$ và $k-l<d$ nên\[m\nmid \left(a^{k-l}-1\right)\]Điều đó kết hợp với $\gcd\left(ra^l;\,m\right)=1$ để cho thấy\[m\nmid ra^l\left(a^{k-l}-1\right)\]Tức là $ra^k-ra^l$ không chia hết cho $m$, hay nói khác đi các phần tử của $\mathcal A_r$ sẽ đôi một không có cùng số dư khi chia $m$.

Cuối cùng, từ tính chất 1 mà thấy với $n\in\mathbb N$ bất kỳ thì $ra^n$ sẽ có cùng số dư với phần tử $\mathfrak a=ra^t\in\mathcal A_r$ trong đó $t$ là số dư của $n$ cho $d$.

$\square$

Tính chất 7.  Với $\varphi (m)$ là số các số nguyên dương không vượt quá $m$ và nguyên tố cùng nhau với $m$ khi đó $\text{ord}_m(a)$ luôn là ước của $\varphi(m)$.}

Chứng minh.  Đặt $\text{ord}_m(a)=d$ và giả sử tập các số nguyên dương không vượt quá $m$ và nguyên tố cùng nhau với $m$ là\[\mathcal R_m=\left\{r_1;\,r_2;\,\ldots;\,r_{\varphi(m)}\right\}\] Với mỗi $r_i\in\mathcal R_m$, ký hiệu\[\mathcal A_{r_i}=\left\{r_i;\,r_ia;\,\ldots;\,r_ia^{d-1}\right\}\]Ta cũng ký hiệu $\mathfrak{R}_{r_i}$ là tập các số dư khi chia cho $m$ của các phần tử trong $\mathcal A_{r_i}$.

Ta lấy ra hai phần tử bất kỳ $r;\,r’$ của $\mathcal R_m$ với $r\ne r’$. Trước tiên, từ tính chất 5 ta thấy rằng $\mathfrak{R}_r$ và $\mathfrak{R}_{r’}$ đều là các tập con của $\mathcal R_m$ và \[\left| {{\mathfrak{R}_r}} \right| = \left| {{A_r}} \right| = \left| {{\mathfrak{R}_{r’}}} \right| = \left| {{A_{r’}}} \right| = d\]
Lại thấy, nếu $\mathfrak{R}_r\cap \mathfrak{R}_{r’}\neq\emptyset$, lúc đó tồn tại $k;\,\in\mathbb N,\;k\ne l$ sao cho\[ra^k\equiv r’a^l\pmod m\]Cho nên $r\in \mathfrak{R}_{r’}$ hoặc $r’\in \mathfrak{R}_r$ do đó $\mathfrak{R}_r=\mathfrak{R}_{r’}$. Cuối cùng, để ý rằng một phần tử $r^*\in\mathcal R_m$ bất kỳ đều nằm trong tập $\mathfrak{R}_{r^*}$ (do $r^*\in \mathcal A_{r^*}=\left\{r^*;\,r^*a;\,\ldots;\,r^*a^{d-1}\right\}$ và $r^*$ chia $m$ dư chính nó) cho nên $\mathcal R_m$ là hợp của các tập rời nhau $\mathfrak{R}_{r_1},\;\mathfrak{R}_{r_2},\;\ldots \mathfrak{R}_{r_t}$ với\[\left| {{\mathfrak{R}_{{r_1}}}} \right| = \left| {{\mathfrak{R}_{{r_2}}}} \right| = \ldots = \left| {{\mathfrak{R}_{{r_t}}}} \right| = d\]Do vậy\[\left| {{\mathcal R_{{m}}}} \right| =\left| {{\mathfrak{R}_{{r_1}}}} \right| + \left| {{\mathfrak{R}_{{r_2}}}} \right| + \ldots + \left| {{\mathfrak{R}_{{r_t}}}} \right| = td\]Tức là, $d\mid\varphi(m)$.

$\square$

Tính chất này, cho ta ý tưởng để tìm $\text{ord}_m(a)$ trong trường hợp tổng quát. Đó là đi tìm các ước số $d$ của $\varphi(m)$, sau đó thử trực tiếp xem nó có thỏa mãn đồng dư $a^d\equiv 1\pmod m$ hay không. Để ý rằng, nếu $m=p_1^{k_1}p_2^{k_2}\ldots p_n^{k_n}$ trong đó $p_1;\,p_2;\,\ldots;\,p_n$ là các số nguyên tố với $p_1<p_2<\ldots <p_n$ còn $k_i\in\mathbb Z^+$ thì ta có công thức tính $\varphi(m)$ như sau
\[\varphi \left( m \right) = p_1^{{k_1} – 1}p_2^{{k_2} – 1} \ldots p_n^{{k_n} – 1}\left( {{p_1} – 1} \right)\left( {{p_2} – 1} \right) \ldots \left( {{p_n} – 1} \right)\]
Một ví dụ là tìm $\text{ord}_{9}(7)$, ta có:

1.  $\varphi(9)=6$, cho nên $\text{ord}_{9}(7)=d\mid 18$.
2. $7^1;\,7^2$ đều không chia $9$ dư 1, nhưng $7^3\equiv 1\pmod{9}$ từ đó $\text{ord}_{9}\left(7\right)=3$.

Một ví dụ khác là tìm $\text{ord}_{19}(2)$, ta có:

1.  $\varphi(19)=18$, cho nên $\text{ord}_{19}(2)=d\mid 18$.
2.  $2^2;\,2^3;\,2^6$ đều không chia $19$ dư 1, nhưng $2^9\equiv -1\pmod{19}$ từ đó $\text{ord}_{19}\left(2^{9}\right)=2$.
3.  $2=\text{ord}_{19}\left(2^{9}\right)=\dfrac{\text{ord}_{19}(2)}{\gcd(9;\,18)}$ vậy nên $\text{ord}_{19}(2)=18$.

Tóm lại, chúng ta có được giải pháp tính $\text{ord}_m(a)$ thay cho việc thử trực tiếp giá trị $d$ từ 1 đến lớn vào đồng dư $a^d\equiv 1\pmod m$ như sau.

1. Tính $\varphi(m)$ theo công thức tính phi-hàm Euler.
2. Liệt kê các ước của $\varphi(m)$ từ nhỏ đến lớn.
3. Tìm số dư của $a^d$ theo $\mod m$, với $d$ là các ước đã liệt kê ở bước trên.
4. $\text{ord}_m(a)=d$ là ước nhỏ nhất của $\varphi(m)$ thỏa mãn $a^d\equiv 1\pmod m$.

Thuật toán tìm cấp này, sẽ được cải tiến nhờ các tính chất sẽ được trình bày tiếp theo sau đây. Tuy nhiên, trước tiên ta cần đưa ngay ra định lý rất quan trọng trong Số Học sau đây.

Định lý Euler. Với $\varphi (m)$ là số các số nguyên dương không vượt quá $m$ và nguyên tố cùng nhau với $m$, khi đó\[a^{\varphi m}\equiv 1\pmod m\]

Chứng minh. Do $\varphi(m)$ là bội của $\text{ord}_m(a)$ (tính chất 7) và hệ quả 2 của tính chất 1 mà ta có điều cần chứng minh.

$\square$

Với số nguyên tố $p$ bất kỳ, từ $\mathcal R_p=\{1;\,2;\,\ldots;\,p-1\}$ nên $\varphi(p)=p-1$. Vì vậy, trong trường hợp $m=p$ thì định lý Euler trở thành định lý sau đây.

Định lý Fermat bé. Với $p$ là số nguyên tố và $p\nmid a$, khi đó\[a^{p-1}\equiv 1\pmod p\]

Cũng từ định lý Euler và tính chất 4, ta có ngay một dạng hay sử dụng của phép khai căn đồng dư như sau.

Tính chất 8. Hễ $\left(\varphi(m);\,n\right)=1$ thì từ $a^n\equiv 1\pmod m$ ta sẽ có\[a\equiv 1\pmod m\]

Cũng như vai trò của định lý Fermat bé với định lý Euler, ta cũng có một trường hợp riêng của tính chất 8, là hệ quả sau đây.

Hệ quả.  Với $p$ là một số nguyên tố, $p\nmid a$ và số nguyên dương $n$ thỏa $(n;\,p-1)$, khi đó $a^n\equiv 1\pmod p$ nếu và chỉ nếu $a\equiv 1\pmod p$.

Tính chất nêu dưới đây, sẽ cho chúng ta cách tính cấp của một số theo modulo tích.

Tính chất 9. Nếu $\gcd(m;\,m’)=\gcd(a;\,m)=\gcd(a;\,m’)=1$ thì $\text{ord}_{mm’}(a)$ sẽ là bội số chung nhỏ nhất của $\text{ord}_m(a)$ và $\text{ord}_{m’}(a)$

Chứng minh. Giả sử $\text{ord}_{mm’}(a)=D;\,\text{ord}_{m}(a)=d;\,\text{ord}_{m’}(a)=d’$, từ\[a^D\equiv 1\pmod{mm’}\]Ta có $d\mid D$ và $d’\mid D$, nói khác đi $D$ là một bội chung của $d$ và $d’;\;(1)$. Ngược lại, lấy $D^*$ là một bội chung bất kỳ của $d$ và $d’$ từ\[a^{D^*}\equiv 1\pmod m,\;a^{D^*}\equiv 1\pmod m’\]Ta có $a^{D^*}-1$ là bội chung của $m$ và $m’$ lại do $\gcd(m;\,m’)=1$ nên $a^{D^*}-1\;\vdots\;mm’$, tức là\[a^{D^*}\equiv 1\pmod{mm’};\;(2)\]Từ $(1)$ và $(2)$ ta có điều cần chứng minh

$\square$

Tính chất này, có một mở rộng tự nhiên như sau

Định lý. Với $m_1;\,m_2;\ldots;\,m_n$ là các số đôi một nguyên tố cùng nhau, khi đó\[\text{ord}_{m_1m_2\ldots m_n}(a)=\text{lcm}\left(\text{ord}_{m_1}(a);\,\text{ord}_{m_1}(a);\,\ldots;\, \text{ord}_{m_n}(a)\right)\]

Một thí dụ đơn giản là tìm $\text{ord}_{90}(7)$, ta có

1.  $90=2.5.3^2$.
2. $\text{ord}_2(7)=1;\,\text{ord}_5(7)=4;\,\text{ord}_9(7)=3.$

Vậy $\text{ord}_{90}(7)=\text{lcm}(1;\,4;\,3)=12$.

Như vậy, để tính $\text{ord}_m(a)$ ta viết $m=p_1^{k_1}p_2^{k_2}\ldots p_n^{k_n}$ trong đó $p_1;\,p_2;\,\ldots;\,p_n$ là các số nguyên tố với $p_1<p_2<\ldots <p_n$ còn $k_i\in\mathbb Z^+$. Sau đó, ta tính cấp $\text{ord}_{p_i^{k_i}}(a)=d_i$ rồi lấy bội số chung nhỏ nhất của các $d_i$ sẽ cho ta $\text{ord}_m(a)$, việc tìm cấp $d_i$ của các thành phần nguyên tố được dựa vào công thức sau.

Tính chất 10. Nếu $p$ là một số nguyên tố lẻ, $a$ là số nguyên không chia hết cho $p$. Giả sử $\text{ord}_p(a)=h$ và $v_p\left(a^h-1\right)=k$, khi đó với số nguyên dương $m$ ta có \[\text{ord}_{p^m}(a)=p^{\max\{m-k,\,0\}}h.\]

Một câu hỏi đặt ra là, ta đã biết $\text{ord}_m(a)\mid \varphi(m)$ liệu nếu ta lấy ra một ước $d$ bất kỳ của $\varphi(m)$ thì có tồn tại $a$ sao cho $\text{ord}_m(a)=d$ hay không? Tất nhiên trường hợp tổng quát là không đúng, như có một trường hợp thỏa sẽ được nêu ở tính chất sau đây.

Tính chất 11. Nếu $p$ là một số nguyên tố và $p\mid\varphi(m)$, thì sẽ tồn tại $a$ sao cho\[\text{ord}_m(a)=p\]

Chứng minh. Xét tập hợp\[\mathcal S = \left\{ {\left( {{x_1},\,{x_2},\, \ldots ,\,{x_p}} \right) \in {\mathcal R^p_m}:\,\,{x_1}{x_2} \ldots {x_p} = 1} \right\}.\]
Bởi vì $x_p$ xác định duy nhất khi ta đã biết $x_1,\ldots, x_{p-1}$ nên số phần tử của $\mathcal{S}$ bằng $|\mathcal R_m|^{p-1}$. Trong $\mathcal{S}$ xét quan hệ sau: $x\sim y$ nếu $x$ thu được từ $y$ bởi phép hoán vị vòng. Dễ thấy đây là một quan hệ tương đương, và một lớp theo quan hệ này có một phần tử khi và chỉ khi nó chứa $(x,\cdots, x)$ với $x^p=1$. Cũng thấy luôn rằng vì $p$ là số nguyên tố nên một lớp tương đương chỉ có thể có $1$ hoặc $p$ phần tử. Gọi $k$ là số lớp có 1 phần tử còn $q$ là số lớp có $p$ phần tử, thế thì ta sẽ có $|\mathcal R_m|^{p-1}=k+pq$, từ đây ta có $p\mid k$, nói riêng $k>1$. Như vậy ngoài lớp chứa $(1,1,…,1)$ còn có những lớp khác cũng gồm một phần tử, giả sử một trong các lớp này chứa $(x,x,…,x)$ thì $x$ là phần tử có bậc $p$.

$\square$

Chứng minh tương tự trong trường hợp $m=p^n$, ta sẽ thấy nếu $d\mid\varphi(m)$ thì luôn tồn tại phần tử cấp $d$. Lại để ý là trong các ước của $\varphi(m)$ thì có ước đặc biệt là chính nó. Những số nguyên dương $m$ mà có $a$ để $\text{ord}_m(a)=\varphi(m)$ lúc đó $a$ được gọi là căn nguyên thủy mod $m$. Những trường hợp $m\in\mathbb Z^+$ có căn nguyên thủy sẽ là một chủ đề ở một bài viết khác, trong bài viết này tôi đưa vấn đề đó vào phần bài tập.