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

[thedragonknight]

Chứng minh $gcd(2^p-1;2^q-1)=1$ khi $gcd(p;q)=1$ và ngược lại

[nguyenta98]

Chứng minh $gcd(2^p-1;2^q-1)=1$ khi $gcd(p;q)=1$ và ngược lại

Giải như sau:
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

[Secrets In Inequalities VP]

Chứng minh $gcd(2^p-1;2^q-1)=1$ khi $gcd(p;q)=1$ và ngược lại

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

[nguyenta98]

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ải như sau:
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$

Do đó gọi $k$ là cấp của $a^d$ mod $p$ suy ra $(a^d)^k-1 \vdots p$ với $k$ nhỏ nhất
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$

Mặt khác $(a^d)^x-1 \vdots (a^d-1)$ và $(a^d)^y-1 \vdots (a^d-1) \rightarrow gcd((a^d)^x-1,(a^d)^y-1) \vdots (a^d-1) \rightarrow p \vdots (a^d-1)$
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]

Chứng minh $gcd(2^p-1;2^q-1)=1$ khi $gcd(p;q)=1$ và ngược lại

Chú Vương chơi k đẹp nhá!
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