วิธีหารแบบยุคลิด

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

17 ถูกแบ่งเป็น 3 กลุ่ม กลุ่มละ 5 โดยเหลือ 2 ในที่นี้ ตัวตั้งคือ 17 ตัวหารคือ 5 ผลหารคือ 3 และเศษคือ 2
17 = 5 × 3 + 2

ตัวอย่างโดยทั่วไป

 

พายแบ่งเป็น 9 ชิ้น มีคน 4 คน แต่ละคนได้พาย 2 ชิ้น เหลืออีก 1 ชิ้น

สมมุติว่าพายชิ้นหนึ่งแบ่งเป็น 9 ชิ้นเล็ก คน 4 คนแบ่งพายเท่าๆ กัน โดยวิธีหารแบบยุคลิด 9 หารด้วย 4 ได้ 2 เศษ 1 นั่นคือแต่ละคนได้พาย 2 ชิ้น เหลือ 1 ชิ้น

ประโยคข้างต้นสามารถยืนยันโดยการคูณ การดำเนินการผกผันของการหาร: ถ้าคนทั้ง 4 ได้พายคนละ 2 ชิ้น แล้วพายที่แจกคนเหล่านี้มีจำนวน 4 × 2 = 8 ชิ้น เมื่อรวมกับอีก 1 ชิ้นที่เหลืออยู่จะได้ 9 ชิ้น ดังนั้น 9 = 4 × 2 + 1

โดยทั่วไป ถ้าจำนวนของชิ้นพายแทนด้วย a และจำนวนของคนคือ b สามารถแบ่งพายให้ทุกคน คนละเท่าๆกัน โดยแต่ละคนได้พาย q ชิ้น (ผลหาร)และพายจำนวน r < b ชิ้นเหลืออยู่(เศษ) สมการ a = bq + r เป็นจริงทุกกรณี

ถ้าพาย 9 ชิ้นถูกแบ่งให้คน 3 คน แทนที่จะเป็น 4 คน แต่ละคนจะได้พาย 3 ชิ้นและไม่มีพายเหลืออยู่ ในกรณีนี้ เศษเป็นศูนย์ เพราะ 3 หาร ลงตัว

การหารแบบยุคลิดขยายกรณีเป็นจำนวนเต็มลบได้โดยใช้สูตรเดียวกัน เช่น −9 = 4 × (−3) + 3 ดังนั้น −9 หารด้วย 4 ได้ −3 เศษ 3 เศษเป็นจำนวนเดียวในสี่จำนวนเหล่านี้ไม่สามารถเป็นลบได้

ประพจน์แสดงทฤษฎีบท

กำหนดจำนวนเต็ม ${\displaystyle a}$  และ ${\displaystyle b}$  ซึ่งมีค่าไม่เป็นศูนย์ จะมีจำนวนเต็ม ${\displaystyle q}$  และ ${\displaystyle r}$  เพียงหนึ่งคู่เท่านั้นที่ ${\displaystyle a=bq+r}$  และ ${\displaystyle 0\leq r<|b|}$  โดย ${\displaystyle |b|}$  แทนค่าสัมบูรณ์ของ ${\displaystyle b}$ 

จำนวนทั้งสี่ที่ปรากฏในทฤษฎีบทนี้มีชื่อดังนี้ ${\displaystyle a}$  เรียกตัวตั้ง ${\displaystyle b}$  เรียกตัวหาร ${\displaystyle q}$  เรียกผลหาร และ ${\displaystyle r}$  เรียกเศษ

การคำนวณผลหารและเศษจากตัวตั้งและตัวหารเรียกว่าการหารหรือการหารแบบยุคลิดเพื่อเลี่ยงความกำกวม ทฤษฎีบทนี้มักกล่าวถึงด้วยชื่อขั้นตอนการหาร แม้ว่าจะเป็นทฤษฎีและไม่ใช่ขั้นตอนวิธี เพราะการพิสูจน์ก็ให้ขั้นตอนวิธีหารอย่างง่ายสำหรับคำนวณ ${\displaystyle q}$  และ ${\displaystyle r}$ 

การหารไม่นิยามถ้า ${\displaystyle b=0}$  ดูหน้าการหารด้วยศูนย์

ตัวอย่าง

• ถ้า a = 7 และ b = 3 แล้ว q = 2 และ r = 1 เพราะ 7 = 3 × 2 + 1
• ถ้า a = 7 และ b = −3 แล้ว q = −2 และ r = 1 เพราะ 7 = −3 × (−2) + 1
• ถ้า a = −7 และ b = 3 แล้ว q = −3 และ r = 2 เพราะ −7 = 3 × (−3) + 2
• ถ้า a = −7 และ b = −3 แล้ว q = 3 และ r = 2 เพราะ −7 = −3 × 3 + 2

อ้างอิง

1. Burton, David M. (2010). Elementary Number Theory. McGraw-Hill. pp. 17–19. ISBN 978-0-07-338314-9.