யூக்ளிடிய படிமுறைத்தீர்வு

யூக்ளிடிய படிமுறைத்தீர்வின் எளிய முறையில் கழித்தல் பயன்படுத்தப்படுகிறது. மீபொவ காண வேண்டிய இரு நேர் முழுஎண்களை ஒரு சோடியாக எடுத்துக்கொண்டு அந்த இரண்டு எண்களில் பெரிய எண்ணிலிருந்து சிறிய எண் கழிக்கப்பட்டு, அதில் கிடைக்கும் வித்தியாசம் மற்றும் தரப்பட்டதில் சிறிய எண் ஆகிய இரண்டும் ஒரு சோடியாகக் கொள்ளப்படுகிறது. பின்னர் இந்த சோடியிலுள்ள பெரிய எண்ணிலிருந்து சிறியஎண் கழிக்கப்பட்டு முதலில் செய்தது போலவே அடுத்த சோடி அமைக்கப்படுகிறது. சோடியின் இரு எண்களும் சமமாக வரும் நிலைவரை இச் செயலானது தொடரப்படுகிறது. அவ்வாறு சம எண்கள் கிடைக்கும்பொழுது அந்தச் சமமான எண்தான் முதலில் எடுத்துக்கொள்ளப்பட்ட இரு எண்களின் மீபொவ ஆகும்.

படவிளக்கம்

தொடக்கநிலை பச்சைநிற செவ்வகத்தின் அளவுகள் a = 1071, b = 462. இச் செவ்வகத்துக்குள் 462×462 அளவுள்ள இரு ஆரஞ்சுநிற சதுரங்கள் அமைக்கப்படும்போது 462×147 அளவுள்ள பச்சைநிற செவ்வகம் மீதமாகிறது; இதனுள் 147×147 அளவுள்ள இரு நீலநிற சதுரங்கள் அமைக்கப்படும்போது 21×147 அளவுள்ள பச்சைநிறச் செவ்வகம் மீதமாகிறது; இதனுள் 21×21 அளவுள்ள ஏழு சிவப்புநிற சதுரங்கள் அமைக்கப்படும்போது பச்சைநிறப் பரப்பளவு எதுவும் மீதமாவதில்லை. எனவே 1071, 462 இன் மீபொவ 21.

எடுத்துக்காட்டு

1071, 462 இன் மீபொவ காணல்:

முதல் சோடி எண்கள்: (1071, 462)1071-462 = 609, எனவே அடுத்த சோடி எண்கள்: (609, 462)609-462 = 147,  எனவே அடுத்த சோடி எண்கள்: (462, 147)462-147 = 315,  எனவே அடுத்த சோடி எண்கள்: (315, 147)315-147 = 168,   எனவே அடுத்த சோடி எண்கள்: (168, 147)168-147 = 21,    எனவே அடுத்த சோடி எண்கள்: (147, 21)147-21 = 126,    எனவே அடுத்த சோடி எண்கள்: (126, 21)126-21 = 105,    எனவே அடுத்த சோடி எண்கள்: (105, 21)105-21 = 84,     எனவே அடுத்த சோடி எண்கள்: (84, 21)84-21 = 63      எனவே அடுத்த சோடி எண்கள்: (63, 21)63-21 = 42,      எனவே அடுத்த சோடி எண்கள்: (42, 21)42-21 = 21,      எனவே அடுத்த சோடி எண்கள்: (21, 21)

1071, 462 இன் மீபொவ 21 எனக் கிடைக்கிறது.

மீபொவ காணவேண்டிய இரு எண்களில் ஒன்று மற்றொன்றைவிட மிகச் சிறியதாக இருக்கும்பட்சத்தில் மீபொவ காணும்வரை கழித்துத் தொடர வேண்டிய படிகளின் எண்ணிக்கை அதிகமாக உள்ளதால் படிகளின் எண்ணிக்கையைக் குறைத்து விரைவாக மீபொவ காணும்வகையில், கழித்தலுக்குப் பதில் வகுத்தல் பயன்படுத்தப்படுகிறது.

மீபொவ காணவேண்டிய இரு எண்களில் கழித்தலுக்குப் பதில் நெடுமுறை வகுத்தல் பயன்படுத்தப்படுகிறது. பெரிய எண்ணை சிறிய எண்ணால் வகுக்கக் கிடைக்கும் மீதியால் சிறிய எண் வகுக்கப்படுகிறது. இந்த வகுத்தலில் கிடைக்கும் இரண்டாவது மீதியால் முதல் மீதி வகுக்கப்பட்டு மூன்றாவது மீதி கண்டுபிடிக்கப்படுகிறது. மீதியாக சுழி கிடைக்கும்வரை இவ்வாறு வகுப்பது தொடரப்படுகிறது. எந்த எண்ணால் வகுக்கும்போது மீதியாக சுழி கிடைக்கிறதோ அந்த எண் தான் மூல எண்களின் மீபொவ ஆகும்.

எடுத்துக்காட்டு

1071, 462 இன் மீபொவ காணல்:

    ____462)1071(2     924      ________      147)462(3          441          ________            21)147(7               147               _____                  0                _______

1071, 462 இன் மீபொவ 21.

மீபொவ காணவேண்டிய இரு நேர் முழுஎண்கள் a , b இல் b < a எனில் மீபொவ காணும் பொது வழிமுறையின் படிநிலைகள்:

a = q₀ b + r₀

b = q₁ r₀ + r₁

r₀ = q₂ r₁ + r₂

r₁ = q₃ r₂ + r₃

…

இப்படிநிலைகள் ஒவ்வொன்றிலும் மீதிகளின் மதிப்புகள் குறைந்து கொண்டே வரும் என்பதாலும் அவை எதிர்மதிப்புகளாக இருக்காது என்பதாலும் இந்தப் படிகளைத் தொடரும்போது ஒரு கட்டத்தில் மீதி சுழியாக இருக்கும்^[2]. இதில் இறுதியாகப் பெறப்பட்ட சுழியற்ற மீதியே a , b இன் மீபொவ ஆகும்.

மேலேயுள்ள எடுத்துக்காட்டினை இம்முறையில் எழுதுதல்:

1071 = 2 × 462 + 147.

462 = 3 × 147 + 21.

147 = 7 × 21 + 0.

கடைசி மீதி சுழி என்பதால் படிமுறைத் தீர்வு இத்துடன் முடிவடைகிறது. 1071, 462 இன் மீபொவ 21.

இப் படிநிலைகளின் அட்டவணை வடிவம்:

விக்கிமீடியா பொதுவகத்தில்,
யூக்ளிடிய படிமுறைத்தீர்வு
என்பதில் ஊடகங்கள் உள்ளன.

• Demonstrations of Euclid's algorithm
• Weisstein, Eric W., "Euclidean Algorithm", MathWorld.
• Euclid's Algorithm at cut-the-knot
• Euclid's algorithm at PlanetMath.
• The Euclidean Algorithm at MathPages
• Euclid's Game at cut-the-knot
• Music and Euclid's algorithm பரணிடப்பட்டது 2007-08-09 at the வந்தவழி இயந்திரம்