كيف نحسب القاسم المشترك الأكبر؟

المزيد عن القاسم المشترك الأكبر (يُشار إليه أحيانًا باسم العامل المشترك الأكبر) : القاسم المشترك الأكبر (GCD) بين رقمين صحيحين موجبين \(n_1\) و \(n_2\) هو أكبر عدد صحيح يقسم كلاً من \(n_1\) و \(n_2\). عادة ما يكون من السهل العثور عليه عن طريق الفحص (أي تجربة الكثير من الأرقام بطريقة منهجية , حتى نجدها) , لكن هذا صحيح فقط بالنسبة للأعداد الصغيرة. قد يكون حساب GCD للأعداد الكبيرة عن طريق الفحص مملاً أو صعبًا.

لحسن الحظ , هناك طريقة منهجية وسهلة (السعال والسعال) لحساب GCD لرقمين. الطريقة تسير على هذا النحو

• احسب ال التحلل الأولي من \(n_1\) و \(n_2\). من الناحية الرمزية , سيكون لدينا شيء مثل هذا: \[n_1 = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_n^{\alpha_n}\] \[n_2 = q_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_m^{\alpha_m}\]
• ابحث عن قائمة الأعداد الأولية الشائعة في التحليل الأولي المقابل. إذا لم تكن هناك أعداد أولية مشتركة , إذن STOP , فقد وجدت أن GCD = 1. وإلا , دع \(\{r_1, ..., r_k \}\) تكون قائمة \(k\) الأولية الشائعة ودع \(\alpha_{i_l}, \beta_{i_l}\) لـ \(l=1,2,..,k\) الأسس المقابلة الموجودة في التحلل الأولي لـ \(n_1\) و __ XYZ المشترك ___ الأعداد الأولية.
  
  
• يتم حساب GCD على النحو التالي: \[GCD = r_1^{\min\{\alpha_{i_1}, \beta_{i_1}\}} \cdot r_2^{ \min\{\alpha_{i_2}, \beta_{i_2}\}} \cdots r_k^{\min\{\alpha_{i_k}, \beta_{i_k}\}} \]

الطريقة أعلاه تبدو معقدة للغاية ؟؟ ليس صحيحا. دعنا نرى مثالاً: دعونا نحسب GCD لـ \(n_1 = 165\) و \(n_2 = 1575\). دعونا نجد التحلل الأولي لكل من هذه الأرقام (يمكنك استخدام حاسبة التحلل الأولي لدينا)

\[165 = 3 \cdot 5 \cdot 11\] \[1575 = 3^2 \cdot 5^2 \cdot 7\]

مما سبق: ما هو القاسم المشترك بين هذين الرقمين؟ كما نرى , الأعداد الأولية الشائعة هي 3 و 5. بالنظر إلى أسس هذه الأعداد الأولية الشائعة في كل رقم , فإننا ننظر إلى الحد الأدنى بين هذين الرقمين. في هذه الحالة , الحد الأدنى للأس 3 هو 1 , والأس الأدنى لـ 5 هو أيضًا 1. لذلك

\[GCD = 3^1 \cdot 5^1 = 3 \cdot 5 = 15 \]

بصرف النظر عن حاسبة GDC , يمكنك الاختيار من بين مجموعة مختارة من حاسبات الجبر والمحللات .