Chủ đề này có 3 trả lời

[Mr handsome ugly]

Cho $n$ là một số nguyên dương và phân tích thừa số nguyên tố của $n$ là $n=\prod_{i=1}^{f}p_{i}^{k_{i}}$ biết $k_{i}$ là nguyên dương với mọi i nguyên dương thoả $f\geq i\geq 1$ và f cũng nguyên dương. Đặt $d=[\varphi (p_{1}^{k_{1}}),\varphi (p_{2}^{k_{2}}),...,\varphi (p_{f}^{k_{f}})]$ và phân tích thừa số nguyên tố của $d$ là $\prod_{t=1}^{H}q_{t}^{m_{t}}$ biết $m_{t}$ là nguyên dương với mọi t nguyên dương thoả $H\geq t\geq 1$ và f cũng nguyên dương. Cho $a$ là một số nguyên dương thoả $a$ nguyên tố cùng nhau với $n$. Chứng minh rằng luôn tồn tại và duy nhất hai bộ số nguyên dương $(u_{1},..,u_{H})$ và $(L_{1},..,L_{H})$ sao cho $a\equiv \prod_{t=1}^{H}u_{t}^{L_{t}}$ trong đó $ord_{n}(u_{t})=q_{t}^{m_{t}}$ và $L_{t}\mid q_{t}^{m_{t}}$ với mọi t thoả $H\geq t\geq 1$ .

 

*Câu hỏi ngoài lề: Mọi người cho em hỏi theo như bài toán trên thì tập tất cả các phần tử u thoả $ord_{n}(a)=q_{t}^{m_{t}}$ với mọi t thoả t $H\geq t\geq 1$ có phải tập sinh của nhóm nhân các phần tử thuộc $\mathbb{Z}_{n}$ nguyên tố cùng nhau với n không ạ ?

Bài viết đã được chỉnh sửa nội dung bởi Mr handsome ugly: 13-11-2023 - 22:03

[nmlinh16]

Đề này không biết bạn lấy từ đâu? Có rất nhiều lỗi sai trong phát biểu. Bạn phải phát biểu lại đúng thì mới làm được.

 

Đầu tiên lấy $n = 8$ thì $d = 4 = 2^2$, và lấy $a$ là số lẻ tùy ý. Từ đây thấy không có số nguyên lẻ $u$ nào để $\ord_8(u) = 4$ cả (hãy xem cả 4 lớp đồng dư khả nghịch trong $\mathbb{Z}/8$, bình phương của chúng đều bằng $\bar{1}$). Nói chung cần lấy $n$ là số nguyên dương không chia hết cho $8$ để đảm bảo rằng các cnhosm $\mathbb{Z}/p_i^{k_i}$ là các nhóm cyclic.

 

Tiếp theo là $(u_1,\ldots,u_H)$ và $(L_1,\ldots,L_H)$ duy nhất theo nghĩa như nào? Mình đồ rằng ý bạn là các số $u_t$ duy nhất modulo $n$. Và với các phát biểu kia thì mình đang hiểu là $a$ cho trước, và hai bộ $(u_1,\ldots,u_H)$ và $(L_1,\ldots,L_H)$ là duy nhất, phụ thuộc vào $a$. Nhưng cái này cũng không đúng: Lấy $n = 5$ thì $d = 4 = 2^2$ và lấy $a=1$. Khi đó có có thể lấy $u = 2$ và $L = 4$, hoặc $u' = 3$ và $L'=4$ để có được $\ord_5(2) = \ord_5(3) = 4$ và $u^L \equiv (u')^{L'} \equiv 1 \pmod 5$.

[Lemonjuice]

Dạ em xin lỗi anh và mọi người vì sự cẩu thả của em trong việc gõ đề ạ, đề này em tự nghĩ ra. Bài toán trên đúng như anh nói nó không có tính duy nhất, nó cần được sủa thành là chứng minh tồn tại 2 bộ số nguyên dương $(u_{1},..,u_{H})$ và $(L_{1},..,L_{H})$, đồng thời n cũng cần được sửa lại thành số lẻ lớn hơn 1. Em xin đưa ra một bài yếu hơn mà em đã chứng minh được như sau ạ: Cho trước n là nguyên dương lẻ (n>1) và cũng cho trước a là nguyên dương thoả $ord_{n}(a)=d$ với d>1 (d cũng là nguyên dương). Ta có phân tích thừa số nguyên tố của d là $d=\prod_{i=1}^{f}q_{i}^{z_{i}}$ biết $z_{i}\geq 1$ với mọi i thoả $f\geq i\geq 1$. Với mỗi i nguyên dương thoả  $f\geq i\geq 1$ Ta đặt tập $A_{i}$ là tập tất cả các số tự nhiên $u_{i}$ nhỏ hơn n sao cho $ord_{n}(u_{i})=q_{i}^{z_{i}}$. Vậy với mỗi tập $A_{i}(f\geq i\geq 1)$ thì tồn tại duy nhất một phần tử $u_{i}$ để $a\equiv \prod_{i=1}^{f}u_{i}(mod n)$ .

 

Quay trở lại bài toán ban đầu của topic. Ta chỉ cần chứng minh nếu a là số nguyên dương thoả $ord_{n}(a)=q^{m}$ với q là một ước nguyên tố của d và m là số nguyên dương lớn hơn 1 thì tồn tại một ước số L của d sao cho $b^{L}=a(mod n)$ trong đó b là số nguyên dương thoả $ord_{n}(b)=q^{k}$ với k là số nguyên dương lớn nhất mà d chia hết cho $q^{k}$. Kết hợp vấn đề này với bài toán yếu hơn phía trên thì có thể chứng minh được bài toán ban đầu của topic với đề được sửa thành chỉ là chứng minh tồn tại chứ không phải chứng minh tồn tại và duy nhất.

 

Em thật lòng muốn viết bài chứng minh bài toán yếu hơn phía trên nhưng em đang trong mùa thi nên tuần sau có lẽ em mới đăng chứng minh lên được. Em cũng mong mọi người chỉ ra các lỗi sai của em để em có thể sửa sai và tiến bộ.

 

Em có một chút tò mò là liệu người ta đã đưa ra công thức cho tập sinh nhỏ nhất (tập sinh có ít phần tử nhất) của nhóm nhân các phần tử thuộc $\mathbb{Z}_{n}$ nguyên tố cùng nhau với n chưa ạ  ?

 

*2 nick này ( Lemonjuice và Mrhandsomeugly) thuộc cùng 1 chủ cả ạ   

Bài viết đã được chỉnh sửa nội dung bởi Lemonjuice: 14-11-2023 - 18:04

[nmlinh16]

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$.