Cho các số nguyên dương $b, m, n$. Trong đó $b>1$ và $m>n$. Chứng minh rằng nếu $b^m-1$ và $b^n-1$ có cùng các ước nguyên tố thì $b+1$ là lũy thùa của $2$.
Bài viết đã được chỉnh sửa nội dung bởi Zaraki: 06-09-2015 - 04:27
Cho các số nguyên dương b, m, n. Trong đó b>1 và m>n. Chứng minh rằng nếu b^m-1 và b^n-1 có cùng các ước nguyên tố thì b+1 là lũy thùa của 2
Nếu mình nhớ không nhầm thì bài này có trong PEN A mục Contest Collections trên mathlinks, bạn thử vào đó tra xem
Lời giải. Hiển nhiên rằng $m \ge 2$. Vì $\gcd (b,1)=1$ nên theo định lý Zsigmondy, nếu $b \ne 2, m \ne 6$ và $b+1$ không là luỹ thừa của $2$ thì sẽ tồn tại ước nguyên tố $p$ của $b^m-1$ sao cho $p \nmid b^k-1$ với mọi $k<n$. Ta suy ra $p \nmid b^n-1$. Như vậy $b=2,m=6$ hoặc $b+1$ là luỹ thừa của $2$. Ta thấy rẳng nếu $b=2,m=6$ thì không tồn tại $n$ thoả mãn.
Như vậy $b+1$ là luỹ thừa của $2$.
Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.
Grothendieck, Récoltes et Semailles (“Crops and Seeds”).
Cho các số nguyên dương $b, m, n$. Trong đó $b>1$ và $m>n$. Chứng minh rằng nếu $b^m-1$ và $b^n-1$ có cùng các ước nguyên tố thì $b+1$ là lũy thùa của $2$.
$\bullet \texttt{Solution}$
Gọi $d=\texttt{ged}(m,n),m=m_1.d$. Ta có kết quả quen thuộc $\texttt{ged}(b^m-1,b^n-1)=\texttt{ged}(b^d-1)$ nên kết hợp với giả thiết suy ra được $b^{m_1.d}-1,b^d-1$ có cùng các ước nguyên tố.
Từ đây ta liên tưởng đến bổ đề sau :
Bổ đề : Nếu $b^k-1$ và $b-1$ có cùng các ước nguyên tố thì khi đó $k$ là lũy thừa của $2$
Chứng minh: Giả sử ngược lại, tồn tại $p$ là ước nguyên tố lẻ của $k$. Khi đó gọi $q$ là ước nguyên tố bất kì của $\frac{b^p-1}{b-1}=1+b+b^2+...+b^{p-1}$.
Từ giả thiết suy ra $q|b-1$ $\Rightarrow b\equiv 1(\mod q)$
Suy ra $1+b+b^2+...+b^{p-1}=p^h(h>1,h\in \mathbb{N})$ $\star$
Lại có $ b\equiv 1(\mod p)$ $\Rightarrow 1+b+...+b^{p-1}\equiv p(\mod p^2)$ (Mâu thuẫn với $\star$)
Vậy điều giả sử sai
Suy ra $k$ là lũy thừa của $2$ (bổ đề được chứng minh)
Từ bổ đề ta suy ra được $b+1$ là lũy thừa của $2$
Thật vậy : Gọi $i$ là ước nguyên tố bất kì của $b+1$. Vì $k$ là lũy thừa của $2$ suy ra $i|b+1|b^k-1$
$i|b^k-1\Rightarrow i|b-1$
Suy ra $i=2$. $\Rightarrow Q.E.D$
Trở lại bài toán : Từ bổ đề trên suy ra $m_1$ và $b^d+1$ là lũy thừa của $2$
Vì $b>1$ nên $b^d+1\vdots 4 \Rightarrow d$ lẻ
Gọi $u$ là ước nguyên tố bất kì của $b+1$. Ta có :
Bài viết đã được chỉnh sửa nội dung bởi Belphegor Varia: 06-09-2015 - 17:24
$ \textbf{NMQ}$
Wait a minute, You have enough time. Also tomorrow will come
Just take off her or give me a ride
Give me one day or one hour or just one minute for a short word
Lại có $ b\equiv 1(\mod p)$ $\Rightarrow 1+b+...+b^{p-1}\equiv p(\mod p^2)$ (Mâu thuẫn với $\star$)
Chỗ này sao từ $b \equiv 1 \pmod p$ có thể suy ra $1+b+b^2+ \cdots +b^{p-1} \equiv p \pmod{p^2}$ được nhỉ ?
Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.
Grothendieck, Récoltes et Semailles (“Crops and Seeds”).
Chỗ này sao từ $b \equiv 1 \pmod p$ có thể suy ra $1+b+b^2+ \cdots +b^{p-1} \equiv p \pmod{p^2}$ được nhỉ ?
Đặt $b=p.x+1$. Khi đó ta có : $1+b+b^2+...+b^{p-1}\equiv (1+1+...+1)$ ($p$ số hạng)$+px+2px+...+(p-1)px\equiv p(\mod p^2)$
$ \textbf{NMQ}$
Wait a minute, You have enough time. Also tomorrow will come
Just take off her or give me a ride
Give me one day or one hour or just one minute for a short word
Chỗ này sao từ $b \equiv 1 \pmod p$ có thể suy ra $1+b+b^2+ \cdots +b^{p-1} \equiv p \pmod{p^2}$ được nhỉ ?
$v_p(1+b+...+b^{p-1})=v_p(b^p-1)-v_p(b-1)=v_p(p)=1$
Đừng khóc vì chuyện đã kết thúc hãy cười vì chuyện đã xảy ra
Thật kì lạ anh không thể nhớ đến tên mình mà chỉ nhớ đến tên em
Chúa tạo ra vũ trụ của con người còn em tạo ra vũ trụ của anh
$v_p(1+b+...+b^{p-1})=v_p(b^p-1)-v_p(b-1)=v_p(p)=1$
Hay thật, tự dưng lại quên mất cái này.
Discovery is a child’s privilege. I mean the small child, the child who is not afraid to be wrong, to look silly, to not be serious, and to act differently from everyone else. He is also not afraid that the things he is interested in are in bad taste or turn out to be different from his expectations, from what they should be, or rather he is not afraid of what they actually are. He ignores the silent and flawless consensus that is part of the air we breathe – the consensus of all the people who are, or are reputed to be, reasonable.
Grothendieck, Récoltes et Semailles (“Crops and Seeds”).
0 thành viên, 1 khách, 0 thành viên ẩn danh