மீப்பெரு பொது வகுத்தி

கணிதத்தில் மீப்பெரு பொது வகுத்தி (மீ.பொ.வ) (இலங்கை வழக்கு: பொதுக் காரணிகளுள் பெரியது - பொ.கா.பெ), greatest common divisor (gcm), greatest common denominator (gcd), greatest common factor (gcf), அல்லது highest common factor (hcf)) அல்லது பொதுச் சினைகளுள் பெரியது (பொ.சி.பெ) என்பது சுழியாக இல்லாத இரண்டு அல்லது அதற்கும் கூடுதலான முழு எண்களை மீதம் விழாமல் வகுக்கக்கூடிய மிகப்பெரிய எண் ஆகும். ஓர் எண்ணை மீதமில்லாமல் வகுக்கும் எண்னை வகுத்தி (இலங்கை வழக்கு: காரணி) என்பர்.

பொது விளக்கம் தொகு

a, b ஆகிய இரண்டு எண்களுக்கு இடையேயான மீப்பெரு பொது வகுத்தி (மீ.பொ.வ.) என்பதை மீபொவ (a, b)என்று எழுதிக்காட்டுவது வழக்கம்; எடுத்துக்காட்டாக மீபொவ (12, 18) = 6, மீபொவ(−4, 14) = 2. இரண்டு எண்களுக்கு இடையே மீபொவ-ஆக 1 என்னும் எண் மட்டும் இருந்தால், பிற பொது வகுத்திகள் அவ்விரு எண்களுக்கும் இடையே இல்லை என்பதால் அவ்விரு எண்ணையும் ஒன்றுக்கு ஓன்று பகா எண்கள் (relatively prime அல்லது co-prime) என்று அழைப்பர். இதனை ஒப்பீட்டு பகா எண் அல்லது இடைத்தொடர்புப் பகாத்தனி (relatively prime) என்றும் கூறுவர். எடுத்துக்காட்டாக 7 ம் 16 உம் ஒன்றுக்கு ஒன்று பகா எண்கள்.

மீப்பெரு பொது வகுத்தி என்னும் கருத்து பின்னங்களை மேலும் சுருக்கமாக எழுதமுடியாத எளிமையான வடிவத்துக்கு மாற்ற உதவுவது. எடுத்துக்காட்டாக மீபொவ(42, 56) = 14, ஆகவே,

{42 \over 56}={3\cdot 14 \over 4\cdot 14}={3 \over 4}.

மீபொவ-ஐ கணக்கிடுவது தொகு

எண் காரணி முறை தொகு

மீப்பெரு பொது வகுத்திகளை அறிய எண் காரணியைப் (ஓர் எண்னைப் பல எண்களின் பெருக்குத்தொகையாக பகுத்தறியும் முறை) பயன்படுத்தலாம். எடுத்துக்காட்டாக: மீபொவ(18, 84) ஐ அறிய, 18 இன் எண்-காரணிகளை அறிவோம்: 18 = 2 · 3², பிறகு 84 இன் எண்-காரணிகளை அறிவோம்: 84 = 2² · 3 · 7, அப்படி செய்த பிறகு இவ்விரண்டு எண்களின் எண்-காரணிகளிலும் பொதுவாக உள்ள காரணிகளை நோக்கினால் 2 · 3; என்று அறியலாம்; எனவே மீபொவ(18, 84) = 6. வழக்கத்தில் இம்முறை சிறிய எண்களின் மீபொவ-ஐ அறிய மட்டுமே எளிதாக இருக்கும். எண்-காரணிகளை (பெருக்கு எண்களை) அறிய நெடு நேரம் எடுக்கலாம்.

கீழே இன்னொரு முறை, வென் படம் (Venn diagram) என்னும் இன்னொரு முறைப் படி ஒரு எடுத்துக்காட்டு. 48 உம் 180 உம் ஆகிய இரண்டு எண்களுக்கும் இடையே ஆன மீப்பெரு பொது வகுத்தியை அறிவதாகக் கொள்வோம். முதலில் இவ்விரண்டு எண்களுக்குமான எண் காரணிகளைக் கண்டுபிடிப்போம்.

48 = 2 × 2 × 2 × 2 × 3,

180 = 2 × 2 × 3 × 3 × 5.

இவை இரண்டுக்கும் பொதுவாக உள்ளவை: இரண்டு "2"களும் ஒரு "3" உம்:

மீச்சிறு பொது மடங்கு (மீ.பொ.ம. அல்லது பொது மடங்குகளுள் சிறியது - பொ.ம.சி. Least common multiple) = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720

