พิสูจน์ จำนวนเฉพาะ

[pont494]

ผมลองทำดูแล้ว บางข้อพอได้นิดหน่อย บางข้อไม่ได้เลย อยากได้วิธีทำครับ หรือวิธีคิดก็ได้ครับ

1.จงตรวจสอบว่า $2^{19}-1$ เป็นจำนวนเฉพาะหรือจำนวนประกอบ

2.จงแสดงว่า จำนวนเฉพาะที่เขียนในรูป $8n+5$ มีจำนวนอนันต์

3.จงแสดงว่า $2^{13}-1$ เป็นจำนวนเฉพาะ และ $2^{23}-1$ ไม่ใช่จำนวนเฉพาะ

4.ให้ $p\nmid n$ สำหรับจำนวนเฉพาะ $p$ ทั้งหมดซึ่ง $p\leqslant \sqrt[3]{n} $
จงแสดงว่า จำนวนเต็มบวก $n>1$ จะเป็นจำนวนจำนวนเฉพาะ หรือเขียนอยู่ในรูปผลคูณของจำนวนเฉพาะ 2 จำนวน

5.จงแสดงว่า ถ้า $p$ เป็นจำนวนเฉพาะและ $a$ เป็นจำนวนเต็มบวก แล้ว $p\mid (a^p-a)$

6.จงตรวจสอบว่า $4^{545}+545^4$ เป็นจำนวนเฉพาะหรือจำนวนประกอบ

[nooonuii]

1. เป็นจำนวนเฉพาะครับ แต่วิธีที่ผมใช้ต้องพึ่งการคำนวณและเครื่องมือหนักหลายอย่าง รอผู้รู้มาเฉลยแบบง่ายๆครับ

[tonklaZolo]

ข้อ 5

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

Fermat's little theorem
$$p\mid a^p-a$$
p is prime and a is any integers.

[Amankris]

ข้อ 1 ต้องเช็คตัวประกอบเฉพาะหกจำนวนนี้ครับ

Click

191, 229, 419, 457, 571, 647

[artty60]

ข้อ6.$545^4+4^545\,เป็นจำนวนประกอบเพราะสามารถแยกตัวประกอบได้$

$545^4+4^545=(545^2+2\cdot4^{272})^2-(2\cdot 545\cdot4^{136})^2$

$=(545^2+2\cdot 4^{272}-2\cdot 545\cdot 4^{136})(545^2+2\cdot4^{272}+2\cdot 545\cdot 4^{136})$

ดังนั้น$\,545^4+4^{545}\,$เป็นจำนวนประกอบ

[pont494]

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

3.จงแสดงว่า $2^{13}-1$ เป็นจำนวนเฉพาะ และ $2^{23}-1$ ไม่ใช่จำนวนเฉพาะ

ในหนังสือเขียนทฤษฎีบทไว้แล้วครับ พอดีพึ่งอ่านถึงครับ
$(M_p=2^p-1)$

ถ้า $p$ เป็นจำนวนเฉพาะคี่ แล้วตัวหารของ $M_p$ จะต้องเขียนอยู่ในรูป $2kp+1$

เนื่องจาก $M_{13}=2^{13}-1=8191$ และ $\sqrt{8191}\leqslant 91 $
ดังนั้น ตัวหารเขียนอยู่ในรูป $2kp+1=2k(13)+1=26k+1$
ซึ่งมีค่าน้อยกว่า 91 คือ 53 และ 79 ซึ่งพบว่า $53\nmid 8191$ และ $79\nmid 8191$
ดังนั้น $M_{13}$ เป็นจำนวนเฉพาะ

[Aquila]

ข้อ 2 ทำให้เป็นกรณีทั่วไปได้ มันคือ Dirichlet's Theorem ส่วนกรณีเฉพาะ (a,b)=(8,5) ยังไม่อยากคิดครับ

ข้อ 4 ให้มี prime k ตัว ($k>1$) say $p_{i}$ ที่ $n=p_{1}...p_{k}$ เรียงจากน้อยไปมาก
จากเงื่อนไขโจทย์ $n=p_{1}...p_{k}> (\sqrt[3]{n})^k$ ต้องได้ $k=2$ ก็จบแล้ว

ข้อ 5 ใช้คอมบินาทอริกให้เหตุผลได้

ข้อ 3 ความเห็นบนอย่าลืมแสดงด้วยว่า $(545^2+2\cdot 4^{272}-2\cdot 545\cdot 4^{136}) > 1$ นะครับ

[Pitchayut]

มาเพิ่มวิธีทำให้

เราจะพิสูจน์ว่า ถ้า $p$ และ $2p+1$ เป็นจำนวนเฉพาะและ $p\equiv 3 \pmod 4$ จะได้ว่า $2p+1\mid 2^p-1$

โดยใช้ Fermat's Little Theorem จะได้ว่า $2^{2p}\equiv 1 \pmod {2p+1}$

นั่นคือ $2p+1\mid 2^{2p}-1 \Rightarrow 2p+1\mid (2^p-1)(2^p+1)$

ทำให้ $2p+1\mid 2^p-1$ หรือ $2p+1 \mid 2^p+1$ เราจะแสดงว่าทางที่สองไม่เป็นจริง โดยการสมมุติให้

$2p+1\mid 2^p+1 \Rightarrow 2^p \equiv -1 \pmod{2p+1}\Rightarrow \left(2^{\frac{p+1}{2}}\right)^2\equiv -2 \pmod{2p+1}$

เนื่องจาก $-2$ จะเป็น quadratic residue modulo $p$ ก็ต่อเมื่อ $p\equiv 1, 3 \pmod 8$

แต่ว่า $2p+1\equiv 7 \pmod 8$ จึงเกิดข้อขัดแย้งขึ้น นั่นคือ $2p+1\mid 2^p-1$

และเมื่อแทน $p=23$ ก็จะได้ว่า $47\mid 2^23-1$ นั่นคือ $2^23-1$ เป็นจำนวนประกอบ