เครื่องคิดเลขตัวหารร่วมมาก

การหาตัวหารร่วมมาก (gcd) เป็นงานที่ค่อนข้างได้รับความนิยม การดำเนินการนี้ช่วยให้เราดำเนินการคำนวณที่มีเศษส่วนธรรมดาปรากฏขึ้น

วิธีการค้นหา GCD

มีเคล็ดลับมากมายในการหาตัวหารร่วมมาก เราจะพิจารณาความนิยมสูงสุดของพวกเขา

การหา GCD ด้วยการแยกย่อยตัวเลขออกเป็นตัวประกอบเฉพาะ

วิธีนี้เป็นวิธีที่ใช้บ่อยที่สุดในการแก้ปัญหาทางคณิตศาสตร์

อัลกอริทึมสำหรับการพิจารณา GCD ด้วยการแยกย่อยออกเป็นปัจจัยสำคัญประกอบด้วยขั้นตอนต่อไปนี้:

• เราแสดงตัวเลขเป็นตัวประกอบเฉพาะ ตัวอย่างเช่น เลข 20 สามารถแสดงเป็นผลคูณของ 2 ⋅ 2 ⋅ 5
• เลือกปัจจัยที่จะปรากฏในส่วนขยายทั้งสอง
• ค้นหาผลคูณของปัจจัยเหล่านี้

ลองพิจารณาตัวอย่างการใช้อัลกอริทึมนี้ในทางปฏิบัติ:

กำหนด GCD ของตัวเลข 12 และ 8

แยกย่อย 12 และ 8 เป็นตัวประกอบเฉพาะ:

• 12 = 2 ⋅ 2 ⋅ 3.
• 8 = 2 ⋅ 2 ⋅ 2.

เราจะดูว่ามีปัจจัยใดบ้างในส่วนขยายทั้งสอง ค้นหา: 2 และ 2

เราคูณปัจจัยและรับ:

• 2 ⋅ 2 = 4.

คำตอบ: gcd (12, 8) = 4

กำหนด GCD ของตัวเลข 75 และ 150

ลำดับการแก้ปัญหาคล้ายกับตัวอย่างก่อนหน้านี้

ลองแทน 75 และ 150 เป็นตัวประกอบเฉพาะ:

• 75 = 3 ⋅ 5 ⋅ 5.
• 150 = 2 ⋅ 3 ⋅ 5 ⋅ 5

กำหนดปัจจัยที่เกิดซ้ำในส่วนขยายทั้งสอง: 3, 5 และ 5

เราคูณจำนวนผลลัพธ์เข้าด้วยกัน: 3 ⋅ 5 ⋅ 5 = 75

คำตอบ: gcd (75, 150) = 75.

กำหนด GCD ของตัวเลข 9 และ 5

ตัวอย่างนี้ใช้จำนวนเฉพาะที่มีตัวคูณเป็น 1 เท่านั้น

เมื่อแยกตัวประกอบของ 9 และ 5 เป็นตัวประกอบเฉพาะ เราจะเห็นว่าไม่มีตัวประกอบที่เหมือนกัน:

• 5 = 5.
• 9 = 3 ⋅ 3.

โปรดจำไว้ว่ากรณีนี้เป็นกรณีพิเศษ ตัวเลขดังกล่าวคือ coprime และตัวหารร่วมกันคือหนึ่ง

อัลกอริทึมของยุคลิด

อัลกอริทึมนี้ตั้งชื่อตาม Euclid นักคณิตศาสตร์ชาวกรีกโบราณ ซึ่งเป็นคนแรกที่อธิบายอัลกอริทึมนี้ไว้ในงานเขียนของเขา (เล่มที่ 7 และ 10 ของ "จุดเริ่มต้น") เป็นที่ทราบกันดีว่า Euclid ไม่ใช่ผู้เขียนอัลกอริทึมนี้ อย่างไรก็ตาม ถือว่าเป็นหนึ่งในอัลกอริทึมที่เก่าแก่ที่สุดที่ใช้อยู่ในปัจจุบัน

