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

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

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

สมมุติว่าพายชิ้นหนึ่งแบ่งเป็น 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 เศษเป็นจำนวนเดียวในสี่จำนวนเหล่านี้ไม่สามารถเป็นลบได้

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

จำนวนทั้งสี่ที่ปรากฏในทฤษฎีบทนี้มีชื่อดังนี้  เรียกตัวตั้ง  เรียกตัวหาร   เรียกผลหาร และ  เรียกเศษ

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

การหารไม่นิยามถ้า  ดูหน้าการหารด้วยศูนย์

ตัวอย่าง 

ถ้า 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

อ้างอิง

หมวดหมู่ : การหาร