ทฤษฎีจำนวน — จำนวนเฉพาะ การหารลงตัว และเลขคณิตมอดูลาร์

ทฤษฎีจำนวนคือการศึกษาจำนวนเต็ม หากคุณต้องการเข้าใจจำนวนเฉพาะ การหารลงตัว หรือเลขคณิตมอดูลาร์ คุณก็กำลังมองอยู่ที่แก่นหลักของทฤษฎีจำนวนแล้ว

จำนวนเฉพาะคือจำนวนเต็มที่มากกว่า $1$ และมีตัวหารบวกอยู่ exactly สองตัว คือ $1$ และตัวมันเอง การหารลงตัวถามว่าจำนวนเต็มหนึ่งหารอีกจำนวนหนึ่งได้โดยไม่เหลือเศษหรือไม่ ส่วนเลขคณิตมอดูลาร์ติดตามค่าเศษ จึงมักถูกเรียกว่าเลขคณิตแบบนาฬิกา

ทฤษฎีจำนวนครอบคลุมอะไรบ้าง

แนวคิดทั้งสามนี้เชื่อมโยงกัน:

• จำนวนเฉพาะเป็นหน่วยพื้นฐานของจำนวนเต็มบวก
• การหารลงตัวบอกว่าจำนวนเต็มหนึ่งหารอีกจำนวนหนึ่งได้พอดีเมื่อใด
• เลขคณิตมอดูลาร์เปลี่ยนคำถามเรื่องการหารลงตัวให้เป็นคำถามเรื่องเศษ

ตัวอย่างเช่น การพูดว่า "$a$ หารด้วย $n$ ลงตัว" เท่ากับการพูดว่า

$$a \equiv 0 \pmod n$$

ดังนั้น คำถามเรื่องการหารลงตัวจึงมักเขียนใหม่ให้อยู่ในรูปคำถามเรื่องเศษได้

จำนวนเฉพาะ: หน่วยประกอบพื้นฐาน

จำนวนเฉพาะเริ่มต้นเป็น

$$2, 3, 5, 7, 11, 13, \dots$$

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

ถ้าจำนวนเต็มบวกที่มากกว่า $1$ ไม่เป็นจำนวนเฉพาะ จะเรียกว่าเป็นจำนวนประกอบ ตัวอย่างเช่น $21$ เป็นจำนวนประกอบ เพราะว่า

$$21 = 3 \cdot 7$$

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

การหารลงตัว: เมื่อจำนวนหนึ่งหารอีกจำนวนได้พอดี

ถ้า $a$ และ $b$ เป็นจำนวนเต็ม โดยที่ $b \ne 0$ แล้วข้อความว่า "$b$ หาร $a$ ลงตัว" หมายความว่ามีจำนวนเต็ม $k$ ที่ทำให้

$$a = bk$$

เขียนได้เป็น

$$b \mid a$$

ตัวอย่างเช่น $4 \mid 20$ เพราะ $20 = 4 \cdot 5$ แต่ $4 \nmid 22$ เพราะเมื่อหาร $22$ ด้วย $4$ จะเหลือเศษ

การหารลงตัวเป็นภาษาพื้นฐานของตัวประกอบ พหุคูณ หารร่วมมาก และคูณร่วมน้อย อีกทั้งยังอธิบายกฎที่คุ้นเคยเหล่านี้ได้ด้วย:

• จำนวนหนึ่งหารด้วย $2$ ลงตัว ถ้าหลักหน่วยเป็นเลขคู่
• จำนวนหนึ่งหารด้วย $5$ ลงตัว ถ้าหลักหน่วยเป็น $0$ หรือ $5$
• จำนวนหนึ่งหารด้วย $3$ ลงตัว ถ้าผลบวกของเลขโดดหารด้วย $3$ ลงตัว

กฎข้อสุดท้ายนั้นไม่ใช่แค่เทคนิคจำ แต่มาจากเลขคณิตมอดูลาร์

เลขคณิตมอดูลาร์: การคำนวณด้วยเศษ

เมื่อจำนวนเต็มสองจำนวนให้เศษเท่ากันเมื่อหารด้วย $n$ เราเรียกว่าทั้งสองจำนวนสมมูลกันมอดูโล $n$ เขียนได้ว่า

$$a \equiv b \pmod n$$

ซึ่งหมายความว่า $n$ หาร $a-b$ ลงตัว

ตัวอย่างเช่น

$$17 \equiv 5 \pmod{12}$$