อัลกอริทึมของยูคลิดทำให้การคำนวณตัวหารร่วมมากของจำนวนบวกสองตัวเป็นเรื่องง่าย

หากต้องการค้นหา GCD (a, b) อัลกอริทึมนี้จะมีลักษณะดังนี้:

• ถ้า a = 0 ดังนั้น gcd(a, b) = b เพราะ gcd(0, b) = b และอัลกอริทึมจะหยุดทำงาน
• ถ้า b = 0 ดังนั้น gcd(a, b) = a เพราะ gcd(a, 0) = a และอัลกอริทึมจะหยุดทำงาน
• หาร a ด้วย b ด้วยเศษที่เหลือ (a = b ⋅ q + r)
• ค้นหา gcd(b, r) โดยใช้อัลกอริทึมของ Euclid เนื่องจาก gcd(a, b) = gcd(b, r)

เพื่อตรวจสอบประสิทธิภาพของวิธีการในทางปฏิบัติ ลองพิจารณาตัวอย่าง

จำเป็นต้องกำหนด GCD ของตัวเลข 270 และ 192

• a = 270, b = 192.
• a ≠ 0.
• b ≠ 0.

หาร a ด้วย b เราจะได้:

• 270 / 192 = 1 (ที่เหลือคือ 78).

คุณสามารถเขียนผลลัพธ์เป็น: 270 = 192 ⋅ 1 + 78

ต่อไป เราจะคำนวณ gcd (192, 78) เนื่องจาก gcd (270, 192) = gcd (192, 78)

ไปต่อกันเถอะ

• a = 192, b = 78.
• a ≠ 0.
• b ≠ 0.

หาร a ด้วย b เราจะได้:

• 192 / 78 = 2 (ที่เหลือคือ 36)

เขียนเป็น:

• 192 = 78 ⋅ 2 + 36.

คำนวณ gcd(78, 36) ตั้งแต่ gcd(192, 78) = gcd(78, 36)

• a = 78, b = 36.
• a ≠ 0.
• b ≠ 0.

หาร a ด้วย b เราจะได้:

• 78 / 36 = 2 (เศษที่เหลือคือ 0)

ลองเขียนผลลัพธ์เป็น:

• 78 = 36 ⋅ 2 + 6

คำนวณ gcd(36, 6) เนื่องจาก gcd(78, 36) = gcd(36, 6)

• a = 36, b = 6.
• a ≠ 0.
• b ≠ 0.

นำ A ไปหารด้วย B เราจะได้ 36 / 6 = 6 (เศษที่เหลือคือ 0)

เขียนผลลัพธ์ในรูปแบบต่อไปนี้:

• 36 = ​​6 ⋅ 6 + 0

ต่อไปเราจะพบ gcd(6, 0) เนื่องจาก gcd(36, 6) = gcd(6, 0)

• a = 6, b = 0.
• ก ≠ 0.
• b = 0.

ผลลัพธ์ที่ได้คือ:

• gcd(6, 0) = 6.

ดังนั้นเราจึงมีลำดับการคำนวณดังต่อไปนี้:

• gcd(270, 192) = gcd(192, 78) = gcd(78, 36) = gcd(36, 6) = gcd(6, 0) = 6

ด้วยเหตุนี้ เราจึงมีคำตอบ:

• gcd(270, 192) = 6.

วิธีการค้นหาแต่ละวิธีที่กล่าวถึงข้างต้นมีข้อดีและข้อเสีย วิธีแรกนั้นยอดเยี่ยมสำหรับการทำงานกับตัวอย่างที่ค่อนข้างง่าย ซึ่งแตกต่างจากวิธีที่สอง ซึ่งสามารถใช้แก้ปัญหาทางคณิตศาสตร์ที่ซับซ้อนมากขึ้นได้