Chứng minh $gcd(2^p-1;2^q-1)=1$ khi $gcd(p;q)=1$ và ngược lại
Chứng minh $gcd(2^p-1;2^q-1)=1$
Bắt đầu bởi thedragonknight, 02-09-2012 - 16:11
#1
Đã gửi 02-09-2012 - 16:11
- kaxevipwar yêu thích
#2
Đã gửi 02-09-2012 - 16:37
Giải như sau:Chứng minh $gcd(2^p-1;2^q-1)=1$ khi $gcd(p;q)=1$ và ngược lại
Bổ đề quen thuộc: $2^x-1 \vdots p$ và $2^y-1 \vdots p$ với $x$ nhỏ nhất thì $y \vdots x$
$\boxed{\text{chiều thuận}}$ $gcd(p,q)=1 \Rightarrow gcd(2^p-1,2^q-1)=1$
Ta giả sử ngược lại $gcd(2^p-1,2^q-1) \vdots r$ với $r$ nguyên tố
Khi đó tồn tại số $k$ nhỏ nhất sao cho $2^k-1 \vdots r$
Áp dụng bổ đề suy ra $2^p-1 \vdots r \Rightarrow p \vdots k$ và tương tự suy ra $q \vdots k$ mà $gcd(p,q)=1$ suy ra $k=1$ do đó $2^1-1 \vdots r$ vô lý
Nên chiều thuận được chứng minh
$\boxed{\text{chiều đảo}}$ $gcd(2^p-1,2^q-1)=1 \Rightarrow gcd(p,q)=1$
Giả sử ngược lại suy ra $gcd(p,q) \vdots r$ với $r>1$ khi ấy $2^p-1 \vdots 2^r-1$ và $2^q-1 \vdots 2^r-1$ khi đó mâu thuẫn vì $gcd(2^p-1,2^q-1)=1$
Suy ra chiều đảo cũng được chứng minh
Vậy nên bài toán được giải hoàn toàn
Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 02-09-2012 - 16:38
- BlackSelena, ducthinh26032011, NLT và 2 người khác yêu thích
#3
Đã gửi 02-09-2012 - 18:27
Ta có bài toán quen thuộc : $a,m,n$ là các số tụ nhiên thì : $(a^m-1,a^n-1)=a^{(m,m)}-1$Chứng minh $gcd(2^p-1;2^q-1)=1$ khi $gcd(p;q)=1$ và ngược lại
Áp dụng có ngay Đ.P.C.M
#4
Đã gửi 02-09-2012 - 18:31
Giải như sau:Ta có bài toán quen thuộc : $a,m,n$ là các số tụ nhiên thì : $(a^m-1,a^n-1)=a^{(m,m)}-1$
Áp dụng có ngay Đ.P.C.M
Giả sử $gcd(m,n)=d \rightarrow m=dx,n=dy, gcd(x,y)=1$
Suy ra $gcd(a^m-2,a^n-1)=gcd((a^d)^x-1,(a^d)^y-1)$
- Giả sử $gcd((a^d)^x-1,(a^d)^y-1)=p$ suy ra $gcd(a,p)=1 \rightarrow gcd(a^d,p)=1$
Theo định lý cấp của một số và $gcd((a^d)^x-1,(a^d)^y-1) \vdots p \rightarrow (a^d)^x-1; (a^d)^y-1 \vdots p$ ta suy ra $x,y \vdots k$ (do $k$ là cấp của $(a^d)$ mod $p$)
Mặt khác $gcd(x,y)=1 \rightarrow k=1$ nên cấp của $(a^d)$ mod $p$ là $1$ do đó suy ra $a^d-1 \vdots p$
Như vậy ta đã chứng minh xong $a^d-1 \vdots p<1>$
- Ta cần chứng minh $p \vdots a^d-1$ thật vậy do $gcd(a^m-1,a^n-1)=p \rightarrow gcd((a^d)^x-1,(a^d)^y-1)=p$
Như vậy ta chứng minh xong $p \vdots a^d-1<2>$
Từ $<1><2> \rightarrow p=a^d-1$ do đó $gcd(a^m-1,a^n-1)=a^d-1=a^{m,n}-1 \rightarrow Q.E.D$
- ducthinh26032011 yêu thích
#5
Đã gửi 02-09-2012 - 18:43
Chú Vương chơi k đẹp nhá!Chứng minh $gcd(2^p-1;2^q-1)=1$ khi $gcd(p;q)=1$ và ngược lại
Lời giải:
Giả sử $(p,q)=d$ (với $d\in N$ )
$\Rightarrow p=dx;q=dy$
$\Rightarrow 2^{p}-1=2^{dx}-1\vdots 2^{d}-1$
$2^{q}-1=2^{dy}-1\vdots 2^{d}-1$
$\Rightarrow (2^{p}-1,2^{q}-1)\vdots 2^{d}-1\Leftrightarrow 1\vdots 2^{d}-1\Leftrightarrow 2^{d}-1=1\Leftrightarrow d=1$
$\Rightarrow Q.E.D$
Bài viết đã được chỉnh sửa nội dung bởi ducthinh26032011: 02-09-2012 - 18:44
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh