Cho trước các số nguyên dương $m,\,n$, và số nguyên $a$ thỏa mãn $\gcd(a,\,m)=1$. Khi đó, với việc biết cấp của $a$ theo mod $m$ là $\text{ord}_m(a)=h$ chúng ta đã có được thuật toán tìm số dư $r$ của $a^n$ khi chia $m$ đó là.

•  Tìm số dư $r_0$ của $n$ khi đem chia cho $h$.
•  Tìm số dư $r$ khi đem $a^{r_0}$ chia cho $m$.

Công việc này dù rắc rối hơn đôi chút, nhưng cũng giống như vấn đề ở đại số sơ cấp đó là tính giá trị của lũy thừa $a^n$ khi biết trước $a$ và $n$. Cũng để ý rằng ở đại số sơ cấp, ta có bài toán ngược của bài toán tính giá trị lũy thừa. Đó là bài toán khai căn, cụ thể là với $a,\,n$ cho trước ta cần tìm $x$ sao cho\[x^n=a.\]Giá trị $x$ (nếu tồn tại), gọi là căn bậc $n$ của $a$. Đối với bài toán khai căn đó, có hai vấn đề đặt ra cần giải quyết.

1.  Tìm điều kiện cần và đủ với $a$, để tồn tại căn bậc $n$ của $a$.
2.  Với $a$ thỏa điều kiện tồn tại căn bậc $n$ của $a$, ta cần xác định tất cả các căn.

Ở trong Số Học ta cũng có hai bài toán về việc “khai căn” tương tự như vậy, đó là khi chúng ta cần xác định xem có tồn tại $x\in\mathbb{Z}$ sao cho $x^n\equiv a\pmod m$ hay không? Và nếu tồn tại thì giá trị của $x$ là bao nhiêu? Do đó, chúng ta cần quan tâm đến các khái niệm cơ bản sau.

Định nghĩa. Cho các số nguyên dương $m,\,n$ và số nguyên $a$ thỏa mãn $\gcd(a,\,m)=1$. Nếu tồn tại số nguyên $r$ sao cho\[a\equiv r^n\pmod m.\] Ta nói $a$ là một thặng dư bậc $n$ theo mod $m$, còn $r$ là một căn bậc $n$ của $a$ theo mod $m$.

Với điều kiện $\gcd(a,\,m)=1$ và $a$ là một thặng dư bậc $n$ theo mod $m$ (tức là có thể khai căn bậc $n$ của $a$ theo mod $m$), khi đó nếu $r$ là một căn bậc $n$ theo mod $m$ của $a$ thì rõ ràng $\gcd(r,\,m)=1$. Thêm nữa, nếu $r_*^n\equiv a\pmod m$ và $r\equiv r_*\pmod m$ thì $r^n\equiv a\pmod m$. Do đó, từ nay về sau khi ta nói “$r$ là một căn bậc $n$ của $a$ theo mod $m$” thì ta tự hiểu $r\in\mathcal{U}_m$ với $\mathcal{U}_m$ là nhóm đơn vị mod $m$, tức là $\mathcal{U}_m=\left\{u\in\mathbb{Z}^+:\;u\le m,\,\gcd(u,\,m)=1\right\}$.

Như vậy, nếu muốn xác định xem $a$ có là thặng dư bậc $n$ theo mod $m$ hay không cũng như đi tìm các căn bậc $n$ của $a$ theo mod $m$, ta có một cách rất thô sơ là đem thử trực tiếp các phần tử $u\in\mathcal{U}_m$ xem nó có thỏa mãn điều kiện $u^n\equiv a\pmod m$ hay không? Ta xét một số ví dụ sau đây.

Ví dụ 1.  Với $m=18,\,n=2$ ta có bảng sau với $u\in\mathcal{U}_{18}=\{1,\,5,\,7,\,11,\,13,\,17\}$, còn $r_{u^2}$ là số dư của $u^2$ khi chia $18$.

Từ bảng trên ta thấy $2005$ là một thặng dư bậc hai theo mod 18, do\[5^2\equiv 13^2\equiv 2005\pmod{18}.\]

Cũng từ bảng đó ta thấy rằng có đúng hai căn bậc hai của 2005 theo mod 18, là $r_1=5$ và $r_2=21$. Còn $2009$ không là thặng dư bậc hai mod 18, do $2009\equiv 11\pmod{18}$ và không tồn tại $u\in\mathcal{U}_{18}$ sao cho\[u^2\equiv r_{u^2}\equiv 11\equiv 2009\pmod{18}.\]

Ví dụ 2. Với $m=14,\,n=3$, bảng số dư của lũy thừa bậc 3 của các phần tử thuộc $\mathcal{U}_{14}$ là.

Theo bảng được lập ra ở trên, ta thấy $a$ là một thặng dư bậc ba theo mod 14 khi và chỉ khi $a$ có dạng $14k+1$ hoặc $14k-1$ với $k\in\mathbb{Z}$.

1.  Nếu $a=14k+1$, thì có ba căn bậc ba theo mod $14$ của $a$ là $1,\,9$ và $11$.
2.  Nếu $a=14k-1$, thì có ba căn bậc ba theo mod $14$ của $a$ là $3,\,5$ và $13$.

Ví dụ 3. Với $m=11,\,n=7$ và $a\in\mathcal{U}_{11}=\{1,\,2,\,\ldots\,10\}$, khi đó theo Fermat bé ta có\[a\equiv a.\left(a^{10}\right)^2\equiv \left(a^3\right)^7\pmod{11}.\]Cho nên nếu gọi $r_a$ là số dư của $a^3$ khi chia $11$, thế thì do $a\in\mathcal{U}_{11}$ nên $r_a\in\mathcal{U}_{11}$ thêm nữa\[a\equiv\left(a^3\right)^7\equiv\left(r_a\right)^7\pmod{11}.\]Tức là $r_a$ là một căn bậc $7$ của $a$ theo mod $11$, và do đó ta thấy mọi số nguyên không là bội của $11$ đều là thặng dư bậc $7$ theo mod $11$.

Bây giờ với $a\in\mathbb{Z}$ thỏa $11\nmid a$, nếu $r_1$ và $r_2$ đều là căn bậc $7$ của $a$ theo mod $11$. Thế thì ta có được $r_1^7\equiv r_2^7\equiv a\pmod{11}$, nên\[r_1^{21}\equiv\left(r_1^7\right)^3\equiv a^3\equiv\left(r_2^7\right)^3\equiv r_2^{21}\pmod{11}.\]
Nhưng với mọi $r\in\mathcal{U}_{11}$ do $r^{21}\equiv r\pmod{11}$ (Fermat bé), nên ta sẽ có được\[r_1\equiv r_2\pmod{11}.\]
Như vậy mọi số nguyên $a$ không là bội số của $11$ đều là một thặng dư bậc $7$ theo mod $11$, và mỗi số nguyên $a$ như thế sẽ có duy nhất một căn bậc $7$ theo mod $11$.

Rõ ràng khi giá trị $m,\,n$ lớn, việc kiểm soát bảng số dư $r_{u^n}$ với $u\in\mathcal{U}_m$ qua việc tính toán trực tiếp là một suy nghĩ ngây thơ. Do đó ở phần tiếp theo sau đây, chúng ta cần phân tích lý thuyết để tìm hiểu điều kiện cần và đủ để số nguyên $a$ là một thặng dư bậc $n$ theo mod $m$. Trong đó $m,\,n$ là các số nguyên dương cho trước và $\gcd(a,\,m)=1$.