Về câu chuyện tập sinh nhỏ nhất của nhóm $(\mathbb{Z}/n)^\times$, theo hiểu biết của mình thì chưa có công thức tổng quát để tính một cách hiệu quả tập sinh này, nhưng có một số bình luân có thể có ích.
Để theo dõi các thảo luận ở dưới thì cần có một chút kiến thức về lý thuyết nhóm, cụ thể là định lý về cấu trúc của nhóm abel hữu hạn.
1. Ta giả sử $n$ có phân tích ra thừa số nguyên tố là $n = 2^k \prod_{i=1}^{f} p_i^{k_i}$, trong đó $p_i$ là các số nguyên tố lẻ phân biệt, $k_i > 0$, và $k \ge 0$ (có một chút rắc rói với số nguyên tố 2 như mình đã nói ở post trước, nên ta sẽ tách riêng nó ra).
Theo định lý số dư Trung Hoa, ta có đẳng cấu nhóm $$(\mathbb{Z}/n)^\times \xrightarrow{\cong} (\mathbb{Z}/2^k)^\times \times \prod_{i=1}^{f} (\mathbb{Z}/p_i^{k_i})^\times, \quad a \mod m \mapsto (a \mod 2^k, a \mod p_1^{k_1},\ldots, a \mod p_f^{k_f}),$$
nên ta có thể đưa về nghiên cứu các nhóm $(\mathbb{Z}/n)^\times$ với $n$ là lũy thừa nguyên tố.
- Với $k = 0, 1$ thì $(\mathbb{Z}/2^k)^\times = \{1\}$.
- Với $k = 2$ thì $(\mathbb{Z}/4)^\times = \{1,3\} \cong \mathbb{Z}/2$, là nhóm cyclic với phần tử sinh là $3$.
- Với $k \ge 3$ thì không khó để chứng minh rằng $(\mathbb{Z}/2^k)^\times \cong (\mathbb{Z}/2) \times (\mathbb{Z}/2^{k-2})$ là nhóm bicyclic với hai phần tử sinh là $-1$ và $3$.
Tiếp theo, với $p$ là số nguyên tố lẻ $(\mathbb{Z}/p)^\times$ luôn là nhóm cyclic (đẳng cấu với $\mathbb{Z}/(p-1)$), tức là được sinh bởi $1$ phần tử. Nói theo ngôn ngữ phổ thông là luôn tồn tại căn nguyên thủy modulo $p$. Nhưng theo hiểu biết của mình thì không có công thức tổng quát để tìm một phần tử sinh của nhóm này.
Sau đó, ta có thể chứng minh rằng nếu $\varepsilon$ là một phần tử sinh của $(\mathbb{Z}/p^k)^\times$ thì ít nhất moojtr trong hai số $\varepsilon$ hoặc $\varepsilon + p$ sẽ là một phần tử sinh của $(\mathbb{Z}/p^{k+1})^\times$. Từ đó ta có thể dùng quy nạp để tính dần dần một phần tử sinh của $(\mathbb{Z}/p^k)^\times$ với $k \ge 1$ và $p$ nguyên tố lẻ. Nói riêng, $(\mathbb{Z}/p^k)^\times \cong \mathbb{Z}/p^{k-1}(p-1)$.
Khi tìm được các phần tử sinh $\varepsilon_i$ của $(\mathbb{Z}/p_i^{k_i})^\times$, ta tìm nghiệm nguyên $u_i$ của hệ phương trình đồng dư $$\begin{cases} u_i \equiv \varepsilon_i \pmod{p_i^{k_i}}\\ u_i \equiv 1 \pmod{2^k \prod_{\substack{j=1 \\ j \neq i}}^f p_j^{k_j}}.\end{cases}$$
Tóm lại, với phân tích của $n$ ra thừa số nguyên tố như trên,
- Với $k=0,1$ thì $(\mathbb{Z}/n)^\times \cong \prod_{i=1}^f \mathbb{Z}/p_i^{k_i-1}(p_i-1)$ với $f$ phần tử sinh là $u_1,\ldots,u_f$.
- Với $k=2$ thì $(\mathbb{Z}/n)^\times \cong (\mathbb{Z}/2) \times \prod_{i=1}^f \mathbb{Z}/p_i^{k_i-1}(p_i-1)$ với $f+1$ phần tử sinh là $u,u_1,\ldots,u_f$, trong đó $u$ là một nghiệm của hệ phương trình đồng dư $$\begin{cases} u \equiv 3 \pmod{2^k} \\ u \equiv 1 \pmod{\prod_{i=1}^{f} p_i^{k_i}}. \end{cases}$$
- Với $k\ge 3$ thì $(\mathbb{Z}/n)^\times \cong (\mathbb{Z}/2) \times (\mathbb{Z}/2^{k-2}) \times \prod_{i=1}^f \mathbb{Z}/p_i^{k_i-1}(p_i-1)$ với $f+2$ phần tử sinh là $u,u',u_1,\ldots,u_f$, trong đó $u$ như trên và $u'$ là một nghiệm của hệ phương trình đồng dư $$\begin{cases} u \equiv -1 \pmod{2^k} \\ u \equiv 1 \pmod{\prod_{i=1}^{f} p_i^{k_i}}. \end{cases}$$
2. Ta sẽ chỉ ra tập sinh như trên là tập sinh (có số phần tử) nhỏ nhất. Để làm điều này ta cần khái niệm nhân tử bất biến cho nhóm abel hữu hạn. Định lý cơ bản về lý thuyết nhóm abel hữu hạn nói rằng mỗi nhóm abel hữu hạn $A$ đều có thể phân tích thành $A \cong (\mathbb{Z}/d_1) \times \cdots \times (\mathbb{Z}/d_\ell)$, trong đó các số nguyên dương $d_1,\ldots,d_\ell$ được xác định một các duy nhất sao cho $d_1 > 1$ và $d_1 | d_2 | \cdots | d_\ell$. Các số nguyên dương $d_i$ được gọi là các nhân tử bất biến của $A$, và $\ell$ được gọi là độ dài bất biến của $A$.
Ví dụ, $(\mathbb{Z}/2) \times (\mathbb{Z}/3) \cong \mathbb{Z}/6$ có độ dài bất biến bằng $1$ và nhân tử bất biến duy nhất là $6$, trong khi $(\mathbb{Z}/4) \times (\mathbb{Z}/10) \cong (\mathbb{Z}/2) \times (\mathbb{Z}/4) \times (\mathbb{Z}/5) \cong (\mathbb{Z}/2) \times (\mathbb{Z}/20)$ có độ dài bất biến bằng $2$ và hai nhân tử bất biến là $2$ và $20$.
Ta chỉ ra được rằng độ dài bất biến của $A$ chính là số phần tử của bất kỳ tập sinh nhỏ nhất nào, xem https://math.stackex...nite-abelian-gr.
Khi ta có một phân tích $A \cong \prod_{i=1}^r \mathbb{Z}/m_i$ thì $A$ được sinh bởi $r$ phần tử, nhưng $r$ không nhất thiết là độ dài bất biến (tức là số phần tử sinh nhỏ nhất), mà ta chỉ biết rằng độ dài bất biến không vượt quá $r$.
Tuy nhiên, nếu có thểm giả thiết rằng $\gcd(m_1,\ldots,m_r) > 1$ thì ta chứng minh được rằng $r$ chính là độ dài bất biến: xem chứng minh của Lemma 5.1, trang 10 trong https://personal.mat...loads/SIFMG.pdf
Áp dụng cho nhóm $A = (\mathbb{Z}/n)^\times$ như trên (ta thấy các nhóm cyclic xuất hiện đều có số phần tử chẵn), ta thấy độ dài bất biến của nhóm $(\mathbb{Z}/n)^\times$ chính là $f$ nếu $k=0,1$, là $f+1$ nếu $k=2$, và là $f+2$ nếu $k \ge 3$.
Kết luận: Nếu số ước nguyên tố phân biệt của $n$ là $f'$ thì số phần tử sinh nhỏ nhất của nhóm nhân khác số nguyên khả nghịch modulo $n$ là
- $f'$ nếu $n$ lẻ hoặc $n \equiv 4 \pmod 8$,
- $f'-1$ nếu $n \equiv 2 \pmod 4$,
- $f'+1$ nếu $n$ chia hết cho $8$.