Đến nội dung

Hình ảnh

Chứng minh b+1 là lũy thừa của 2

- - - - -

  • Please log in to reply
Chủ đề này có 7 trả lời

#1
dinhnguyenhoangkim

dinhnguyenhoangkim

    Hạ sĩ

  • Thành viên
  • 56 Bài viết

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


#2
Chris yang

Chris yang

    Thượng sĩ

  • Thành viên
  • 223 Bài viết

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 :)



#3
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết

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”). 


#4
Belphegor Varia

Belphegor Varia

    Thượng sĩ

  • Thành viên
  • 227 Bài viết

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

$\Rightarrow 1+b+b^2+...+b^{p-1}\equiv p(\mod q)$
$\Rightarrow p=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ó :

$u|b+1|b^d+1(1)$
$u|b+1|b^{m_1}-1|b^{m_1.d}-1\Rightarrow u|b^d-1(2)$
Từ $(1),(2)$ suy ra $u=2$  $\Rightarrow Q.E.D$                   $\square$ 
 
Spoiler

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 

 


#5
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết

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”). 


#6
Belphegor Varia

Belphegor Varia

    Thượng sĩ

  • Thành viên
  • 227 Bài viết

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ỉ ?

 

Spoiler

Đặ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 

 


#7
nhungvienkimcuong

nhungvienkimcuong

    Thiếu úy

  • Hiệp sỹ
  • 669 Bài viết

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 ~O) 
Thật kì lạ anh không thể nhớ đến tên mình mà chỉ nhớ đến tên em :wub:
Chúa tạo ra vũ trụ của con người còn em tạo ra vũ trụ của anh :ukliam2:


#8
Zaraki

Zaraki

    PQT

  • Phó Quản lý Toán Cao cấp
  • 4273 Bài viết

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


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 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh