Cho các số nguyên dương $m,\,n$ và số nguyên $a$ thỏa mãn $\gcd(a,\,m)=1$, giả sử phân tích ra thừa số nguyên tố của $m$ là\[m=p_1^{k_1}p_2^{k_2}\ldots p_t^{k_t}.\]Trong đó, $k_i\in\mathbb{Z}^+,\,p_i\in\mathbb P,\;\forall\,i=\overline{1,\,t}$ và $p_1<p_2<\ldots<p_t$.

Nếu $a$ là một thặng dư bậc $n$ theo mod $m$, thì từ $a\equiv r^n\pmod m$ với $r$ là một căn bậc $n$ của $a$ theo mod $m$, ta có\[a\equiv r^n\pmod{p_i^{k_i}}\quad\forall\,i=\overline{1,\,t}.\]
Điều này cho chúng ta thấy, nếu $a$ là một thặng dư bậc $n$ theo mod $m$ thì nó cũng là một thặng dư bậc $n$ theo mod $p_i^{k_i}$ với mọi $i=\overline{1,\,t}$.

Đảo lại, nếu với mỗi $i=\overline{1,\,t}$ ta có $a$ là một thặng dư bậc $n$ theo mod $p_i^{k_i}$. Nghĩa là với mỗi $i=\overline{1,\,t}$ lại tồn tại một $r_i\in\mathcal{U}_{p_i^{k_i}}$ sao cho\[a\equiv r_i^{n}\pmod{p_i^{k_i}}.\]Theo định lý thặng dư Trung Hoa, với mỗi bộ $\left(r_1,\,r_2,\,\ldots,\,r_t\right)$ như thế sẽ tồn tại duy nhất một $\mathfrak{r}\in\mathcal{U}_m$ sao cho\[\mathfrak{r}\equiv r_i\pmod{p_i^{k_i}}\quad\forall\,i=\overline{1,\,t}.\]Lúc đó rõ ràng rằng $\mathfrak{r}$ là một căn bậc $n$ của $a$ theo mod $m$, nói khác đi\[a\equiv \mathfrak{r}^n\pmod m.\]Tóm tắt những lý luận trên, ta có định lý sau.

Định lý 1. Giả sử $m=m_1m_1$ với $m_1,\,m_2\in\mathbb Z^+$ và $\gcd\left(m_1,\,m_2\right)=1$ và $n$ là một số nguyên dương, khi đó số nguyên $a$ nguyên tố cùng nhau với $m$ và là một thặng dư bậc $n$ theo mod $m$ khi và chỉ khi $a$ vừa là thặng dư bậc $n$ theo mod $m_1$ đồng thời là thặng dư bậc $n$ theo mod $m_2$.

Như vậy, $a$ là một thặng dư bậc $n$ theo mod $m$ khi và chỉ khi $a$ là một thặng dư bậc $n$ theo mod $p_i^{k_i}$ với mỗi một chỉ số $i=\overline{1,\,t}$. Lý do đó khiến chúng ta thấy rằng, bài toán tìm điều kiện để $a$ là một thặng dư bậc $n$ theo mod $m$ sẽ quy về trường hợp $m=p^k$ với $p\in\mathbb P$ và $k\in\mathbb{Z}^+$.

Ta xét trường hợp đầu tiên, đó là khi $m=2^k$ với $k\in\mathbb Z^+$. Ta cần đến bổ đề sau.

Bổ đề. Với mỗi số nguyên dương $k$ (với $k\ge 3$) và số nguyên $a$ lẻ cho trước, luôn tồn tại các số nguyên dương $s,\,t$ với $s\in\{1,\,2\}$ và $t\le 2^{k-2}$ sao cho\[a\equiv (-1)^s5^t\pmod{2^k}.\]

Chứng minh. Với $k\ge 3$ ta xét\[\mathcal R=\left\{(-1)^s5^{t}:\;s=\overline{1,\,2},\,t\in \left[2^{k-2}\right]\right\}.\]Ta thấy rằng $\left|\mathcal R\right|=\varphi\left(2^k\right)=2^{k-1}$, các phần tử của $\mathcal R$ đều là số nguyên lẻ nên đều nguyên tố cùng nhau với $2^k$, thêm nữa do $\text{ord}_{2^k}\left(5\right)=2^{k-2}$ nên để\[{\left( { – 1} \right)^{{s_1}}}{5^{{t_1}}} \equiv {\left( { – 1} \right)^{{s_2}}}{5^{{t_2}}}\pmod{2^k},\]thì $s_1,\,s_2$ cùng tính chẵn lẻ và $t_1\equiv t_2\pmod{2^{k-2}}$ và điều đó xảy đến khi và chỉ khi $t_1=t_2$. Những điều này cho thấy $\mathcal R$ là một hệ thặng dư thu gọn mod $2^k$. Và đó chính là điều ta cần chứng minh.

$\square$

Quay lại mục đích tìm các thặng dư bậc $n$ theo mod $2^k$, ta viết $n=2^tl$ với $t\in\mathbb N$ và $l$ là một số nguyên dương lẻ và xét các tình huống.

1. Nếu $t=0$, thì do $\gcd\left(2^k,\,n\right)=1$ nên theo định lý Bézout luôn tồn tại các số tự nhiên $\alpha ,\,\beta$ sao cho\[2^k\alpha-\beta n=1.\] Ta lại lưu ý rằng $a$ lẻ và $k\in\mathbb Z^+$ nên\[v_2\left(a^{2^k\alpha}-1\right)=v_2\left(a^2-1\right)+v_2\left(2^{k-1}\alpha\right)\ge k+2>k.\]Từ đó $2^k\mid\left(a^{2^k\alpha}-1\right)$ ta có được\[{\left( {{a^\beta }} \right)^n} = {a^{\beta n}} = {a^{{2^k}\alpha + 1}} = a + a\left( {{a^{{2^k}\alpha }} – 1} \right) \equiv a\pmod{2^k}.\]
   Vậy, $a$ là thặng dư bậc $n$ theo mod $2^k$ vì nó có một căn bậc $n$ theo mod $2^k$ là $a^{\beta}$.
2. Nếu $t\in\mathbb Z^+$ và $k\le t+2$, khi đó với $r$ là số nguyên lẻ bất kỳ ta có\[{v_2}\left( {{r^n} – 1} \right) = {v_2}\left( {{r^{{2^t}l}} – 1} \right) = {v_2}\left( {{r^2} – 1} \right) + {v_2}\left( {{2^{t – 1}}l} \right) \ge 3 + t – 1 \ge k.\]Từ đó nếu $a$ có căn bậc $n$ theo mod $2^k$ là $r$ thì\[a\equiv r^n\equiv 1\pmod{2^k}.\]
   Đảo lại, hễ $a\equiv 1\pmod{2^k}$ thì rõ ràng $1$ là một căn bậc $n$ theo mod $2^k$ của $a$. Cho nên, trong trường hợp này thì $a$ là thặng dư bậc $n$ theo mod $2^k$ khi và chỉ khi $$a\equiv 1\pmod{2^k}.$$
3. Nếu $t\in\mathbb Z^+$ và $k>t+2$, nếu $a$ có căn bậc $n$ theo mod $2^k$ là $r$ thì\[a \equiv {r^n} \pmod{2^k}.\]Đồng thời ta lại có\[{v_2}\left( {{r^n} – 1} \right) = {v_2}\left( {{r^{{2^t}l}} – 1} \right) = {v_2}\left( {{r^2} – 1} \right) + {v_2}\left( {{2^{t – 1}}l} \right) \ge 3 + t – 1 = t + 2.\]Như vậy ta có điều kiện cần là\[a \equiv 1\pmod{2^{t+2}}.\]Ta sẽ chứng minh đó đồng thời là điều kiện đủ.Thật vậy, nếu $a \equiv 1\pmod{2^{t+2}}$ thì theo bổ đề sẽ luôn tồn tại các số nguyên dương $s_a,\,t_a$ với $s_a\in\{1,\,2\}$ còn $t_a\le 2^{k-2}$ sao cho\[{\left( { – 1} \right)^{{s_a}}}{5^{{t_a}}} \equiv a\pmod{2^k}.\]Giờ do $a\equiv 1\pmod{2^{t+2}}$ nên $s_a=2$ và vì $k>t+2$ nên ta có\[a\equiv 5^{t_a}\equiv 1\pmod{2^{t+2}}.\] Rõ ràng $8\mid 2^{t+2}$ nên $t_a$ chẵn, và vì thế ta có đánh giá sau\[t + 2 \le {v_2}\left( {{5^{{t_a}}} – 1} \right) = {v_2}\left( {{5^2} – 1} \right) + {v_2}\left( {{t_a}} \right) – 1 = {v_2}\left( {{t_a}} \right) + 2.\]Từ đó $t_a=2^tq$, với $q$ là một số nguyên dương. Giờ để ý $l$ là số nguyên dương lẻ nên tồn tại nghịch đảo của nó là $l’$ theo mod $2^{k-t-2}$, từ đó\[nql’={2^t}qll’ = {2^t}q + {2^t}q\left( {ll’ – 1} \right) \equiv2^tq\equiv {t_a}\pmod{2^{k-2}}.\] Ta chọn $r=5^{ql’}$ và để ý $\text{ord}_{2^k}(5)=2^{k-2}$ để có\[{r^n} = {5^{{2^t}qll’}} \equiv {5^{{t_a}}} \equiv a\pmod{2^k}.\]Điều này thông báo $a$ là thặng dư bậc $n$ theo mod $2^k$.

