cho n là số nguyên dương lớn hơn 1. CMR $2^n-1$ không chia hết cho n
#2
Đã gửi 06-12-2012 - 17:07
Biểu diễn $n=\prod_{i=1}^n p_i^{\alpha_i}$, khi đó $\Phi(n)=\prod_{i=1}^n p_i^{\alpha_i-1}\cdot \prod_{i=1}^n (p_i-1)$, $\frac{n}{\Phi(n)}$ không là số nguyên.
Do đó $\Phi(n)\nmid n$, mâu thuẫn với <*>. Vậy ta có đpcm.
#3
Đã gửi 06-12-2012 - 21:45
Sai bét từ dòng đầu, chỉ có $ord_p(n)|n$ thôiGiả sử ngược lại, tức là $n|2^n-1$. Theo định lý Euler: $n|2^{\Phi(n)}-1$. Ta có $\Phi(n)<n$, do đó $\Phi(n)|n$ <*>
Biểu diễn $n=\prod_{i=1}^n p_i^{\alpha_i}$, khi đó $\Phi(n)=\prod_{i=1}^n p_i^{\alpha_i-1}\cdot \prod_{i=1}^n (p_i-1)$, $\frac{n}{\Phi(n)}$ không là số nguyên.
Do đó $\Phi(n)\nmid n$, mâu thuẫn với <*>. Vậy ta có đpcm.
Giải như sau:
Gọi $p$ là ước nguyên tố nhỏ nhất của $n$
Khi ấy $2^n-1 \vdots p$ gọi $h$ là số nhỏ nhất $2^h-1 \vdots p$ nên $n \vdots h$
Ngoài ra theo Fermat nhỏ $2^{p-1}-1 \vdots p$ nên $p-1 \vdots h$
Vì $gcd(h,n)=1$ vì nếu không thì $h \vdots r,n \vdots r$ nên $p-1 \vdots r$ nên $p>r$ mà $p$ là ước nguyên tố nhỏ nhất của $n$ giờ lại có $r$ nhỏ hơn cũng là ước của $n$ vô lí
Do đó $gcd(h,n)=1$ mà $n \vdots h$ nên $h=1$ suy ra $2-1 \vdots p$ vô lí
Vậy $2^n-1 \not \vdots n$
- milinh7a, perfectstrong, thukilop và 1 người khác yêu thích
#4
Đã gửi 07-12-2012 - 22:20
Ý tưởng ko khác gì mấy vs nguyenta98, chủ yếu là xét $v_2$ thôi.cho n là số nguyên dương lớn hơn 1. CMR $2^n-1$ không chia hết cho n
Giải:
Xét phân tích tiêu chuẩn của $n=\prod\limits_{i = 1}^h {{p_i}^{{k_i}}}$ với các số nguyên tố ${p_1} < {p_2} < ... < {p_h}$. Trong đó ${p_i} = 1 + {2^{{r_i}}}{m_i}$ ($m_i$ lẻ) $\Rightarrow n \equiv 1(\bmod {m})$
Đặt $n - 1 = {2^m}t$ $\Rightarrow {2^{{2^m}t}} \equiv - 1(\bmod {p_i})$
Mà $- 1 \equiv {2^{{2^m}t{m_i}}} \equiv {2^{({p_i} - 1)t}} \equiv 1(\bmod {p_i})$
Vậy $p_i = 2$ (Vô lí)
Q.E.D
Remark: Chắc nguyenta98 có biết bài này:
Tìm tất cả số tự nhiên $n$ sao cho: $n|{2^n} + 2$
- perfectstrong và nguyenta98 thích
$P_{G}(\sigma_{1},\sigma_{2},\cdots,\sigma_{n})=\frac{1}{|G|}\sum_{\tau\in G}ind(\tau)$
#5
Đã gửi 07-12-2012 - 23:15
Ánh nhầm không đấy cách của anh là bài $2^{n-1}+1 \vdots n$ mà ????Ý tưởng ko khác gì mấy vs nguyenta98, chủ yếu là xét $v_2$ thôi.
Giải:
Xét phân tích tiêu chuẩn của $n=\prod\limits_{i = 1}^h {{p_i}^{{k_i}}}$ với các số nguyên tố ${p_1} < {p_2} < ... < {p_h}$. Trong đó ${p_i} = 1 + {2^{{r_i}}}{m_i}$ ($m_i$ lẻ) $\Rightarrow n \equiv 1(\bmod {m})$
Đặt $n - 1 = {2^m}t$ $\Rightarrow {2^{{2^m}t}} \equiv - 1(\bmod {p_i})$
Mà $- 1 \equiv {2^{{2^m}t{m_i}}} \equiv {2^{({p_i} - 1)t}} \equiv 1(\bmod {p_i})$
Vậy $p_i = 2$ (Vô lí)
Q.E.D
Remark: Chắc nguyenta98 có biết bài này:
Tìm tất cả số tự nhiên $n$ sao cho: $n|{2^n} + 2$
#6
Đã gửi 11-12-2012 - 00:02
- Giả sử $2^{n}-1 \vdots n$ tức là $2^{n}\equiv 1 (mod n)$ (1)
Ta đi chứng minh điều ấy không xảy ra
Thật vậy: ta có: $2^{n}=n.k+m $ (*) ( với k,m nguyên dương)
--Xét n chẵn, vì $2^{n}$ chẵn nên khi chia nó cho n chẵn thì k cũng chẵn... Do đó để thỏa (*) thì m phải chẵn hay $m \neq 1$
-- Xét n lẻ, lí luận tượng tự trên...... Ta cũng được m chẵn
Từ 2 trường hợp, suy ra với mọi n thì $2^{n}\equiv m (mod n)$ với m nguyên dương và m chẵn....Do đó điều (1) không xảy ra => $2^{n}-1$ không chia hết cho n với mọi n nguyên dương, n lớn hơn 1
-VƯƠN ĐẾN ƯỚC MƠ-
#7
Đã gửi 11-12-2012 - 17:17
Đoạn chia $2^n$ cho $n$ được $k$ chẵn đã bị sai do $m$ là dư rất tiếcMình dùng kiến thức cấp 2 giải thử được không:
- Giả sử $2^{n}-1 \vdots n$ tức là $2^{n}\equiv 1 (mod n)$ (1)
Ta đi chứng minh điều ấy không xảy ra
Thật vậy: ta có: $2^{n}=n.k+m $ (*) ( với k,m nguyên dương)
--Xét n chẵn, vì $2^{n}$ chẵn nên khi chia nó cho n chẵn thì k cũng chẵn... Do đó để thỏa (*) thì m phải chẵn hay $m \neq 1$
-- Xét n lẻ, lí luận tượng tự trên...... Ta cũng được m chẵn
Từ 2 trường hợp, suy ra với mọi n thì $2^{n}\equiv m (mod n)$ với m nguyên dương và m chẵn....Do đó điều (1) không xảy ra => $2^{n}-1$ không chia hết cho n với mọi n nguyên dương, n lớn hơn 1
- thukilop yêu thích
#8
Đã gửi 12-12-2012 - 02:33
-VƯƠN ĐẾN ƯỚC MƠ-
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh