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

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

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

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

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

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

การหารไม่นิยามถ้า $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