จำนวนเฉพาะ — รายการ ความหมาย และวิธีหา

จำนวนเฉพาะคือจำนวนเต็มที่มากกว่า $1$ และมีตัวหารบวกอยู่พอดี 2 ตัว คือ $1$ และตัวมันเอง ดังนั้น $2, 3, 5,$ และ $7$ เป็นจำนวนเฉพาะ, $1$ ไม่เป็นจำนวนเฉพาะ, และจำนวนอย่าง $12$ เป็นจำนวนประกอบ

ถ้าจำนวนเต็มที่มากกว่า $1$ มีตัวหารบวกมากกว่า 2 ตัว จะเรียกว่าเป็นจำนวนประกอบ ตัวอย่างเช่น $12$ เป็นจำนวนประกอบ เพราะหารด้วย $1, 2, 3, 4, 6,$ และ $12$ ลงตัว

จำนวนเฉพาะไม่เกิน 50

ต่อไปนี้คือจำนวนเฉพาะที่ไม่เกิน $50$:

$$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47$$

ช่วงห่างระหว่างจำนวนเฉพาะไม่มีรูปแบบซ้ำที่ง่าย ๆ ตัวอย่างเช่น $11$ กับ $13$ อยู่ใกล้กัน แต่ช่วงถัดไปจาก $23$ ถึง $29$ ห่างกว่า

อะไรทำให้จำนวนหนึ่งเป็นจำนวนเฉพาะ?

จำนวนหนึ่งจะเป็นจำนวนเฉพาะได้ ต้องผ่านทั้ง 2 เงื่อนไขนี้:

1. ต้องมากกว่า $1$
2. ตัวหารบวกของมันต้องมีเพียง $1$ และตัวมันเอง

นี่จึงเป็นเหตุผลว่า $1$ ไม่เป็นจำนวนเฉพาะ และยังอธิบายด้วยว่าทำไม $2$ จึงเป็นจำนวนเฉพาะแม้จะเป็นจำนวนคู่ จำนวน $2$ มีตัวหารบวกอยู่พอดี 2 ตัว คือ $1$ และ $2$

วิธีตรวจว่าจำนวนหนึ่งเป็นจำนวนเฉพาะหรือไม่

สำหรับจำนวนเต็ม $n > 1$ คุณสามารถตรวจได้ว่ามันเป็นจำนวนเฉพาะหรือไม่ โดยเช็กว่ามีจำนวนเต็มใดตั้งแต่ $2$ ถึง $\lfloor \sqrt{n} \rfloor$ ที่หารมันลงตัวหรือไม่

เหตุผลนี้ใช้ได้จริงในทางปฏิบัติ: ถ้า $n = ab$ แล้วตัวประกอบตัวใดตัวหนึ่งจะต้องน้อยกว่าหรือเท่ากับ $\sqrt{n}$ ดังนั้นถ้ายังไม่พบตัวหารเมื่อเช็กถึง $\sqrt{n}$ ก็จะไม่มีคู่ตัวประกอบที่ใหญ่กว่านั้นซ่อนอยู่

ในการใช้งานทั่วไป คนมักตรวจด้วยกฎการหารลงตัวแบบง่าย ๆ ก่อน:

1. ถ้า $n$ เป็นจำนวนคู่และมากกว่า $2$ มันจะไม่เป็นจำนวนเฉพาะ
2. ถ้าผลบวกของเลขโดดเป็นพหุคูณของ $3$ แล้ว $n$ จะหารด้วย $3$ ลงตัว
3. ถ้า $n$ ลงท้ายด้วย $0$ หรือ $5$ และมากกว่า $5$ มันจะหารด้วย $5$ ลงตัว

ทางลัดเหล่านี้ยังไม่เพียงพอที่จะพิสูจน์ว่าจำนวนหนึ่งเป็นจำนวนเฉพาะได้ด้วยตัวเอง แต่ช่วยตัดจำนวนประกอบออกไปได้อย่างรวดเร็วหลายจำนวน

ตัวอย่างทำโจทย์: $29$ เป็นจำนวนเฉพาะหรือไม่?

ในการทดสอบ $29$ ก่อนอื่นสังเกตว่า

$$\sqrt{29} \approx 5.38$$

ดังนั้นจึงพอที่จะตรวจตัวหารที่เป็นจำนวนเต็มถึงแค่ $5$

• $29$ หารด้วย $2$ ไม่ลงตัว เพราะเป็นจำนวนคี่
• $29$ หารด้วย $3$ ไม่ลงตัว เพราะ $2 + 9 = 11$ และ $11$ ไม่ใช่พหุคูณของ $3$
• $29$ หารด้วย $5$ ไม่ลงตัว เพราะไม่ได้ลงท้ายด้วย $0$ หรือ $5$

การตรวจ $4$ ไม่ได้ช่วยอะไรเพิ่มเติมในที่นี้ เพราะพหุคูณของ $4$ ทุกจำนวนเป็นจำนวนคู่ และเรารู้แล้วว่า $29$ หารด้วย $2$ ไม่ลงตัว

ไม่มีตัวหารใดที่ไม่เกิน $5$ ใช้ได้ ดังนั้น $29$ เป็นจำนวนเฉพาะ

ข้อผิดพลาดที่พบบ่อยเกี่ยวกับจำนวนเฉพาะ

บอกว่า $1$ เป็นจำนวนเฉพาะ

ไม่ใช่ ตามนิยามต้องมีตัวหารบวกอยู่พอดี 2 ตัว แต่ $1$ มีเพียงตัวเดียว

คิดว่าจำนวนคี่ทุกจำนวนเป็นจำนวนเฉพาะ

จำนวนคี่หลายจำนวนเป็นจำนวนประกอบ ตัวอย่างเช่น $21$ เป็นจำนวนคี่ แต่

$$21 = 3 \times 7$$

ดังนั้นมันจึงไม่เป็นจำนวนเฉพาะ

ตรวจไกลเกินไป

ถ้าคุณต้องการเพียงตรวจว่าเป็นจำนวนเฉพาะหรือไม่ ก็ไม่จำเป็นต้องลองทุกจำนวนที่น้อยกว่า $n$ การหยุดที่ $\sqrt{n}$ ก็เพียงพอแล้ว

จำนวนเฉพาะถูกใช้ที่ไหนบ้าง

จำนวนเฉพาะปรากฏในเรื่องการแยกตัวประกอบ การหารลงตัว โจทย์ตัวหารร่วมมาก และโจทย์ตัวคูณร่วมน้อย จำนวนเฉพาะสำคัญเพราะจำนวนเต็มทุกจำนวนที่มากกว่า $1$ สามารถแยกเป็นตัวประกอบเฉพาะได้อย่างเป็นเอกลักษณ์เมื่อไม่นับลำดับ

จำนวนเฉพาะยังปรากฏในเลขคณิตมอดูลาร์และวิทยาการเข้ารหัสลับ ในวิทยาการเข้ารหัสลับ บริบทจะเฉพาะทางมากกว่า และใช้จำนวนเฉพาะขนาดใหญ่ร่วมกับกฎและขั้นตอนวิธีเพิ่มเติม

ลองทำโจทย์ที่คล้ายกัน

ลองตรวจ $47$ และ $51$ ด้วยวิธีรากที่สองแบบเดียวกัน จำนวนหนึ่งเป็นจำนวนเฉพาะและอีกจำนวนหนึ่งเป็นจำนวนประกอบ ดังนั้นนี่เป็นวิธีเร็ว ๆ ในการเช็กว่าคุณเข้าใจกฎการหยุดที่ $\sqrt{n}$ หรือไม่