Với các số nguyên dương $m,\,n$ cho trước và $a$ là một số nguyên nguyên tố cùng nhau với $m$, xét phương trình đồng dư\begin{align}x^n\equiv a\pmod m,\qquad (1).\end{align}Ở các phần phía trước bao gồm http://songha.maths.vn/khai-niem-thang-du-bac-cao-va-can-theo-modulo/, http://songha.maths.vn/dieu-kien-la-mot-thang-du-bac-cao/ và http://songha.maths.vn/so-cac-thang-du-bac-cao/ thì về cơ bản thì chúng ta đã giải quyết được hai vấn đề, đó là

• Điều kiên cần và đủ của $a$ theo $m$ và $n$ để phương trình đồng dư đó có nghiệm.
• Số các $a\in\mathcal U_m$ sao cho phương trình đồng dư đó có nghiệm.

Bây giờ, nếu cho trước $a$ là một thặng dư bậc $n$ theo mod $m$ tức là giá trị của $a$ đảm bảo cho phương trình đồng dư trên có nghiệm thì vấn đề đặt ra là cấu trúc các nghiệm của nó ra sao? Nói khác đi, khi biết chắc có thể khai căn bậc $n$ của $a$ theo mod $m$, thì các căn đó sẽ được xác định ra sao? Và đó chính là mục đích của phần này.

Khi $a$ là một thặng dư bậc $n$ theo mod $m$, gọi $r$ là một căn bậc $n$ theo mod $m$ của $a$, do $r\in\mathcal U_m$ nên tồn tại $r_{-1}$ là nghịch đảo của $r$ theo theo mod $m$ và ta có\[ar_{ – 1}^n \equiv {\left( {r{r_{ – 1}}} \right)^n} \equiv 1.\]Nhân hai vế của phương trình $(1)$ với $r_{-1}^n$ và đặt $xr_{-1}=X$, ta có phương trình $(1)$ trở thành\begin{align}X^n\equiv 1\pmod m,\qquad (2).\end{align}
Chú ý rằng mỗi nghiệm $x_*$ nào đó của $(1)$, cũng sẽ sinh ra một nghiệm $X_*=x_*r_{-1}$ của $(2)$ và ngược lại (với $x_*=X_*r$). Do vậy, về bản chất thì muốn giải $(1)$ ta chỉ cần xử lý $(2)$.

Viết phân tích $m$ ra thừa số nguyên tố dưới dạng\[m = p_1^{{k_1}}p_2^{{k_2}} \ldots p_t^{{k_t}}.\]Khi đó mỗi nghiệm $X_*$ của $(2)$ cũng là nghiệm của từng phương trình trong $t$ phương trình đồng dư sau\[X^n\equiv 1\pmod{p_i^{k_i}},\quad i=\overline{1,\,t}.\]Đảo lại, nếu với mỗi $i=\overline{1,\,t}$ phương trình $X^n\equiv 1\pmod{p_i^{k_i}}$ có nghiệm $X_i\in\mathcal U_{p_i^{k_i}}$ nào đó, thì theo định lý thặng dư Trung Hoa mỗi bộ $\left(X_1,\,X_2,\,\ldots,\,X_t\right)$ sẽ ứng với duy nhất một nghiệm $X_*\in\mathcal U_m$ của phương trình $(2)$ thỏa mãn\[X_*\equiv X_i\pmod{p_i^{k_i}}\quad\forall\,i=\overline{1,\,t}.\]Nghiệm $X_*$ này xác định bởi công thức (trong đó $P_i=\dfrac{m}{p_i^{k_i}}$) là\[{X_*} = {X_1}P_1^{\varphi \left( {p_1^{{k_1}}} \right)} + {X_2}P_2^{\varphi \left( {p_2^{{k_2}}} \right)} + \ldots + {X_t}P_t^{\varphi \left( {p_t^{{k_t}}} \right)}.\]
Những lý luận đó cho ta thấy rằng, mọi vấn đề quy về các phương trình đồng dư ở dạng\[x^n\equiv 1\pmod{p^k},\text{với}\;p\in\mathbb P,\,k\in\mathbb Z^+.\]
Ta xét trường hợp đầu tiên, đó là các phương trình dạng\[x^n\equiv 1\pmod{2^k},\qquad (3)\]