เพราะ $17$ และ $5$ ต่างก็เหลือเศษ $5$ เมื่อหารด้วย $12$ และอีกทางหนึ่งก็เพราะ $12$ หาร $17 - 5 = 12$ ลงตัว

แนวคิดนี้มีประโยชน์เพราะคุณสามารถแทนจำนวนหนึ่งด้วยอีกจำนวนที่สมมูลกันแต่เรียบง่ายกว่าได้ บนนาฬิกา $12$ ชั่วโมง การบวก $15$ ชั่วโมงให้ผลเหมือนกับการบวก $3$ ชั่วโมง เพราะว่า

$$15 \equiv 3 \pmod{12}$$

ตัวอย่างทำจริง: ทำไม $231$ จึงหารด้วย $3$ ลงตัว?

พิจารณาจำนวน $231$

ก่อนอื่น เขียนให้อยู่ในรูปค่าประจำหลัก:

$$231 = 2 \cdot 100 + 3 \cdot 10 + 1$$

จากนั้นพิจารณาแบบมอดูโล $3$ เนื่องจาก

$$10 \equiv 1 \pmod 3$$

จึงได้ว่า

$$100 = 10^2 \equiv 1^2 \equiv 1 \pmod 3$$

ดังนั้น

$$231 \equiv 2 \cdot 1 + 3 \cdot 1 + 1 \equiv 2 + 3 + 1 = 6 \equiv 0 \pmod 3$$

เพราะ $231 \equiv 0 \pmod 3$ จำนวนนี้จึงหารด้วย $3$ ลงตัว

นี่อธิบายกฎผลบวกของเลขโดดได้ว่า ในฐาน $10$ กำลังแต่ละกำลังของ $10$ สมมูลกับ $1$ มอดูโล $3$ ดังนั้นทั้งจำนวนจึงมีเศษเท่ากับผลบวกของเลขโดดของมัน

และเมื่อหารต่อไป จะได้ว่า

$$231 = 3 \cdot 77 = 3 \cdot 7 \cdot 11$$

ดังนั้น $231$ เป็นจำนวนประกอบ ไม่ใช่จำนวนเฉพาะ

ข้อผิดพลาดที่พบบ่อยในทฤษฎีจำนวน

คิดว่า $1$ เป็นจำนวนเฉพาะ

$1$ ไม่ใช่จำนวนเฉพาะ จำนวนเฉพาะต้องมีตัวหารบวก exactly สองตัว แต่ $1$ มีเพียงตัวเดียว

ลืมเงื่อนไขในการหารลงตัว

ข้อความ $b \mid a$ จะมีความหมายก็ต่อเมื่อ $b \ne 0$ เท่านั้น การหารด้วยศูนย์ทำไม่ได้

สับสนระหว่างความเท่ากันกับความสมมูล

$17 \equiv 5 \pmod{12}$ ไม่ได้หมายความว่า $17 = 5$ แต่มันหมายความว่าทั้งสองจำนวนต่างกันอยู่เท่ากับพหุคูณของ $12$

ใช้กฎการหารลงตัวมากเกินไป

บางกฎตรวจได้เร็วเพราะเลขคณิตฐาน $10$ ทำให้มันใช้ได้สะดวก แต่ไม่ได้แปลว่าตัวหารทุกตัวจะมีกฎเกี่ยวกับเลขโดดที่ง่ายเสมอไป

ทฤษฎีจำนวนพบได้ที่ไหน

ในระดับโรงเรียน ทฤษฎีจำนวนปรากฏในเรื่องการแยกตัวประกอบ โจทย์เศษ การพิสูจน์การหารลงตัว และโจทย์ลักษณะนาฬิกา นอกจากนี้ยังพบเมื่อคุณย่อเศษส่วน มองหาตัวประกอบร่วม หรือแก้ปัญหาที่มีรูปแบบวนซ้ำ

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

ลองทำด้วยตัวเอง

ลองใช้เหตุผลแบบเดียวกันกับ $462$ ก่อนอื่นใช้ผลบวกของเลขโดดเพื่อตรวจว่าหารด้วย $3$ ลงตัวหรือไม่ จากนั้นแยกตัวประกอบให้พอที่จะตัดสินได้ว่ามันเป็นจำนวนเฉพาะหรือจำนวนประกอบ

ถ้าคุณต้องการตรวจวิธีทำของตัวเอง ให้ลองแก้โจทย์การหารลงตัวหรือโจทย์เศษที่คล้ายกันในเครื่องมือแก้โจทย์คณิตศาสตร์ แล้วเปรียบเทียบขั้นตอนเลขคณิตมอดูลาร์กับวิธีของคุณ