عاد اعظم

سب سے بڑا صحیح عدد جو دو صحیح اعداد کو پورا تقسیم کرے، ان دو اعداد کا عادِ اعظم کہلاتا ہے۔ انگریزی میں عاداعظم کو greatest common divisor (gcd) کہتے ہیں۔ مثال کے طور پر 30 اور 42 کا عاد اعظم 6 ہے، کیونکہ ${\begin{matrix}30=5\times 3\times 2\\42=7\times 3\times 2\\\gcd(30,42)=3\times 2=6\end{matrix}}$

عاد اعظم الخوارزم[ترمیم]

اگرچہ دو صحیح اعداد کا عاد اعظم ان اعداد کے ضربی جُز دیکھ کر معلوم کیا جا سکتا ہے، مگر جب اعداد بڑے ہوں تو ضربی جز نکالنا مشکل ہو جاتا ہے۔ عادِاعظم نکالنے کا ایک تیز طریقہ "تقسیم الخوارزم" کے ذریعے ہے۔ اس الخوارزم کو عموماً یکلڈ کا الخوارزم کہا جاتا ہے۔
یکلڈ الخوارزم: فرض کرو کہ a اور b صحیح اعداد ہیں، $\ a>0$ ۔ تقسیم الخوازم یکے بعد دیگرے استعمال کرو: ${\begin{matrix}b=aq_{1}+r_{1}\,,\,0\leq r_{1}<a,\\a=r_{1}q_{2}+r_{2}\,,\,0\leq r_{2}<r_{1},\\r_{1}=r_{2}q_{3}+r_{3}\,,\,0\leq r_{3}<r_{3},\\\vdots \\r_{n-2}=r_{n-1}q_{n}+r_{n}\,,\,0\leq r_{3}<r_{3},\\r_{n-1}=r_{n}q_{n+1}\end{matrix}}$ اب اگر آخری عدد بچا ہے جو صفر نہیں ہے، تو $\ r_{n}=\gcd(a,b)$ ۔

مثال: ہم 198اور 1050 کا عادِ اعظم نکالتے ہیں: ${\begin{matrix}1050&=198&\times 5&+&60\\&\swarrow &&&\swarrow \\198&=60&\times 3&+&18\\&\swarrow &&&\swarrow \\60&=18&\times 3&+&6\\&\swarrow &&&\swarrow \\18&=6&\times 3&+&0\end{matrix}}$ اس لیے $\ \gcd(198,1050)=6$ ۔

مسلئہ اثباتی[ترمیم]

اگر a اور b کا عاد اعظم $\ \gcd(a,b)$ ہو، تو اس عاد اعظم کو a اور b کے لکیری جوڑ کے طور پر لکھا جا سکتا ہے۔ یعنی ایسے صحیح اعداد x اور y موجود ہوں گے کہ $\ \gcd(a,b)=xa+yb$

اعداد x اور y کو نکالنے کے لیے عاد اعظم الخوارزم کو اُلٹی طرف سے پڑھا جا سکتا ہے۔ اوپر کی مثال ہم الٹی جانب لکھتے ہیں: ${\begin{matrix}6&=&60-18\times 3&&\\&=&60-(198-60\times 3)\times 3&=&-198\times 3+60\times 10\\&=&-198\times 3+(1050-198\times 5)\times 10&=&1050\times 10-198\times 53\end{matrix}}$
گویا x=10 اور y=-53