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

[cool hunter]

Cho số nguyên k. Tìm tất cả các số tự nhiên n để 3ⁿ-1 chia hết cho 2^k

[perfectstrong]

Lời giải:
Gọi $d$ là số tự nhiên nhỏ nhất thỏa $3^d \equiv 1 \pmod {2^k}$.
Ta chứng minh $3^n \equiv 1 \pmod {2^k} \Leftrightarrow d|n$. (1)
Thật vậy, giả sử $n=qd+r$ với $q,r \in \mathbb{Z}^; 1 \leq r \leq d-1$
$3^n=3^{qd+r}=(3^d)^q.3^r \equiv 3^r \pmod {2^k}$
Mặt khác, do cách chọn $d$ ban đầu nên $3^r \not \equiv 1 \pmod {2^k} \Rightarrow 3^n \not \equiv 1 \pmod {2^k}$: trái gt.
Suy ra, điều giả sử là sai. Vậy ta có (1) đúng.
Từ đề suy ra $3^n \equiv 1 \pmod {2^k}$. Theo (1) nên $d|n$.
Vậy tất cả các số tự nhiên $n$ thỏa đề là $n=qd$ với $d$ xác định như trên và $q \in \mathbb{N}$
===================================
Chú ý: $d$ chính là cấp của $3$ modulo $2^k$.

Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 26-02-2012 - 22:16

[nguyenta98]

Lời giải khác
Định lý Euler: Gọi $Q(x)$ là số số nguyên tố cùng nhau với $x$ và $gcd(a,x)=1$
Như vậy $$a^{Q(x)} \equiv 1 \pmod{x}$$
Áp dụng ta có
Các số không nguyên tố cùng nhau với $2^k$ là $2,4,6,...,2^k$ (có $2^{k-1}$ số)
Như vậy $Q(2^k)=2^k-2^{k-1}=2^{k-1}$
Như vậy áp dụng định lý Euler ta có $3^{2^k} \equiv 1 \pmod{2^k}$
Áp dụng bổ đề $p|3^m-1$ và $p|3^n-1$ và $m$ bé nhất thỏa mãn suy ra $m|n$ (chứng minh như anh perfectstrong)
Như vậy $2^{k-1}|n$ do vậy $n=2^{k-1}.q$
Vậy $n$ có dạng $2^{k-1}.q$

Em chỉ tìm dạng nghiệm còn kiểu tìm cấp modulo đó thì em chưa được học, lời giải của anh hình như là phương pháp để tìm ra số $n$ đúng không?

Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 26-02-2012 - 22:51

[perfectstrong]

Như vậy $2^{k-1}|n$ do vậy $n=2^{k-1}.q$
Vậy $n$ có dạng $2^{k-1}.q$

Kết luận của em ở đây chưa đúng. Em chưa chứng minh được $2^{k-1}$ là cấp của $3$ modulo $2^k$. Đó chỉ mới là chứng minh tồn tại 1 số tự nhiên $t$ thỏa mãn $3^t \equiv 1 \pmod {2^k}$. Có thể chứng minh cái này bằng quy nạp.
Anh đưa thêm công thức tính phi hàm Euler.
Giả sử $n$ có dạng phân tích chính tắc là $n = \prod\limits_{i = 1}^m {p_i^{{\alpha _i}}}$. Khi đó
\[\varphi \left( n \right) = n\prod\limits_{i = 1}^m {\left( {1 - \frac{1}{{{p_i}}}} \right)} \]