Mersenne Number

[BallSuke]

จงพิสูจน์ว่า (2^x)-1 = p^t มีคำตอบก็ต่อเมื่อ t= 1 เท่านั้น

เมื่อ x , t เป็นจำนวนนับ และ p เป็นจำนวนเฉพาะ

ช่วยหน่อยครับ ขอบคุณครับ

[BallSuke]

p มากกว่าเท่ากับ 3 ด้วยนะครับ

[Thgx0312555]

ให้ x เป็นจำนวนนับซึ่ง $(2^x)-1 = p^t$
แยกเคส x เป็นจำนวนเฉพาะกับจำนวนประกอบดูครับ

เคส x เป็นจำนวนเฉพาะเห็นได้ชัดว่าจริง

ถ้า x เป็นจำนวนประกอบ ให้ r,s เป็นจำนวนเฉพาะ ซึ่ง $rs \ | \ x$

$2^{rs}-1=(2^r-1)(2^{r(s-1)}+2^{r(s-2)}+\cdots +2^r+1)=p^k$ for some natural k

$gcd(2^r-1,2^{r(s-1)}+2^{r(s-2)}+\cdots +2^r+1) \ | \ s$

if $gcd(2^r-1,2^{r(s-1)}+2^{r(s-2)}+\cdots +2^r+1)=1$ ขัดแย้ง

if $gcd(2^r-1,2^{r(s-1)}+2^{r(s-2)}+\cdots +2^r+1)=s$
จะได้ $p=s$

ในทำนองเดียวกัน $p=r$
$r=s$

ดังนั้น $r \ | \ (2^r-1)$ ซึ่งขัดแย้งโดย FLT

ดังนั้น $t=1$ เสมอ (ขากลับไม่เป็นจริงครับ)

[BallSuke]

บรรทัดที่ 6

ทำไม หรม ของสองตัวนั้นถึงหาร s ลงตัวเหรอครับ

[Thgx0312555]

โดย Euclidean Algorithm ครับ หรือจะใช้หลักของ หรม ตามนี้ก็ได้
$\gcd(x-1,x^{n-1}+x^{n-2}+\cdots+1) = \gcd(x-1,(x^{n-1}-1)+(x^{n-2}-1)+\cdots + (x-1)+s)$
ซึ่ง $(x-1) \ | \ (x^r-1)$ เสมอ
$\gcd(x-1,x^{n-1}+x^{n-2}+\cdots+1) = \gcd(x-1,s) \ | \ s$

[BallSuke]

ขอรบกวนอีกรอบนะครับ ที่หรมเป็น 1 กับ s นี่มันขัดแย้งยังไงเหรอครับ แล้วทำไม p=s เหรอครับ ขอบคุณครับ

[Thgx0312555]

ขอแก้ solution ใหม่นะครับ เหมือนว่าอันเก่าจะผิดนิดนึง

สมมติให้ $2^x-1=p^t$

ถ้า $2 \ | \ t$

ถ้า $x=1, p^t = 1$ ซึ่งขัดแย้ง
ถ้า $x \ge 2$ จะได้ $2^x-1 \equiv 3 \pmod 4$ แต่จาก $2 \nmid p, p^2 \equiv 1 \pmod 4, p^t \equiv 1 \pmod 4$ ซึ่งขัดแย้ง

ถ้า $2 \nmid t$

$2^x = p^t+1 = (p+1)(p^{t-1}-p^{t-2}+\cdots-p+1)$

ให้ $p+1 = 2^y, p^{t-1}-p^{t-2}+\cdots-p+1 = 2^{x-y}, 0 \le y \le x$

$\gcd(2^y, 2^{x-y}) = \gcd (p+1,p^{t-1}-p^{t-2}+\cdots-p+1)$
$ = \gcd(p+1,(p^{t-1}+p^{t-2})-(2p^{t-2}+2p^{t-3})+\cdots-((t-1)p+(t-1))+t)$
$ = \gcd(p+1,(p+1)(p^{t-2}-2p^{t-3}+\cdots-(t-1))+t)$
$ = \gcd(p+1,t)$

ซึ่งจาก $2 \nmid t$ $\gcd(p+1,t) = \gcd(2^y, 2^{x-y})$ เป็นจำนวนคี่

นั่นคือ $y=0$ หรือ $y=x$
ถ้า $y=0$, $p+1=2^0, p=0$ ซึ่งขัดแย้ง
ถ้า $y=x$, $p^{t-1}-p^{t-2}+\cdots-p+1 = 2^0$

ซึ่งถ้า $t=1$ ฝั่งซ้ายจะเหลือพจน์เดียว คือ $1$
ถ้า $t>1$ $p^{t-1}-p^{t-2}+\cdots-p=0$
$p$ หารตลอด ; $p^{t-2}-p^{t-3}+\cdots+p-1=0$

$p(p^{t-3}-p^{t-4}+\cdots+1)=1$
$p \ | \ 1$ ซึ่งขัดแย้ง

ดังนั้น $t=1$

[BallSuke]

ทำไม p+1=2^y ได้เหรอครับ? เช่น p=5 จะได้ 6 แต่เขียนอยู่ในรูป 2^y ไม่ได้