Anh đính chính lại là lập thành hệ thặng dư thu gọn thôi nhá, tức là lấp đầy từ 1 đến $p-1$, còn đồng dư 0 thì chọn đơn giản rồi.Anh Karl Heinrich Marx chứng minh lại cho em chỗ phần HĐĐ được không ạ?
Bổ đề:
Cho $p$ là số nguyên tố lẻ. $k$ nguyên dương thỏa $(k;p)=(k-1;p)=1$.
Khi đó, $\{ 1^k;2^k;...;(p-1)^k \}$ là HĐĐ mod $p$.
Cái này sử dụng đến căn nguyên thủy. Gọi $g$ là căn nguyên thủy của $p$ tức là $ord_p(g)=p-1$ khi đấy thì $g^1,g^2,...,g^{p-1}$ lập thành 1 hệ thặng dư thu gọn của $p$ và rõ ràng $g^{a_1},g^{a_2},...,g^{a_{p-1}}$ là hệ thặng dư thu gọn của $p$ khi và chỉ khi $a_1,a_2,..,a_{p-1}$ là hệ thặng dư đầy đủ của $p-1$. Với $1 \le i \le p-1$ thì tồn tại $a_i$ để mà $i \equiv g^{a_i} (mod p)$ và rõ ràng $a_i$ lập thành 1 hệ thặng dư thu gọn nên hệ $ 1^k,2^k,..,(p-1)^k$ có thể viết lại là $g^k,g^{2k},...,g^{(p-1)k}$, nó là hệ thặng dư thu gọn khi và chỉ khi $k,2k,...,(p-1)k$ là hệ thặng dư đầy đủ của $p-1$, tức là $k$ nguyên tố cùng nhau với $p-1$ đây chính là đk cần và đủ luôn đấy.
