ตัวหารร่วมมาก
ตัวหารร่วมมาก (ห.ร.ม.) ของจำนวนเต็มสองจำนวนคือจำนวนที่หารทั้งสองจำนวนลงตัว และไม่มีจำนวนอื่นที่มากกว่าซึ่งหารทั้งสองจำนวนลงตัวด้วย
ตัวอย่างเช่น พิจารณา 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 แล้วทำตามขั้นตอนต่อไปนี้:
- หาร x / y และจำเศษจากการหารไว้ ให้เศษนี้แทนด้วย z ในตัวอย่างของเราได้ 50 / 35 ซึ่งเหลือเศษ z = 15
- สลับค่าของตัวแปร โดยเก็บค่าของ y ไว้ในตัวแปร x และเก็บค่าของ z ไว้ใน y ค่าเดิมของ x ทิ้งไป หลังขั้นนี้จะได้ x = 35 และ y = 15
- ตรวจดูว่า y เท่ากับศูนย์หรือไม่ ถ้าใช่ ห.ร.ม. คือ x เนื่องจาก y ไม่เท่ากับศูนย์ จึงทำต่อไปโดยเริ่มขั้นตอนทั้งหมดใหม่จากข้อแรก
- หาร x / y อีกครั้ง คือหาร 35 / 15 ซึ่งเหลือเศษ z = 5
- สลับค่าของตัวแปร จะได้ x = 15 และ y = 5 เนื่องจาก y ไม่เท่ากับศูนย์ จึงทำต่อไป
- หาร x / y คือหาร 15 / 5 เศษจากการหารคือ z = 0
- สลับค่าของตัวแปร จะได้ x = 5 และ y = 0
- ตอนนี้ y = 0 ขั้นตอนวิธีจึงสิ้นสุด ห.ร.ม. คือ x = 5
สิ่งสำคัญคือลำดับของจำนวนไม่มีผล ถ้าสลับจำนวนในตัวอย่าง จะได้คู่ x = 35 และ y = 50 ขั้นตอนก็เหมือนเดิม:
- หาร x / y คือหาร 35 / 50 ซึ่งเหลือเศษ z = 35
- สลับค่าของตัวแปร ได้ x = 50 และ y = 35
- จะเห็นว่าขั้นนี้เพียงสลับค่าของตัวแปร x และ y กันเท่านั้น…
เครื่องคิดเลข
เครื่องคิดเลขนี้คำนวณตัวหารร่วมมาก