โจทย์ สอวน ค่าย 2 ศูนย์ กทม ข้อแรก

[LightLucifer]

จงพิสูจน์ว่า สำหรับทุก $n\in \mathbb{N} $
$$ gcd (n,2^{2^{n}}+1)=1$$

[tatari/nightmare]

ข้อความเดิมเขียนโดยคุณ LightLucifer

จงพิสูจน์ว่า สำหรับทุก $n\in \mathbb{N} $
$$ gcd (n,2^{2^{n}}+1)=1$$

สมมติในเชิงขัดแย้งว่า $gcd (n,2^{2^{n}}+1)>1$ ดังนั้นจะมีจำนวนเฉพาะ $p$ ซึ่ง $p$ หาร หรม ของมันลงตัว
เราได้ $p\mid n$ และ $2^{2^{n}}\equiv -1(mod p)\rightarrow 2^{2^{n+1}}\equiv 1(mod p)$
แต่จากที่ $p$ เป็นจำนวนเฉพาะและชัดเจนว่า $p$ ไม่ใช่ 2(เพราะว่ามันหาร $2^{2^{n}}+1$)
ดังนั้นโดยแฟร์มาต เราได้ $2^{p-1}\equiv 1(mod p)$
$\therefore 2^{(p-1,2^{n+1})}\equiv 1(mod p)$
พิจารณาว่า $(p-1,2^{n+1})$ สังเกตว่ามันจะต้องอยู่ในรูป $2^k$ เมื่อ $0\leq k\leq n+1$
ถ้า $0\leq k\leq n$ เราจะได้ $2^{2^k}\equiv 1(mod p)\rightarrow (2^{2^k})^{2^{n-k}}\equiv 1(mod p)\rightarrow 2^{2^{n}}\equiv 1(mod p) $ เกิดข้อขัดแย้ง
ดังนั้น $(p-1,2^{n+1})=2^{n+1}$ เท่านั้น นั่นคือ $2^{n+1}\mid p-1$ หรือได้ว่า $p\geq 2^{n+1}+1$ แต่จากที่ $p\mid n$ จึงได้ $n\geq p$ ทำให้ได้ว่า $n\geq 2^{n+1}+1$ ซึ่งเป็นการง่ายที่จะแสดงว่าเป็นไปไม่ได้สำหรับจำนวนนับ $n$

[LightLucifer]

วิธีของผมนะ ไม่ค่อยมั่นใจ

สมมติว่า $(n,2^{2^n}+1)\not= 1$ สมมติให้เท่ากับ $d$ จะได้ว่า
$2^{2^n}+1\equiv n \pmod{d}$
พิจรณา $(2^{2^n}+1,2^{2^n})=1$ จะได้ว่า $(2^{2^n},d)=1$ เช่นกัน
โดย ทบ ของออยเลอร์จะได้ว่า
$(2^{2^n})^{\phi (d)}\equiv 1 \pmod{d}$
$(2^{2^n})^{\phi (d)+1}+1\equiv 2^{2^n}+1\equiv n \pmod{d}$
จะได้ว่า
$(2^{2^n})^{\phi (d)+1}+1\equiv n \pmod{d}$
$(2^{2^n})^{\phi (d)+1}-1\equiv n-2 \pmod{d}$
$((2^{2^n})^{\phi (d)}-1)((2^{2^n})^{\phi (d)-1}+(2^{2^n})^{\phi (d)-2}+...+(2^{2^n})+1)\equiv n-2 \pmod{d}$
แต่ $((2^{2^n})^{\phi (d)}-1)\equiv 0 \pmod{d}$
จะได้ว่า
$n-2 \equiv 0 \pmod{d}$
นั่นคือ $d \mid n-2$ แต่จาก $d=(n,2^{2^n}+1)$ จะได้ว่า $d\mid n$
จะได้ว่า $d\mid [(n)-(n-2)]\rightarrow d\mid 2$
จะได้ว่า $d=1,2$ แต่ $2^{2^n}+1$ เป็นจำนวนคี่ จะได้ว่า $d=(n,2^{2^n}+1)\not= 2$
ดังนั้น $d=1$ Contradiction!

[tatari/nightmare]

ข้อความเดิมเขียนโดยคุณ LightLucifer

วิธีของผมนะ ไม่ค่อยมั่นใจ

สมมติว่า $(n,2^{2^n}+1)\not= 1$ สมมติให้เท่ากับ $d$ จะได้ว่า
$2^{2^n}+1\equiv n \pmod{d}$
พิจรณา $(2^{2^n}+1,2^{2^n})=1$ จะได้ว่า $(2^{2^n},d)=1$ เช่นกัน
โดย ทบ ของออยเลอร์จะได้ว่า
$(2^{2^n})^{\phi (d)}\equiv 1 \pmod{d}$
$(2^{2^n})^{\phi (d)+1}+1\equiv 2^{2^n}+1\equiv n \pmod{d}$
จะได้ว่า
$(2^{2^n})^{\phi (d)+1}+1\equiv n \pmod{d}$
$(2^{2^n})^{\phi (d)+1}-1\equiv n-2 \pmod{d}$
$((2^{2^n})^{\phi (d)}-1)((2^{2^n})^{\phi (d)-1}+(2^{2^n})^{\phi (d)-2}+...+(2^{2^n})+1)$$\equiv n-2 \pmod{d}$
แต่ $((2^{2^n})^{\phi (d)}-1)\equiv 0 \pmod{d}$
จะได้ว่า
$n-2 \equiv 0 \pmod{d}$
นั่นคือ $d \mid n-2$ แต่จาก $d=(n,2^{2^n}+1)$ จะได้ว่า $d\mid n$
จะได้ว่า $d\mid [(n)-(n-2)]\rightarrow d\mid 2$
จะได้ว่า $d=1,2$ แต่ $2^{2^n}+1$ เป็นจำนวนคี่ จะได้ว่า $d=(n,2^{2^n}+1)\not= 2$
ดังนั้น $d=1$ Contradiction!

ผมรู้สึกแปลกๆกับตรงสีแดงอะครับ.....

[LightLucifer]

จิงด้วย จ๊ากกกกกกกกก 10 คะแนนนนนน บ๊ายบายยยย T_T