மீப்பெரு பொது வகுத்தி
[[கணிதம்|கணிதத்தில்]] '''மீப்பெரு பொது வகுத்தி''' (மீ.பொ.வ) (இலங்கை வழக்கு: '''பொதுக் காரணிகளுள் பெரியது - பொ.கா.பெ'''), ''greatest common divisor'' (gcm), ''greatest common denominator'' (gcd), ''greatest common factor'' (gcf), அல்லது ''highest common factor'' (hcf)) அல்லது '''பொதுச் சினைகளுள் பெரியது''' (பொ.சி.பெ) என்பது [[சுழி]]யாக இல்லாத இரண்டு அல்லது அதற்கும் கூடுதலான [[முழு எண்]]களை மீதம் விழாமல் வகுக்கக்கூடிய மிகப்பெரிய எண் ஆகும். ஓர் எண்ணை மீதமில்லாமல் வகுக்கும் எண்னை ''வகுத்தி'' (இலங்கை வழக்கு: ''காரணி'') என்பர்.
 
 == பொது விளக்கம் ==
 
 ''a'', ''b'' ஆகிய இரண்டு எண்களுக்கு இடையேயான '''மீப்பெரு பொது வகுத்தி''' (மீ.பொ.வ.) என்பதை மீபொவ (''a'',&amp;nbsp;''b'')என்று எழுதிக்காட்டுவது வழக்கம்; எடுத்துக்காட்டாக மீபொவ (12,&amp;nbsp;18)&amp;nbsp;=&amp;nbsp;6, மீபொவ(−4,&amp;nbsp;14)&amp;nbsp;=&amp;nbsp;2. இரண்டு எண்களுக்கு இடையே மீபொவ-ஆக 1 என்னும் எண் மட்டும் இருந்தால், பிற பொது வகுத்திகள் அவ்விரு எண்களுக்கும் இடையே இல்லை என்பதால் அவ்விரு எண்ணையும் ''ஒன்றுக்கு ஓன்று பகா எண்கள்'' (relatively prime அல்லது co-prime) என்று அழைப்பர். இதனை ''ஒப்பீட்டு பகா எண்'' அல்லது ''இடைத்தொடர்புப் பகாத்தனி'' (''relatively prime'') என்றும் கூறுவர். எடுத்துக்காட்டாக 7 ம் 16 உம் ஒன்றுக்கு ஒன்று பகா எண்கள்.
 
 மீப்பெரு பொது வகுத்தி என்னும் கருத்து பின்னங்களை மேலும் சுருக்கமாக எழுதமுடியாத எளிமையான வடிவத்துக்கு மாற்ற உதவுவது. எடுத்துக்காட்டாக மீபொவ(42,&amp;nbsp;56)&amp;nbsp;=&amp;nbsp;14, ஆகவே,
 
 :&lt;math&gt;{42 \over 56}={3 \cdot 14 \over 4 \cdot 14}={3 \over 4}.&lt;/math&gt;
 
 == மீபொவ-ஐ கணக்கிடுவது ==&lt;!-- This section is linked from [[Fundamental theorem of arithmetic]] --&gt;
 
 === எண் காரணி முறை ===
 மீப்பெரு பொது வகுத்திகளை அறிய எண் காரணியைப் (ஓர் எண்னைப் பல எண்களின் பெருக்குத்தொகையாக பகுத்தறியும் முறை) பயன்படுத்தலாம். எடுத்துக்காட்டாக: மீபொவ(18,&amp;nbsp;84) ஐ அறிய, 18 இன் எண்-காரணிகளை அறிவோம்: 18&amp;nbsp;=&amp;nbsp;2&amp;nbsp;·&amp;nbsp;3&lt;sup&gt;2&lt;/sup&gt;, பிறகு 84 இன் எண்-காரணிகளை அறிவோம்: 84&amp;nbsp;=&amp;nbsp;2&lt;sup&gt;2&lt;/sup&gt;&amp;nbsp;·&amp;nbsp;3&amp;nbsp;·&amp;nbsp;7, அப்படி செய்த பிறகு இவ்விரண்டு எண்களின் எண்-காரணிகளிலும் ''பொதுவாக உள்ள'' காரணிகளை நோக்கினால் 2&amp;nbsp;·&amp;nbsp;3; என்று அறியலாம்; எனவே மீபொவ(18,&amp;nbsp;84)&amp;nbsp;=&amp;nbsp;6. வழக்கத்தில் இம்முறை சிறிய எண்களின் மீபொவ-ஐ அறிய மட்டுமே எளிதாக இருக்கும். எண்-காரணிகளை (பெருக்கு எண்களை) அறிய நெடு நேரம் எடுக்கலாம்.
 
 கீழே இன்னொரு முறை, [[வென் படம்]] (Venn diagram) என்னும் இன்னொரு முறைப் படி ஒரு எடுத்துக்காட்டு.  48 உம்&amp;nbsp;180 உம் ஆகிய இரண்டு எண்களுக்கும் இடையே ஆன மீப்பெரு பொது வகுத்தியை அறிவதாகக் கொள்வோம். முதலில் இவ்விரண்டு எண்களுக்குமான எண் காரணிகளைக் கண்டுபிடிப்போம்.
 : 48 = 2 × 2 × 2 × 2 × 3,
 : 180 = 2 × 2 × 3 × 3 × 5.
 
 இவை இரண்டுக்கும் பொதுவாக உள்ளவை: இரண்டு &quot;2&quot;களும் ஒரு &quot;3&quot; உம்:
 
 :[[File:Least common multiple.svg|300px]]
 
 : [[மீச்சிறு பொது மடங்கு]] (மீ.பொ.ம. அல்லது பொது மடங்குகளுள் சிறியது - பொ.ம.சி. ''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 = மீபொவ] :
 
 :&lt;math&gt;\operatorname{gcd}(a,0) = a&lt;/math&gt;
 :&lt;math&gt;\operatorname{gcd}(a,b) = \operatorname{gcd}(b,a - b \left\lfloor {a \over b} \right\rfloor).&lt;/math&gt;
 
 யூக்ளிட் முறையில் எழும் ஈவுகள் ஒரு தொடர் பின்னம் (continued fraction) ஒன்றைத் தருவது.
 
 === மற்ற முறைகள் ===
 
 ''a'' யும் ''b'' யும் இரண்டும் சுழியாக இல்லை என்றால், அவற்றின் மீப்பெரு பொது வகுத்தியை அவற்றின் [[மீச்சிறு பொது மடங்கு]]  என்னும் எண்ணால் கணிக்க இயலும்
 (gcd = மீபொவ):
 
 :&lt;math&gt;\operatorname{gcd}(a,b)=\frac{a\cdot b}{\operatorname{lcm}(a,b)}.&lt;/math&gt;
 
 எடுத்துக்காட்டாக 12, 18 ஆகிய இரண்டு எண்களின் மீபொவ = 6, இதன் மீச்சிறு மடங்கு 36. இவற்றின் பெருக்குத்தொகை 216 = 6*36. இரண்டு எண்களின் பெருக்குத்தொகையில் இருந்து மீபொவ-ஐ வகுத்துவிட்டால் எஞ்சி இருப்பது மீச்சிறு பொது மடங்குதான்.
 
 ''a''&amp;nbsp;≥&amp;nbsp;1 எனில் ஒற்றைப்படையான எண்களுக்கு கீத் சிலாவின் (Keith Slavin) என்பவர் காட்டிய [[முற்றொருமை (கணிதம்)#முற்றொருமை|முற்றொருமை]]:
 
 :&lt;math&gt;\operatorname{gcd}(a,b)=\log_2\prod_{k=0}^{a-1} (1+e^{-2i\pi k b/a})&lt;/math&gt;
 
 மேலுள்ளதில் b என்னும் எண் [[சிக்கலெண்]]ணாக இருந்த பொழுதும் கணக்கிட இயலும் &lt;ref&gt;{{cite journal |last=Slavin |first=Keith R. |title=Q-Binomials and the Greatest Common Divisor |journal=Integers Electronic Journal of Combinatorial Number Theory |volume=8 |pages=A5 |publisher=[[University of West Georgia]], [[Charles University in Prague]] |date=2008 |url=http://www.integers-ejcnt.org/vol8.html |accessdate=2008-05-26}}&lt;/ref&gt;, மேலும் வுல்ஃவ்காங் இஃழ்ச்றம் (Wolfgang Schramm) காட்டியபடி:
 
 :&lt;math&gt;\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}} &lt;/math&gt;
 
 என்னும் சமன்பாட்டில் எல்லா நேர்ம முழு எண் ''a'' வுக்கும் ''b''  என்னும் மாறியால் ஆன முழுத்தொகை சார்பியம் (entire function) ஆகும்; இதில் ''c''&lt;sub&gt;''d''&lt;/sub&gt;(''k'') என்பது [[இராமானுசன் கூட்டு]] (Ramanujan's sum) ஆகும்.&lt;ref&gt;{{cite journal |last=Schramm |first=Wolfgang |title=The Fourier transform of functions of the greatest common divisor |journal=Integers Electronic Journal of Combinatorial Number Theory |volume=8 |pages=A50 |publisher=[[University of West Georgia]], [[Charles University in Prague]] |date=2008 |url=http://www.integers-ejcnt.org/vol8.html |accessdate=2008-11-25}}&lt;/ref&gt; எல்லா நேர்ம முழு எண் ''a'',''b'' -களுக்கும், மார்சேலோ பொலேட்ஃசி (Marcelo Polezzi) கீழ்க்கண்ட சமன்பாட்டை நிறுவியுள்ளார் &lt;ref&gt;{{cite journal |last=Polezzi |first=Marcelo |title=A Geometrical Method for Finding an Explicit Formula for the Greatest Common Divisor |journal=Amer. Math. Monthly |volume=104 |pages=445–446 |publisher=[[Mathematical Association of America]] |date=1997 |url=http://www.jstor.org/pss/2974739 |doi=10.2307/2974739 |issue=5}}&lt;/ref&gt;:
 
 :&lt;math&gt;\operatorname{gcd}(a,b)=2\sum_{k=1}^{a-1} \lfloor k b/a\rfloor+a+b-a b&lt;/math&gt;
 
 மேலும், ''a'', ''b'' ஆகிய எதிர்மமல்லா முழு எண்களுக்கு (non-negative integers), அவை இரண்டுமே சுழியாக இல்லாது இருக்குமெனில், [[டொனால்டு குனுத்]] (Donald Knuth) கீழ்க்காணும் சுருக்க வடிவை (எளிமைப்படுத்துதலை) நிறுவியுள்ளார்&lt;ref&gt;{{cite book |first=Donald E. |last=Knuth|title=[[Concrete Mathematics: A Foundation for Computer Science]] |coauthors=R. L. Graham, O. Patashnik |year=1994 |month=March |publisher=[[Addison-Wesley]] |isbn=0-201-55802-5}}&lt;/ref&gt;:
 
 :&lt;math&gt;\operatorname{gcd}(2^a-1,2^b-1)=2^{\operatorname{gcd}(a,b)}-1&lt;/math&gt;
 
 எடுத்துக்காட்டாக a = 4 என்றும் b = 6 என்று கொண்டால், 2&lt;sup&gt;4&lt;/sup&gt;-1 =  15; அதே போல 2&lt;sup&gt;6&lt;/sup&gt;- 1 = 63, ஆகவே 15, 63 ஆகிய இரண்டின் மீபொவ= 3. இந்த மீபொவ-ஐ சிறிய எண்களாகிய a,b ஆகியவற்றின் மீபொவ-வைக் கொண்டே கண்டுபிடிக்கலாம் என்பதே இச்சமன்பாட்டின் முக்கியப் பயன்பாடு. 4, 6 ஆகியவற்றின் மீபொவ = 2. ஆகவே 2&lt;sup&gt;2&lt;/sup&gt; – 1 = 4-1 = 3, இதுவே 15, 63 இன் மீபொவ. மேலுள்ளவாறு (2&lt;sup&gt;n&lt;/sup&gt; -1) என எழுதக்கூடிய இரண்டு பெரிய ஒற்றைப்படை எண்களின் மீபொவ-ஐ இவ்வகையில் எளிதாகக் கணக்கிடலாம். எடுத்துக்காட்டாக 4095, 262143 ஆகிய இரண்டு எண்களின் மீபொவ = 63 ஆகும். ஆனால் 4095, 262143 ஆகிய இரண்டு எண்களை 2&lt;sup&gt;12&lt;/sup&gt; – 1, 2&lt;sup&gt;18&lt;/sup&gt; – 1 என்று எழுதலாம் என்று அறிந்தால், மடி எண்களாகிய 12,18 ஆகியவற்றின் மீபொவ = 6 என்பதால் 2&lt;sup&gt;6&lt;/sup&gt; – 1 = 64 – 1= 63 என்பதை 4095, 262143 ஆகிய இரண்டு எண்களின் மீபொவ என எளிதாக அறிந்துகொள்ள உதவும்.
 
 == இவற்றையும் பார்க்கவும் ==
 
 * [[மீச்சிறு பொது மடங்கு]]
 
 == குறிப்புகள் ==
 {{reflist}}
 
 == மேலும் படிக்க ==
 * Donald Knuth. ''The Art of Computer Programming'', Volume 2: ''Seminumerical Algorithms'', Third Edition. Addison-Wesley, 1997. {{ISBN|0-201-89684-2}}. Section 4.5.2: The Greatest Common Divisor, pp.&amp;nbsp;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. {{ISBN|0-262-03293-7}}. Section 31.2: Greatest common divisor, pp.&amp;nbsp;856–862.
 * Saunders MacLane and Garrett Birkhoff.  ''A Survey of Modern Algebra'', Fourth Edition.  MacMillan Publishing Co., 1977.  {{ISBN|0-02-310070-2}}.  1–7:  &quot;The Euclidean Algorithm.&quot;
 
 == வெளி இணைப்புகள் ==
 * [http://www.textbooksonline.tn.nic.in/Books/06/Std06-Maths-TM.pdf தமிழ்நாடு ஆறாம் வகுப்புக் கணக்குப் பாடம். பக்கம் 25-29] {{Webarchive|url=https://web.archive.org/web/20100705091255/http://www.textbooksonline.tn.nic.in/Books/06/Std06-Maths-TM.pdf |date=2010-07-05 }}
 * [http://everything2.com/?node_id=482506 greatest common divisor at Everything2.com]
 * [http://www.stepanovpapers.com/gcd.pdf Greatest Common Measure: The Last 2500 Years], by [[Alexander Stepanov]]
 * [http://wims.unice.fr/wims/wims.cgi?module=tool/popup.en&amp;search=gcd Online gcd calculator]
 * [http://www.idomaths.com/hcflcm.php HCF and LCM Calculator]
 * [http://sputsoft.com/2009/10/computing-the-greatest-common-divisor/ Computing the greatest common divisor] {{Webarchive|url=https://web.archive.org/web/20091208032706/http://sputsoft.com/2009/10/computing-the-greatest-common-divisor/ |date=2009-12-08 }}
 * [http://www.calculla.com/eng/greatest_common_divisor Online calculator – displays fractions of given numbers and supports more than 2 input numbers]
 
 [[பகுப்பு:எளிய கணிதம்]]