மீப்பெரு பொது வகுத்தி (Greatest common divisor) = 2 × 2 × 3 = 12.

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

யூக்ளிட் படிமுறைத்தீர்வு (Euclidean algorithm) என்பது வகுக்கும் முறையைக் கொண்டு மீப்பெரு பொது வகுத்தியைக் காணும் முறை. எடுத்துக்காட்டாக 84 ஐ 18 ஆல் வகுத்தால் ஈவு 4 என்பதும் மீதி 12 என்பதையும் பெறலாம். அடுத்து அந்த 18 என்னும் எண்ணை மீதியாகிய 12 ஆல் வகுத்தால் கிடைப்பது ஈவு 1, மீதி 6. அடுத்து 12 ஐ மீதியாகிய 6 ஆல் வகுத்தால் கிட்டும் மீதி சுழி (0), ஆகவே மீப்பெரு பொது வகுத்தி (மீபொவ) 6 ஆகும். இதனைக் கணக்குக் குறியீட்டுடன் பொதுப்பட கீழ்க்காணுமாறு சொல்லலாம் [gcd = மீபொவ] :

\operatorname {gcd} (a,0)=a

\operatorname {gcd} (a,b)=\operatorname {gcd} (b,a-b\left\lfloor {a \over b}\right\rfloor ).

யூக்ளிட் முறையில் எழும் ஈவுகள் ஒரு தொடர் பின்னம் (continued fraction) ஒன்றைத் தருவது.

மற்ற முறைகள் தொகு

a யும் b யும் இரண்டும் சுழியாக இல்லை என்றால், அவற்றின் மீப்பெரு பொது வகுத்தியை அவற்றின் மீச்சிறு பொது மடங்கு (least common multiple, lcm) என்னும் எண்ணால் கணிக்க இயலும் (gcd = மீபொவ):

\operatorname {gcd} (a,b)={\frac {a\cdot b}{\operatorname {lcm} (a,b)}}.

எடுத்துக்காட்டாக 12, 18 ஆகிய இரண்டு எண்களின் மீபொவ = 6, இதன் மீச்சிறு மடங்கு 36. இவற்றின் பெருக்குத்தொகை 216 = 6*36. இரண்டு எண்களின் பெருக்குத்தொகையில் இருந்து மீபொவ-ஐ வகுத்துவிட்டால் எஞ்சி இருப்பது மீச்சிறு பொது மடங்குதான்.

a ≥ 1 எனில் ஒற்றைப்படையான எண்களுக்கு கீத் சிலாவின் (Keith Slavin) என்பவர் காட்டிய முற்றொருமை:

\operatorname {gcd} (a,b)=\log _{2}\prod _{k=0}^{a-1}(1+e^{-2i\pi kb/a})

மேலுள்ளதில் b என்னும் எண் சிக்கலெண்ணாக இருந்த பொழுதும் கணக்கிட இயலும் ^[1], மேலும் வுல்ஃவ்காங் இஃழ்ச்றம் (Wolfgang Schramm) காட்டியபடி:

\operatorname {gcd} (a,b)=\sum \limits _{k=1}^{a}{\exp(2\pi ikb/a)}\cdot \sum \limits _{d\left|a\right.}{\frac {c_{d}(k)}{d}}

