Ở bài viết về điều kiện để là thặng dư bậc cao ở http://songha.maths.vn/dieu-kien-la-mot-thang-du-bac-cao/ , ta đã chỉ ra rằng nếu $m=m_1m_1$ với $m_1,\,m_2\in\mathbb Z^+$ trong đó $\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$ nếu và chỉ nếu $a$ vừa là thặng dư bậc $n$ theo mod $m_1$ và đồng thời là thặng dư bậc $n$ theo mod $m_2$.

Bây giờ với $a_1,\,a_2$ lần lượt là các thặng dư bậc $n$ theo các mod $m_1,\,m_2$ tương ứng. Lúc đó, lại theo định lý thặng dư Trung Hoa sẽ tồn tại duy nhất $a\in\mathcal U_m$ sao cho\[a\equiv a_i\pmod{m_i}\quad\forall\,i=\overline{1,\,2}.\]Do đó $a$ cũng là một thặng dư bậc $n$ theo mod $m_i$, vì thế ta có định lý sau đây.

Định lý 1. Với $m,\,n$ là các số nguyên dương cho trước, ký hiệu $\Re_n(m)$ là số các thặng dư bậc $n$ theo mod $m$ trong $\mathcal U_m$. Khi đó $\Re_n(m)$ là một hàm nhân tính số học, tức là\[{\Re _n}\left( {\alpha \beta } \right) = {\Re _n}\left( \alpha \right){\Re _n}\left( \beta \right)\quad\forall\,\alpha,\,\beta\in\mathbb Z^+:\;\gcd\left(\alpha,\,\beta\right)=1.\]

Từ định lý vừa nêu, bài toán tìm số thặng dư bậc $n$ theo mod $m$ trong $\mathcal U_m$ quy về bài toán tìm số các thặng dư bậc $n$ theo mod $p^k$ trong $\mathcal U_{p^k}$. Ở đây, $p\in\mathbb P:\,p\mid m$ và $k=v_p(m)$.

Trường hợp đầu tiên cần xét đến là với $p=2$, tức là ta sẽ tìm số các thặng dư bậc $n$ theo mod $2^k$ (với $k\in\mathbb Z^+$) trong $\mathcal U_{2^k}$. Ta xét các tình huống sau.

1. Nếu $n$ lẻ, khi đó theo định lý 2 ở http://songha.maths.vn/dieu-kien-la-mot-thang-du-bac-cao/ thì mọi phần tử của $\mathcal U_{2^k}$ đều là thặng dư bậc $n$ theo mod $2^k$ tức là\[\Re_{n}\left(2^k\right)=\left| \mathcal U_{2^k}\right|=2^{k-1}.\]
2. Nếu $n$ chẵn, khi đó theo định lý 2 ở http://songha.maths.vn/dieu-kien-la-mot-thang-du-bac-cao/ thì phần tử $a$ của $\mathcal U_{2^k}$ là thặng dư bậc $n$ theo mod $2^k$ khi và chỉ khi\[a \equiv 1\pmod{2^{\min \left\{ {k,\,2 + {v_2}\left( n \right)} \right\}}}.\]Vì thế, khi $n$ chẵn thì\[{\Re _n}\left( {{2^k}} \right) = {2^{k – \min \left\{ {k,\,2 + {v_2}\left( n \right)} \right\}}}.\]

Tóm kết lại, ta có khẳng định sau.

Định lý 2. Cho các số nguyên dương $n$ và $k$, khi đó số các thặng dư bậc $n$ theo mod $2^k$ ở trong $\mathcal U_{2^k}$ là\[{\Re _n}\left( {{2^k}} \right) = \begin{cases}
{2^{k – 1}},\quad\text{nếu}\;n\;\text{lẻ}.\\
{2^{k – \min \left\{ {k,\,2 + {v_2}\left( n \right)} \right\}}},\quad\text{nếu}\;n\;\text{chẵn}.
\end{cases}\]

Bây giờ vấn đề còn lại của chúng ta là đi tính $\Re_n\left(p^k\right)$, trong đó $p\in\mathbb P\setminus\{2\}$ còn $k\in\mathbb Z^+$. Theo định lý 3 ở phần trước (http://songha.maths.vn/dieu-kien-la-mot-thang-du-bac-cao/) thì $a$ là một thặng dư bậc $n$ theo mod $m=p^k$ nếu và chỉ nếu\[a^{\frac{\varphi\left(m\right)}{\gcd\left(n,\,\varphi(m)\right)}}\equiv 1\pmod{m}.\]Với $d=\gcd\left(n,\,\varphi(m)\right)$ và $M=\dfrac{\varphi\left(m\right)}{d}$ thì điều kiện đó tương đương với việc $a$ là một nghiệm của phương trình đồng dư\[x^M\equiv 1\pmod{m}.\]Gọi $\mathfrak g$ là một căn nguyên thủy của $m=p^k$, thì ứng với mỗi nghiệm $a$ của phương trình nêu trên, sẽ tồn tại duy nhất một chỉ số $i_a\in\left[\varphi(m)\right]$ sao cho\[a\equiv \mathfrak{g}^{i_a}\pmod m.\]Cho nên nếu $a$ là nghiệm, thì phải có\[i_aM\equiv 0\pmod{\varphi(m)}.\]Từ đó điều kiện cần và đủ cho $a$ là $d\mid i_a$, chú ý việc $i_a\in\left[\varphi(m)\right]$ để thấy \[i_a\in\left\{d,\,2d,\,\ldots,\,Md\right\}.\]Vì thế số các $i_a$ thỏa mãn chính là $M$, và ta có định lý sau.

Định lý 3. Với $p$ là một số nguyên tố lẻ và $k$ là một số nguyên dương, ta có\[{\Re _n}\left( {{p^k}} \right) = \frac{{\varphi \left( {{p^k}} \right)}}{{\gcd \left( {n,\,\varphi \left( {{p^k}} \right)} \right)}} = \frac{{{p^k}\left( {p – 1} \right)}}{{\gcd \left( {n,\,{p^k}\left( {p – 1} \right)} \right)}}.\]

Trên nền tảng là các định lý 2 và định lý 3, ta có thuật toán sau.

Thuật toán tính số thặng dư bậc $n$ theo mod $m$

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ý 2 để tìm số thặng dư bậc $n$ theo mod $2^k$. Tất nhiên, không cần qua bước này nếu $k=0$.

Bước 3.  Sử dụng định lý 3 để tìm số thặng dư bậc $n$ theo mod $p_i^{k_i}$.

Bước 4. Số các thặng dư bậc $n$ theo mod $m$ là\[{\Re _n}\left( m \right) = {\Re _n}\left( {{2^k}} \right){\Re _n}\left( {p_1^{{k_1}}} \right){\Re _n}\left( {p_2^{{k_2}}} \right) \ldots {\Re _n}\left( {p_t^{{k_t}}} \right).\]

Ta xét một số ví dụ như sau.

Ví dụ 1. Ta sẽ tìm số các thặng dư bậc $7$ mod $2016$.

Trước hết ta có phân tích $2016 = {2^5}{{.3}^2}{{.7}^1}$ đồng thời do $7$ là một số lẻ nên theo định lý 3.2 ta có $\Re_7\left(2^5\right)=2^4$. Còn lại, theo định lý 3.3 ta có\[\begin{array}{l}
{\Re _7}\left( {{3^2}} \right) = \dfrac{{\varphi \left( {{3^2}} \right)}}{{\gcd \left( {7,\varphi \left( {{3^2}} \right)} \right)}} = 6,\qquad
{\Re _7}\left( 7 \right) = \dfrac{{\varphi \left( 7 \right)}}{{\gcd \left( {7,\varphi \left( 7 \right)} \right)}} = 6.
\end{array}\]Từ đó theo định lý 3.1, thì số các thặng dư bậc $7$ theo mod $2016$ là\[{\Re _7}\left( {2016} \right) = {\Re _7}\left( {2^5} \right).{\Re _7}\left( {{3^2}} \right).{\Re _7}\left( 7 \right) = {2^4}.6.6 = 576.\]

Ở ví dụ vừa rồi, ta thấy kết quả chính là $576=\varphi(2016)$. Và tất nhiên đây không phải là kết quả tình cờ nếu ta để ý $\gcd\left(7,\,\varphi(2016)\right)=1$. Tổng quát lên, ta có khẳng định 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 đó số các thặng dư bậc $n$ theo mod $m$ trong $\mathcal U_m$ là $\Re_n(m)=\varphi(m)$.

Chứng minh. Do $\gcd\left(n,\,\varphi(m)\right)=1$ nên theo hệ quả ở http://songha.maths.vn/dieu-kien-la-mot-thang-du-bac-cao/ thì mọi phần tử của $\mathcal U_m$ đều là thặng dư bậc $n$ theo mod $m$, vì thế\[\Re_n(m)=\left|\mathcal U_m\right|=\varphi(m).\]

Ta xét đến một ví dụ cần tính toán hơn, như sau.

Ví dụ 2. Tìm số các thặng dư bậc $6$ mod $2016$.

Theo định lý 2 ta có \[{\Re _6}\left( {{2^5}} \right) = {2^{5 – \min \left\{ {5,\,2 + {v_2}\left( 6 \right)} \right\}}} = 4.\] Tiếp theo, theo định lý 3.3 ta có\[\begin{array}{*{20}{l}}
{{\Re _6}\left( {{3^2}} \right) = \dfrac{{\varphi \left( {{3^2}} \right)}}{{\gcd \left( {6,\,\varphi \left( {{3^2}} \right)} \right)}} = 1,\qquad {\Re _6}\left( 7 \right) = \dfrac{{\varphi \left( 7 \right)}}{{\gcd \left( {6,\,\varphi \left( 7 \right)} \right)}} = 1.}
\end{array}\]Kết hợp $2016 = {2^5}{{.3}^2}{{.7}^1}$ và định lý 1, thì số các thặng dư bậc $6$ theo mod $2016$ là\[{\Re _6}\left( {2016} \right) = {\Re _6}\left( {{2^5}} \right).{\Re _6}\left( {{3^2}} \right).{\Re _6}\left( 7 \right) = 4.1.1 = 4.\]
Nhắc lại là, ở ví dụ 2 ở http://songha.maths.vn/dieu-kien-la-mot-thang-du-bac-cao/ ta đã chứng tỏ rằng các thặng dư bậc $6$ theo mod $2016$ có dạng $a=504k+1$ với $k\in\mathbb Z$. Bây giờ kết hợp với $a\in\mathcal U_{2016}$, để có $k\in\{0,\,1,\,2,\,3\}$, điều đó cũng là một lời giải thích khác cho kết quả $\Re_6(2016)=4$.