1. Nếu $n$ lẻ, từ $x^n\equiv 1\pmod{2^k}$ ta có luôn $x\equiv 1\pmod{2^k}$ do\[{v_2}\left( {x – 1} \right) = {v_2}\left( {{x^n} – 1} \right).\]Tức là trong mod $2^k$, ta có nghiệm duy nhất của phương trình $(3)$ là $x_0=1$.
2. Nếu $n$ chẵn và $v_2(n)+2>k$, từ\[{v_2}\left( {{x^n} – 1} \right) = {v_2}\left( {{x^2} – 1} \right) + {v_2}\left( n \right) – 1 \ge {v_2}\left( n \right) + 2.\]Vậy trong mod $2^k$, thì mọi phần tử của $\mathcal U_{2^k}$ đều là nghiệm của $(3)$.
3. Nếu $n$ chẵn và $v_2(n)+2\le k$, thế thì nếu $x$ là nghiệm của phương trình ta sẽ có\[{v_2}\left( {{x^2} – 1} \right) = {v_2}\left( {{x^n} – 1} \right) – {v_2}\left( n \right) + 1 \ge k – {v_2}\left( n \right) + 1.\]Cũng để ý thêm là $\gcd(x-1,\,x+1)=2$ với $x$ lẻ, nên phương trình $(3)$ tương đương với $x\equiv 1\pmod{2^{k-v_2(n)}}$ hoặc $x\equiv -1\pmod{2^{k-v_2(n)}}$. Tức là trong $\mathcal U_{2^k}$, các nghiệm của $(3)$ có dạng\[{x_t} = {2^{k – {v_2}\left( n \right)}}t + 1,\qquad {x_{t’}} = {2^{k – {v_2}\left( n \right)}}t’ – 1.\]
   Ở đây $t=\overline{0,\,2^{v_2(n)}-1},\,t’=\overline{1,\,2^{v_2(n)}}$, và ta có số nghiệm là $2^{1+v_2(n)}$.

Như vậy ta có định lý sau đây.

Định lý 1. Với $n,\,k$ là các số nguyên dương cho trước, trên $\mathcal U_{2^k}$ xét phương trình\[x^n\equiv 1\pmod{2^k}.\]

1. Nếu $n$ lẻ thì phương trình đó có nghiệm duy nhất là $x_0=1$.
2. Nếu $n$ chẵn và $v_2(n)>k-2$ thì phương trình đó có $2^{k-1}$, và tập nghiệm của nó là $\mathcal U_{2^k}$.
3. Nếu $n$ chẵn và $v_2(n)\le k-2$ thì phương trình đó có $2^{1+v_2(n)}$ nghiệm, tập nghiệm của nó sẽ là\[\left\{ {{2^{k – {v_2}\left( n \right)}}t + 1,\,{2^{k – {v_2}\left( n \right)}}\left( {t + 1} \right) – 1:\quad t = \overline{0,\,2^{v_2(n)}-1}} \right\}.\]

Ta xét ví dụ như sau.

Ví dụ 1. Với $n=2019$ và $k=5$, thì do $2019$ là số lẻ nên có duy nhất một căn bậc $2019$ của đơn vị trong $\mathcal U_{32}$. Tức là tất cả các căn bậc $2019$ của đơn vị theo mod $32$ sẽ có dạng $32k+1,\,k\in\mathbb Z.$

Với $n=6$ và $k=5$, ta có $v_2(6)=1<5-2$ nên ta sẽ có tất cả $2^{1+1}$ nghiệm của phương trình $x^6\equiv 1\pmod{32}$ trong $\mathcal U_{32}$, đó là\[x_1=1,\quad x_2=17,\quad x_3=15,\quad x_4=31.\]
Với $n=8$ và $k=5$, ta sẽ có tất cả $16$ căn bậc $8$ của đơn vị theo mod $32$ trong $\mathcal U_{32}$. Điều đó cũng có nghĩa là, mọi số lẻ đều là căn bậc $8$ của đơn vị theo mod $32$.

