✖

ตัวหารร่วมมาก

ตัวหารร่วมมาก (ห.ร.ม.) ของจำนวนเต็มสองจำนวนคือจำนวนที่หารทั้งสองจำนวนลงตัว และไม่มีจำนวนอื่นที่มากกว่าซึ่งหารทั้งสองจำนวนลงตัวด้วย

ตัวอย่างเช่น พิจารณา 24 และ 32 ห.ร.ม. ของสองจำนวนนี้คือเท่าใด ขั้นแรกหาจำนวนที่หารทั้งสองจำนวนลงตัว

  • เช่น 12 หาร 24 ลงตัว แต่หาร 32 ไม่ลงตัว เพราะ 32 / 12 เท่ากับ 2.666… ซึ่งไม่ใช่จำนวนเต็ม ดังนั้น 12 จึงเป็น ห.ร.ม. ของ 24 และ 32 ไม่ได้
  • แล้ว 4 เป็นอย่างไร 4 หารทั้งสองจำนวนลงตัว 24 / 4 เท่ากับ 6 และ 32 / 4 เท่ากับ 8 ดังนั้น 4 จึงเป็นตัวเลือกแรก มีจำนวนที่มากกว่าซึ่งหารทั้งสองจำนวนลงตัวหรือไม่
  • 8 หารทั้ง 24 และ 32 ลงตัว และมากกว่า 4
  • ไม่มีจำนวนอื่นที่มากกว่า 8 ซึ่งหารทั้งสองจำนวนลงตัว ดังนั้น 8 เป็น ห.ร.ม. ของ 24 และ 32

ขั้นตอนวิธีของยุคลิดสำหรับหาตัวหารร่วมมาก

วิธีที่ค่อนข้างง่ายในการหา ห.ร.ม. ของจำนวนสองจำนวนคือขั้นตอนวิธีของยุคลิด (Euclidean algorithm) เริ่มจากจำนวนสองจำนวน x และ y ที่ต้องการหา ห.ร.ม. ลองทำกับ x = 50 และ y = 35 แล้วทำตามขั้นตอนต่อไปนี้:

  1. หาร x / y และจำเศษจากการหารไว้ ให้เศษนี้แทนด้วย z ในตัวอย่างของเราได้ 50 / 35 ซึ่งเหลือเศษ z = 15
  2. สลับค่าของตัวแปร โดยเก็บค่าของ y ไว้ในตัวแปร x และเก็บค่าของ z ไว้ใน y ค่าเดิมของ x ทิ้งไป หลังขั้นนี้จะได้ x = 35 และ y = 15
  3. ตรวจดูว่า y เท่ากับศูนย์หรือไม่ ถ้าใช่ ห.ร.ม. คือ x เนื่องจาก y ไม่เท่ากับศูนย์ จึงทำต่อไปโดยเริ่มขั้นตอนทั้งหมดใหม่จากข้อแรก
  4. หาร x / y อีกครั้ง คือหาร 35 / 15 ซึ่งเหลือเศษ z = 5
  5. สลับค่าของตัวแปร จะได้ x = 15 และ y = 5 เนื่องจาก y ไม่เท่ากับศูนย์ จึงทำต่อไป
  6. หาร x / y คือหาร 15 / 5 เศษจากการหารคือ z = 0
  7. สลับค่าของตัวแปร จะได้ x = 5 และ y = 0
  8. ตอนนี้ y = 0 ขั้นตอนวิธีจึงสิ้นสุด ห.ร.ม. คือ x = 5

สิ่งสำคัญคือลำดับของจำนวนไม่มีผล ถ้าสลับจำนวนในตัวอย่าง จะได้คู่ x = 35 และ y = 50 ขั้นตอนก็เหมือนเดิม:

  1. หาร x / y คือหาร 35 / 50 ซึ่งเหลือเศษ z = 35
  2. สลับค่าของตัวแปร ได้ x = 50 และ y = 35
  3. จะเห็นว่าขั้นนี้เพียงสลับค่าของตัวแปร x และ y กันเท่านั้น…

เครื่องคิดเลข

เครื่องคิดเลขนี้คำนวณตัวหารร่วมมาก