Tổng hợp những lý luận ở trên, ta có định lý sau đây.

Định lý 2. Cho $a$ là một số nguyên lẻ và các số nguyên dương $n,\,k$.

1. Khi $n$ lẻ, thì $a$ luôn là một thặng dư bậc $n$ theo mod $2^k$.
2. Khi $n$ chẵn, thì $a$ là một thặng dư bậc $n$ theo mod $2^k$ nếu và chỉ nếu\[a \equiv 1\pmod{2^{\min \left\{ {k,\,2 + {v_2}\left( n \right)} \right\}}}.\]

Bây giờ với $m=p^k$ trong đó $p$ là một số nguyên tố lẻ, giả sử $\mathfrak{g}$ là một căn nguyên thủy mod $m$, thì do tính chất của căn nguyên thủy đã trình bày ở http://songha.maths.vn/can-nguyen-thuy/ ta có $\left\{\mathfrak{g},\,\mathfrak{g}^2,\,\ldots\,\mathfrak{g}^{\varphi(m)}
\right\}$ là một hệ thặng dư thu gọn mod $m$, do vậy nếu $a,\,r\in\mathcal{U}_m$ thì tồn tại tương ứng $i_a,\,i_r\in [\varphi(m)]$ sao cho \[a\equiv\mathfrak{g}^{i_a}\pmod m,\;r\equiv\mathfrak{g}^{i_r}\pmod m.\]Lúc này, đồng dư thức $a\equiv r^n\pmod m$ tương đương với $\mathfrak{g}^{i_a}\equiv\mathfrak{g}^{ni_r}\pmod m$. Ta lại lưu ý rằng $\text{ord}_m\left(\mathfrak{g}\right)=\varphi(m)$, cho nên ta có điều kiện tương đương là\[i_a\equiv n i_r\pmod{\varphi(m)}.\]Đặt $\gcd\left(n,\,\varphi(m)\right)=d$, thế thì điều kiện cần và đủ sẽ là $d\mid i_a$ và ta có định lý sau đây.

Định lý 3. Với $m=p^k$, trong đó $p\in\mathbb P\setminus\{2\},\,k\in\mathbb{Z}^+$. Điều kiện cần và đủ để $a$ là thặng dư bậc $n$ theo mod $m$ là \[a^{\frac{\varphi\left(m\right)}{\gcd\left(n,\,\varphi(m)\right)}}\equiv 1\pmod{m}.\]

Chứng minh. Giả sử $\mathfrak{g}$ là một căn nguyên thủy theo mod $m$, và $i_a\in [\varphi(m)]$ là chỉ số thỏa mãn đồng dư $a\equiv\mathfrak{g}^{i_a}\pmod m$, ta cũng gọi $\gcd\left(n,\,\varphi(m)\right)=d$ và viết $\varphi(m)=Md,\,n=Nd$ trong đó $\gcd(M,\,N)=1$, ta xét.

