ເນື້ອຫາ

• ຂັ້ນຕອນ
• ວິທີທີ່ 1 ຈາກທັງ:ົດ 2: ຕົວແຍກຂັ້ນຕອນ
• ວິທີທີ່ 2 ຂອງ 2: ປັດໃຈຫຼັກ
• ຄໍາແນະນໍາ

ຕົວຫານໃຫຍ່ສຸດທີ່ສຸດ (GCD) ຂອງສອງ ຈຳ ນວນເຕັມເປັນ ຈຳ ນວນເຕັມໃຫຍ່ທີ່ສຸດທີ່ຫານຕົວເລກແຕ່ລະຕົວເລກເຫຼົ່ານັ້ນ. ຕົວຢ່າງ, gcd ສໍາລັບ 20 ແລະ 16 ແມ່ນ 4 (ທັງ 16 ແລະ 20 ມີຕົວຫານໃຫຍ່, ແຕ່ພວກມັນບໍ່ແມ່ນເລື່ອງທໍາມະດາ - ຕົວຢ່າງ, 8 ແມ່ນຕົວຫານ 16, ແຕ່ບໍ່ແມ່ນຕົວຫານ 20). ມີວິທີການທີ່ງ່າຍແລະເປັນລະບົບສໍາລັບການຊອກຫາ GCD, ເອີ້ນວ່າ "ສູດການຄິດໄລ່ຂອງ Euclid". ບົດຄວາມນີ້ຈະສະແດງໃຫ້ເຈົ້າເຫັນວິທີຊອກຫາຕົວຫານທົ່ວໄປທີ່ໃຫຍ່ທີ່ສຸດຂອງສອງ ຈຳ ນວນເຕັມ.

ຂັ້ນຕອນ

ວິທີທີ່ 1 ຈາກທັງ:ົດ 2: ຕົວແຍກຂັ້ນຕອນ

1. 1 ຫຼີກເວັ້ນເຄື່ອງminາຍລົບໃດ.
2. 2 ຮຽນຮູ້ຄໍາສັບ: ເມື່ອຫານ 32 ດ້ວຍ 5,
   • 32 - ເງິນປັນຜົນ
   • 5 - ຕົວຫານ
   • 6 - ເອກະຊົນ
   • 2 - ສ່ວນທີ່ເຫຼືອ
3. 3 ກໍານົດຕົວເລກທີ່ໃຫຍ່ກວ່າ. ມັນຈະເປັນຕົວຫານ, ແລະຕົວເລກທີ່ນ້ອຍກວ່າຈະເປັນຕົວຫານ.
4. 4 ຂຽນສູດການຄິດໄລ່ຕໍ່ໄປນີ້: (ເງິນປັນຜົນ) = (ຕົວຫານ) * (ຕົວຫານ) + (ສ່ວນທີ່ເຫຼືອ)
5. 5 ເອົາຕົວເລກທີ່ໃຫຍ່ກວ່າມາແທນບ່ອນຂອງເງິນປັນຜົນແລະຕົວເລກທີ່ນ້ອຍກວ່າຢູ່ໃນບ່ອນຂອງຕົວຫານ.
6. 6 ຊອກຫາຕົວເລກໃຫຍ່ກວ່ານັ້ນຫານດ້ວຍຈໍານວນເທົ່າໃດ, ແລະຂຽນຜົນໄດ້ຮັບແທນຕົວເລກ.
7. 7 ຊອກຫາສ່ວນທີ່ເຫຼືອແລະຂຽນມັນໄວ້ໃນຕໍາ ແໜ່ງ ທີ່ເappropriateາະສົມໃນສູດການຄິດໄລ່.
8. 8 ຂຽນສູດການຄິດໄລ່ຄືນໃ່, ແຕ່ (A) ຂຽນຕົວຫານກ່ອນ ໜ້າ ເປັນເງິນປັນຜົນໃ,່, ແລະ (B) ສ່ວນທີ່ເຫຼືອຜ່ານມາເປັນຕົວຫານໃnew່.
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 ຫຼີກເວັ້ນເຄື່ອງminາຍລົບໃດ.
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 ຊອກຫາປັດໃຈຫຼັກ prime ທົ່ວໄປ.
   • ຕົວຢ່າງ, ສໍາລັບ 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
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, 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 ເທົ່າກັບສູນ, ຫຼັງຈາກນັ້ນຕົວເລກໃດzທີ່ບໍ່ແມ່ນສູນແມ່ນຕົວຫານຂອງເຂົາເຈົ້າ, ສະນັ້ນໃນກໍລະນີນີ້ບໍ່ມີ GCD (ນັກຄະນິດສາດພຽງແຕ່ເຊື່ອວ່າຕົວຫານທົ່ວໄປທີ່ໃຫຍ່ທີ່ສຸດຂອງ 0 ແລະ 0 ແມ່ນ 0).