เนื้อหา

• ขั้นตอน
• วิธีที่ 1 จาก 2: อัลกอริธึมตัวแบ่ง
• วิธีที่ 2 จาก 2: ปัจจัยสำคัญ
• เคล็ดลับ

ตัวหารร่วมที่ยิ่งใหญ่ที่สุด (GCD) ของจำนวนเต็มสองจำนวนคือจำนวนเต็มที่มากที่สุดที่หารตัวเลขแต่ละจำนวนเหล่านั้น ตัวอย่างเช่น gcd สำหรับ 20 และ 16 คือ 4 (ทั้ง 16 และ 20 มีตัวหารขนาดใหญ่ แต่ไม่เหมือนกัน - ตัวอย่างเช่น 8 เป็นตัวหารของ 16 แต่ไม่ใช่ตัวหารของ 20) มีวิธีการที่ง่ายและเป็นระบบในการค้นหา GCD ที่เรียกว่า "อัลกอริทึมของ Euclid" บทความนี้จะแสดงวิธีหาตัวหารร่วมมากของจำนวนเต็มสองจำนวน

ขั้นตอน

วิธีที่ 1 จาก 2: อัลกอริธึมตัวแบ่ง

1. 1 ละเว้นเครื่องหมายลบใด ๆ
2. 2 เรียนรู้คำศัพท์: เมื่อหาร 32 ด้วย 5
   • 32 - เงินปันผล
   • 5 - ตัวหาร
   • 6 - ส่วนตัว
   • 2 - ส่วนที่เหลือ
3. 3 กำหนดจำนวนที่มากขึ้น มันจะหารลงตัวและจำนวนที่น้อยกว่าจะเป็นตัวหาร
4. 4 เขียนอัลกอริทึมต่อไปนี้: (เงินปันผล) = (ตัวหาร) * (ผลหาร) + (ส่วนที่เหลือ)
5. 5 ใส่จำนวนที่มากกว่าแทนตัวปันผล และใส่จำนวนที่น้อยกว่าแทนตัวหาร
6. 6 หาว่าจำนวนที่มากกว่าหารด้วยน้อยกว่านั้นกี่ครั้ง แล้วเขียนผลลัพธ์แทนผลหาร
7. 7 ค้นหาส่วนที่เหลือและเขียนในตำแหน่งที่เหมาะสมในอัลกอริทึม
8. 8 เขียนอัลกอริทึมอีกครั้ง แต่ (A) เขียนตัวหารก่อนหน้าเป็นตัวหารใหม่ และ (B) เศษที่เหลือก่อนหน้าเป็นตัวหารใหม่
9. 9 ทำซ้ำขั้นตอนก่อนหน้าจนเหลือ 0
10. 10 ตัวหารสุดท้ายจะเป็นตัวหารร่วมมาก (GCD)
11. 11 ตัวอย่างเช่น ลองหา GCD สำหรับ 108 และ 30:
12. 12 สังเกตว่าตัวเลข 30 และ 18 จากบรรทัดแรกสร้างบรรทัดที่สองอย่างไร จากนั้น 18 และ 12 จะสร้างแถวที่สาม และ 12 และ 6 จะสร้างแถวที่สี่ ไม่ใช้ผลคูณของ 3, 1, 1 และ 2 ตัวเลขเหล่านี้แสดงถึงจำนวนครั้งที่เงินปันผลหารด้วยตัวหารได้ ดังนั้นจึงไม่ซ้ำกันในแต่ละแถว

วิธีที่ 2 จาก 2: ปัจจัยสำคัญ

1. 1 ละเว้นเครื่องหมายลบใด ๆ
2. 2 หาตัวประกอบเฉพาะของตัวเลข. นำเสนอตามที่แสดงในภาพ
   • ตัวอย่างเช่น สำหรับ 24 และ 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • ตัวอย่างเช่น สำหรับ 50 และ 35:
     • 50- 2 x 5 x 5
     • 35- 5 x 7
3. 3 หาปัจจัยเฉพาะทั่วไป.
   • ตัวอย่างเช่น สำหรับ 24 และ 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 NS 3 x 3
   • ตัวอย่างเช่น สำหรับ 50 และ 35:
     • 50 - 2 x 5 x 5
     • 35- 5 x7
4. 4 คูณปัจจัยเฉพาะร่วม.
   • สำหรับ 24 และ 18 ให้คูณ 2 และ 3 และรับ 6... 6 เป็นตัวส่วนร่วมที่ยิ่งใหญ่ที่สุดของ 24 และ 18
   • ไม่มีอะไรจะคูณกับ 50 และ 35 5 เป็นปัจจัยเฉพาะทั่วไปเพียงอย่างเดียว และมันคือ GCD
5. 5 ทำ!

เคล็ดลับ

• วิธีหนึ่งในการเขียนสิ่งนี้คือ: เงินปันผล> ตัวแบ่งตัวดัดแปลง> = ส่วนที่เหลือ; GCD (a, b) = b ถ้า mod b = 0 และ gcd (a, b) = gcd (b, a mod b) มิฉะนั้น
• ตัวอย่างเช่น ลองหา GCD (-77.91) ขั้นแรก ใช้ 77 แทน -77: GCD (-77.91) แปลงเป็น GCD (77.91) 77 น้อยกว่า 91 ดังนั้นเราจึงต้องสลับกัน แต่ให้พิจารณาว่าอัลกอริทึมทำงานอย่างไร ถ้าเราไม่เปลี่ยน เมื่อคำนวณ 77 mod 91 เราจะได้ 77 (77 = 91 x 0 + 77) เนื่องจากนี่ไม่ใช่ศูนย์ เราจึงพิจารณาสถานการณ์ (b, a mod b) นั่นคือ GCD (77.91) = GCD (91.77) 91 mod 77 = 14 (14 เป็นส่วนที่เหลือ) ไม่ใช่ศูนย์ ดังนั้น GCD (91.77) จึงกลายเป็น GCD (77.14) 77 mod 14 = 7 นี่ไม่ใช่ศูนย์ ดังนั้น GCD (77.14) จึงกลายเป็น GCD (14.7) 14 mod 7 = 0 (ตั้งแต่ 14/7 = 2 โดยไม่มีเศษ) คำตอบ: GCD (-77.91) = 7
• วิธีการที่อธิบายไว้มีประโยชน์มากสำหรับการทอนเศษส่วนอย่างง่าย ในตัวอย่างด้านบน: -77/91 = -11/13 เนื่องจาก 7 เป็นตัวส่วนร่วมที่ยิ่งใหญ่ที่สุดของ -77 และ 91
• ถ้า a และ b เท่ากับศูนย์ ดังนั้นจำนวนที่ไม่ใช่ศูนย์ใดๆ ก็คือตัวหาร ดังนั้นในกรณีนี้จะไม่มี GCD (นักคณิตศาสตร์เพียงเชื่อว่าตัวหารร่วมมากของ 0 และ 0 คือ 0)