1. Nếu $a^M\equiv 1\pmod m$, ta có\[\mathfrak{g}^{i_aM}\equiv 1\pmod m.\] Cho nên $\text{ord}_m\left({\mathfrak{g}}\right)\mid i_aM$ mà $\text{ord}_m\left({\mathfrak{g}}\right)=\varphi(m)=Md$ nên $d\mid i_a$ tức $i_a=\alpha d$ với $\alpha\in\mathbb{Z}^+$. Lại do $\gcd\left(n,\,\varphi(m)\right)=d$ nên theo định lý Bézout tồn tại $k,\,l\in\mathbb N$ sao cho $$d=kn-l\varphi(m).$$Từ đó mà có được\[a \equiv {\mathfrak{g}^{{i_a}}} \equiv {\mathfrak{g}^{\alpha d}} \equiv {\mathfrak{g}^{\alpha d + \alpha l\varphi \left( m \right)}} \equiv {\mathfrak{g}^{\alpha kn}} \equiv {\left( {{\mathfrak{g}^{\alpha k}}} \right)^n}\pmod m.\]
   Vậy, $r_{\alpha}=\mathfrak{g}^{\alpha k}$ là một căn bậc $n$ của $a$ theo mod $m$ và bởi thế nên $a$ là một thặng dư bậc $n$ theo mod $m$.
2. Nếu $a$ là một thặng dư bậc $n$ theo mod $m$ khi đó sẽ có một căn bậc $n$ theo mod $m$ của $a$ là $r$. Do $a\equiv r^n\pmod m$, nên ta có\[{a^M} \equiv {r^{Mn}} \equiv {r^{MNd}} \equiv {\left( {{r^{\varphi \left( m \right)}}} \right)^N} \equiv 1\pmod m.\]

Với hai chiều đã xét, ta có điều cần chứng minh cho định lý.

$\square$

Bây giờ ta xét một ví dụ như sau.

Ví dụ 1. Ta sẽ xét xem $19$ có là thặng dư bậc $7$ mod $2016$ hay không?

Trước hết ta có phân tích $2016 = {2^5}{{.3}^2}{{.7}^1},\;$ đồng thời\[{\dfrac{{\varphi \left( {{3^2}} \right)}}{{\gcd \left( {7,\,\varphi \left( {{3^2}} \right)} \right)}} = \dfrac{{\varphi \left( 7 \right)}}{{\gcd \left( {7,\,\varphi \left( 7 \right)} \right)}} =\varphi \left( {{3^2}} \right)=\varphi \left( {{7}} \right).}\]Vậy nên ta có các đồng dư sau\begin{align*}
{19^{\frac{{\varphi \left( {{3^2}} \right)}}{{\gcd \left( {7,\,\varphi \left( {{3^2}} \right)} \right)}}}} = {19^{\varphi \left( {{3^2}} \right)}} \equiv 1\pmod{3^2},\\
{19^{\frac{{\varphi \left( 7 \right)}}{{\gcd \left( {7,\,\varphi \left( 7 \right)} \right)}}}} = {19^{\varphi \left( 7 \right)}} \equiv 1\pmod 7.
\end{align*}Điều này kết hợp với $7$ là một số nguyên dương lẻ, cho thấy rằng $19$ là một thặng dư bậc $7$ theo mod $2016$.

Viết ra thì nhiêu khê, chứ thực tế thì ở ví dụ trên chúng ta cũng không cần phải tính toán các lũy thừa. Nguyên nhân là bởi vì \[\gcd\left(7,\, \varphi(2016)\right) =\gcd\left(7,\,2^4.6.6\right)=1.\]Cho nên, có sẵn các đồng dư như đã thấy. Tổng quát tình huống này lên, ta có hệ quả sau.

Hệ quả. Cho các số nguyên dương $m,\,n$ thỏa mãn $\gcd\left(n,\,\varphi(m)\right)=1$. Khi đó nếu số nguyên $a$ nguyên tố cùng nhau với $m$, thì $a$ luôn là một thặng dư bậc $n$ theo mod $m$, tức là luôn tồn tại $r\in\mathcal U_m$ sao cho\[a\equiv r^n\pmod m.\]

Chứng minh.Theo định lý Bézout sẽ tồn tại các số tự nhiên $k,\,l$ thỏa mãn\[kn-l\varphi(m)=1.\]Khi đó nếu $\gcd(a,\,m)=1$ thì theo định lý Euler ta có\[{\left( {{a^k}} \right)^n} = {a^{1 + l\varphi \left( m \right)}} = a.{\left( {{a^{\varphi \left( m \right)}}} \right)^l} \equiv a\pmod m.\]
Vậy $a$ có một căn bậc $n$ theo mod $m$ là $a^{k}$, vì thế $a$ là một thặng dư bậc $n$ theo mod $m$.

$\square$

Bây giờ ta sẽ xét một ví dụ khác, cần tính toán một chút.

