عاد اعظم

تعریف: سب سے بڑا صحیح عدد جو دو صحیح اعداد کو پورا تقسیم کرے، ان دو اعداد کا عادِ اعظم کہلاتا ہے۔ انگریزی میں عاداعظم کو ‭ 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 = a q_1 + r_1\,,\, 0 \le r_1 < a, \\ a = r_1 q_2 + r_2 \,,\, 0 \le r_2 < r_1, \\ r_1 = r_2 q_3 + r_3\,,\, 0 \le r_3 < r_3, \\ \vdots \\ r_{n-2} = r_{n-1} q_n + r_n \,,\, 0 \le 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) = x a + y b$

اعداد 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

$\gcd(1050,198) = 10 \times 1050 - 53 \times 198$

اور دیکھو

• ذواضعاف اقل

E=mc2     اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں LTR پڑھیٔے     ریاضی علامات