Bây giờ với $p\in\mathbb P\setminus\{2\}$ và $k\in\mathbb Z^+$, trên $\mathcal U_{p^k}$ ta xét đến phương trình \begin{align}x^n\equiv 1\pmod{p^k},\qquad (4)\end{align}Gọi căn nguyên thủy mod $p^k$ là $\mathfrak g$, với $x\in\mathcal U_{p^k}$ khi đó sẽ tồn tại duy nhất chỉ số của $x$ theo mod $p^k$ là $i_x\in\left[\varphi\left(p^k\right)\right]$ sao cho $x\equiv\mathfrak{g}^{i_x}\pmod{p^k}$. Vì $\text{ord}_{p^k}\left(\mathfrak g\right)=\varphi\left(p^k\right)$, nên từ $(4)$ có điều kiện tương đương là\begin{align}\varphi\left(p^k\right)\mid i_xn,\qquad (5)\end{align}Giả sử $\gcd\left(n,\,\varphi\left(p^k\right)\right)=d$, ta viết $\varphi\left(p^k\right)=Md,\,n=Nd$ với $M,\,\in\mathbb Z^+$ và $\gcd(M,\,N)=1$. Điều kiện $(5)$ khi này trở thành $M\mid i_x$, tức là $i_x=tM$ với $t\in [d]$, và ta có khẳng định sau.

Định lý 2. Với $p$ là số nguyên tố lẻ và $n,\,k$ là các số nguyên dương cho trước, giả sử $\gcd\left(n,\,\varphi\left(p^k\right)\right)=d$ khi đó trên $\mathcal U_{p^k}$ phương trình $x^n\equiv 1\pmod{p^k}$ sẽ có đúng $d$ nghiệm là\[{x_t} = {\mathfrak g^{\frac{{t\varphi \left( {{p^k}} \right)}}{d}}},\quad t=\overline{1,\,d}.\]

Xét một ví dụ như sau.

Ví dụ 2. Với $n=6$, $p=3$ và $k=2$. Khi đó do $2$ là căn nguyên thủy mod $9$, đồng thời $d=\gcd(6,\,\varphi(9))=6$ cho nên có đúng $6$ căn bậc $6$ của đơn vị theo mod $9$ trong $\mathcal U_9$ bao gồm\[x_1=2^0,\,x_2=2^1,\,x_3=2^2,\,x_4=2^3,\,x_5=7\equiv 2^4\pmod{9},\,x_6=5\equiv 2^5\pmod 9.\]

Với các công việc đã xử lý, nếu $a$ là một thặng dư bậc $n$ theo mod $m$ và biết trước $r$ là một căn bậc $n$ theo mod $m$ của $a$. Ta có thuật toán khai căn bậc $n$ theo mod $m$ sau đây.

Thuật toán khai căn theo modulo

Bước 1. Phân tích $m$ ra thừa số nguyên tố, tức là viết\[m = {2^k}p_1^{{k_1}}p_2^{{k_2}} \ldots p_t^{{k_t}},\;p_i\in\mathbb P,\;2 < {p_1} < {p_2} < \ldots < {p_t},\;k \in \mathbb N,\;{k_i} \in {\mathbb Z^+ }.\]
Bước 2. Sử dụng định lý 4.1 để tìm $x_0$ thỏa $x_0^n\equiv 1\pmod{2^k}$.

Bước 3. Sử dụng định lý 4.2 để tìm số các $x_i$ thỏa $x_i^n\equiv 1\pmod{p_i^k}.$

Bước 4. Các căn bậc $n$ của $a$ theo mod $m$, sẽ được xác định bởi công thức\[{r_*} =r\left({x_0}P_0^{{2^k}} + {x_1}P_1^{\varphi \left( {p_1^{{k_1}}} \right)} + {x_2}P_2^{\varphi \left( {p_2^{{k_2}}} \right)} + \ldots + {x_t}P_t^{\varphi \left( {p_t^{{k_t}}} \right)}\right) .\]Ở đây, với mỗi $i=\overline{1,\,t}$ thì $P_i=\dfrac{m}{p_i^{k_i}},\,P_0=\dfrac{m}{2^k}$.