என்னும் சமன்பாட்டில் எல்லா நேர்ம முழு எண் a வுக்கும் b என்னும் மாறியால் ஆன முழுத்தொகை சார்பியம் (entire function) ஆகும்; இதில் c_d(k) என்பது இராமானுசன் கூட்டு (Ramanujan's sum) ஆகும்.^[2] எல்லா நேர்ம முழு எண் a,b -களுக்கும், மார்சேலோ பொலேட்ஃசி (Marcelo Polezzi) கீழ்க்கண்ட சமன்பாட்டை நிறுவியுள்ளார் ^[3]:

\operatorname {gcd} (a,b)=2\sum _{k=1}^{a-1}\lfloor kb/a\rfloor +a+b-ab

மேலும், a, b ஆகிய எதிர்மமல்லா முழு எண்களுக்கு (non-negative integers), அவை இரண்டுமே சுழியாக இல்லாது இருக்குmenil, டொனால்டு குனுத் (Donald Knuth) கீழ்க்காணும் சுருக்க வடிவை (எளிமைப்படுத்துதலை) நிறுவியுள்ளார்^[4]:

\operatorname {gcd} (2^{a}-1,2^{b}-1)=2^{\operatorname {gcd} (a,b)}-1

எடுத்துக்காட்டாக a = 4 என்றும் b = 6 என்று கொண்டால், 2⁴-1 = 15; அதே போல 2⁶- 1 = 63, ஆகவே 15, 63 ஆகிய இரண்டின் மீபொவ= 3. இந்த மீபொவ-ஐ சிறிய எண்களாகிய a,b ஆகியவற்றின் மீபொவ-வைக் கொண்டே கண்டுபிடிக்கலாம் என்பதே இச்சமன்பாட்டின் முக்கியப் பயன்பாடு. 4, 6 ஆகியவற்றின் மீபொவ = 2. ஆகவே 2² – 1 = 4-1 = 3, இதுவே 15, 63 இன் மீபொவ. மேலுள்ளவாறு (2ⁿ -1) என எழுதக்கூடிய இரண்டு பெரிய ஒற்றைப்படை எண்களின் மீபொவ-ஐ இவ்வகையில் எளிதாகக் கணக்கிடலாம். எடுத்துக்காட்டாக 4095, 262143 ஆகிய இரண்டு எண்களின் மீபொவ = 63 ஆகும். ஆனால் 4095, 262143 ஆகிய இரண்டு எண்களை 2¹² – 1, 2¹⁸ – 1 என்று எழுதலாம் என்று அறிந்தால், மடி எண்களாகிய 12,18 ஆகியவற்றின் மீபொவ = 6 என்பதால் 2⁶ – 1 = 64 – 1= 63 என்பதை 4095, 262143 ஆகிய இரண்டு எண்களின் மீபொவ என எளிதாக அறிந்துகொள்ள உதவும்.

இவற்றையும் பார்க்கவும் தொகு

மீச்சிறு பொது மடங்கு

குறிப்புகள் தொகு

↑ Slavin, Keith R. (2008). "Q-Binomials and the Greatest Common Divisor". Integers Electronic Journal of Combinatorial Number Theory (University of West Georgia, Charles University in Prague) 8: A5. http://www.integers-ejcnt.org/vol8.html. பார்த்த நாள்: 2008-05-26.
↑ Schramm, Wolfgang (2008). "The Fourier transform of functions of the greatest common divisor". Integers Electronic Journal of Combinatorial Number Theory (University of West Georgia, Charles University in Prague) 8: A50. http://www.integers-ejcnt.org/vol8.html. பார்த்த நாள்: 2008-11-25.
↑ Polezzi, Marcelo (1997). "A Geometrical Method for Finding an Explicit Formula for the Greatest Common Divisor". Amer. Math. Monthly (Mathematical Association of America) 104 (5): 445–446. doi:10.2307/2974739. http://www.jstor.org/pss/2974739.
↑ Knuth, Donald E.; R. L. Graham, O. Patashnik (March 1994). Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley. பன்னாட்டுத் தரப்புத்தக எண்:0-201-55802-5.

மேலும் படிக்க தொகு

Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. பன்னாட்டுத் தரப்புத்தக எண் 0-201-89684-2. Section 4.5.2: The Greatest Common Divisor, pp. 333–356.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. பன்னாட்டுத் தரப்புத்தக எண் 0-262-03293-7. Section 31.2: Greatest common divisor, pp. 856–862.
Saunders MacLane and Garrett Birkhoff. A Survey of Modern Algebra, Fourth Edition. MacMillan Publishing Co., 1977. பன்னாட்டுத் தரப்புத்தக எண் 0-02-310070-2. 1–7: "The Euclidean Algorithm."

வெளி இணைப்புகள் தொகு

[1] Slavin, Keith R. (2008). "Q-Binomials and the Greatest Common Divisor". Integers Electronic Journal of Combinatorial Number Theory (University of West Georgia, Charles University in Prague) 8: A5. http://www.integers-ejcnt.org/vol8.html. பார்த்த நாள்: 2008-05-26.

[2] Schramm, Wolfgang (2008). "The Fourier transform of functions of the greatest common divisor". Integers Electronic Journal of Combinatorial Number Theory (University of West Georgia, Charles University in Prague) 8: A50. http://www.integers-ejcnt.org/vol8.html. பார்த்த நாள்: 2008-11-25.

[3] Polezzi, Marcelo (1997). "A Geometrical Method for Finding an Explicit Formula for the Greatest Common Divisor". Amer. Math. Monthly (Mathematical Association of America) 104 (5): 445–446. doi:10.2307/2974739. http://www.jstor.org/pss/2974739.

[4] Knuth, Donald E.; R. L. Graham, O. Patashnik (March 1994). Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley. பன்னாட்டுத் தரப்புத்தக எண்:0-201-55802-5.

[1]

[2]

[3]

[4]