Ví dụ 2.Ta xét xem $145$ có là thặng dư bậc $6$ mod $2016$ hay không?

Lúc này ta sẽ có $\min\left\{5,\,2+v_2(6)\right\}=3$, và $145\equiv 1\pmod{2^3}$ nên $145$ là một thặng dư bậc $6$ theo mod $2^5$. Đồng thời ta lại thấy\[\frac{{\varphi \left( {{3^2}} \right)}}{{\gcd \left( {6,{\mkern 1mu} \varphi \left( {{3^2}} \right)} \right)}} =\frac{{\varphi \left( 7 \right)}}{{\gcd \left( {6,{\mkern 1mu} \varphi \left( 7 \right)} \right)}} = 1.\]Rõ ràng là $
{145^{\frac{{\varphi \left( {{3^2}} \right)}}{{\gcd \left( {6,\,\varphi \left( {{3^2}} \right)} \right)}}}} = {145^{1}} \equiv 1\pmod{3^2}$, chỉ có điều không xảy đến đồng dư$${145^{\frac{{\varphi \left( 7 \right)}}{{\gcd \left( {6,\,\varphi \left( 7 \right)} \right)}}}} = {145^{1}} \equiv 1\pmod 7.$$Điều này cho thấy rằng $145$ không là một thặng dư bậc $6$ theo mod $2016$.

Cũng từ những tính toán ở ví dụ vừa rồi, ta thấy rằng để $a$ là một thặng dư bậc $6$ theo mod $2016$ thì $a\equiv 1\pmod{8}$ và $a-1$ là bội của cả $9$ và $7$. Cho nên có thể thấy rằng, tất cả các thặng dư bậc $6$ theo mod $2016$ là\[a=504k+1,\quad k\in\mathbb Z.\]
Bằng những kỹ năng tương tự, ta xét một ví dụ khó khăn hơn.

Ví dụ 3. Tìm tất cả các thặng dư bậc $8$ theo mod $2016$.

Bây giờ ta lại có $\min\left\{5,\,2+v_2(8)\right\}=5$, nên để $a$ là một thặng dư bậc $8$ theo mod $2016$ thì ta cần phải có $a\equiv 1\pmod{32}$ và để ý \[\frac{{\varphi \left( {{3^2}} \right)}}{{\gcd \left( {8,{\mkern 1mu} \varphi \left( {{3^2}} \right)} \right)}} =\frac{{\varphi \left( 7 \right)}}{{\gcd \left( {8,{\mkern 1mu} \varphi \left( 7 \right)} \right)}} = 3.\]Ta cũng thấy rằng để $a^3\equiv 1\pmod 9$ thì $a\equiv 1\pmod 3$ còn để $a^3\equiv 1\pmod 7$ thì $a\equiv r\pmod 7$ với $r\in\{1,\,2,\,4\}$. Xét hệ đồng dư sau\[\left\{ \begin{array}{l}
x \equiv {1}\pmod{32},\\
x \equiv 1\pmod 3,\\
x \equiv {r}\pmod 7.
\end{array} \right.\]
Từ hai đồng dư đầu chúng ta có $x=96t+1,\,t\in\mathbb Z$, để ý rằng $3$ là nghịch đảo của $96$ theo mod $7$ nên $t\equiv 3\left(r-1\right)\pmod 7$. Vậy, nghiệm của hệ đó có dạng\[x\equiv 288\left(r-1\right)+1\pmod{672}.\]Thay vào sau tính toán ta được $x\equiv r^*\pmod{672}$ với $$r^*\in\{1,\,193,\,289\}.$$Vậy, tập hợp các số là thặng dư bậc $8$ theo mod $2016$ là\[\mathcal F_8=\{672k+1,\,672k+193,\,672k+289 :\;k\in\mathbb Z\}.\]Từ tính toán trên ta thấy $1979$ không là một thặng dư bậc $8$ theo mod $2016$, nói khác đi\[2016\nmid\left(a^8-1979\right)\quad\forall\,a\in\mathbb Z.\]
Còn số nhỏ nhất lớn hơn $2018$ mà là thặng dư bậc $8$ theo mod $2016$ là $2209$.

Chúng ta tạm hài lòng với những câu trả lời rất xù xì và xấu xí ở các định lý 2.1 và 2.2 cho câu hỏi: “Khi nào $a$ là một thặng dư bậc $n$ theo mod $m$?” ở đây.