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

கணிதத்தில் யூக்ளிடிய படிமுறைத் தீர்வு (Euclidean algorithm) என்பது இரு முழுஎண்களின் மீப்பெரு பொது வகுத்தியைக் (மீபொவ) காணும் வழிமுறையாகும். நேர் முழுஎண்களின் மீப்பெரு வகுத்தி காண்பதற்கே இம்முறையானது அதிகம் பயன்படுத்தப்படுகிறது. இவ் வழிமுறையை கணிதவியலாளர் யூக்ளிட் தனது புத்தகத்தில் ( VII , X -Elements) விளக்கியுள்ளார்.

BA, DC நீளங்களின் மீபொவ காணும் யூக்ளிடிய படிமுறைத் தீர்வின் விளக்க வரைபடம். சிறிய நீளம் DC ஐக் கொண்டு பெரிய நீளம் BA ஒருமுறை அளக்கப்படுகிறது; அதில் கிடைக்கும் மீத நீளம் EA. இப்பொழுது நீளம் EA ஐக் கொண்டு நீளம் DC ஐ இருமுறை அளக்கக் கிடைக்கும் மீதி நீளம் FC. மீண்டும் FC ஐக் கொண்டு நீளம் EA மூன்று முறை அளக்கப்படும்போது மீதி நீளம் இல்லை. எனவே BA, DC நீளங்களின் மீபொப FC ஆகும். வலதுபக்கத்திலுள்ள படவிளக்கம் 49, 21 இன் மீபொவ கணக்கிடுவதினை விளக்குகிறது.

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

யூக்ளிடின் புத்தகத்தில் காணப்பட்ட படிமுறைத்தீர்வு (கிமு 300) இயல் எண்களுக்கும் நீளங்களுக்கும் மட்டும் பயன்படுத்தக் கூடியதாக இருந்தது. 19 ஆம் நூற்றாண்டில் காசிய முழுஎண்கள், ஒரு மாறியிலமைந்த பல்லுறுப்புக்கோவைகள் போன்றவற்றுக்கும் பயன்படும் வகையில் இப் படிமுறைத்தீர்வு பொதுமைப்படுத்தப்பட்டது.

செயல்முறை

கழித்தலானது பயன்படுத்தல்

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

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

படவிளக்கம்

தொடக்கநிலை பச்சைநிற செவ்வகத்தின் அளவுகள் 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₃

…

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

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

1071 = 2 × 462 + 147.

462 = 3 × 147 + 21.

147 = 7 × 21 + 0.

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

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

படி k	சமன்பாடு	ஈவும் மீதமும்
0	1071 = q0 462 + r0	q0 = 2 and r0 = 147
1	462 = q1 147 + r1	q1 = 3 and r1 = 21
2	147 = q2 21 + r2	q2 = 7 and r2 = 0; படிமுறைத் தீர்வு முடிவுற்றது

வெளியிணைப்புகள்

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

• 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 வந்தவழி இயந்திரம்