حاسبة GCD و LCM

GCD، ويُسمَّى أيضًا العامل المشترك الأكبر (GCF)، هو أكبر عدد صحيح موجب يقسم كلا العددين دون باقٍ. على سبيل المثال، العامل المشترك الأكبر ل 12 و18 هو 6 لأن 6 هو أكبر عدد يقسم كلا العددين بالتساوي.

LCM هو أصغر عدد صحيح موجب يقبل القسمة على كلا العددين. على سبيل المثال، حاصل جمع العددين 4 و6 يساوي 12 لأن 12 هو أصغر عدد يقبل القسمة على كل من العددين 4 و6.

لأي عددين صحيحين موجبين a وb: GCD(a,b) × LCM(a,b) = a × b. تتيح لك هذه العلاقة حساب LCM إذا كنت تعرف GCD، أو العكس.

يعد GCD ضروريًا لتبسيط الكسور (قسمة البسط والمقام على GCD الخاص بهما)، وحل معادلات ديوفانتين وتطبيقات مختلفة في التشفير وعلوم الكمبيوتر.

لتبسيط الكسر، اقسم كلًا من البسط والمقام على إجمالي عدد الكسرين. على سبيل المثال، لتبسيط 24/36: أوجد GCD(24،36) = 12، ثم اقسم كلاهما على 12 لتحصل على 2/3. هذا يعطيك الكسر في أدنى حدوده.

يُستخدم LCM عند مزامنة الأحداث المتكررة. تتضمن الأمثلة على ذلك إيجاد وقت وصول حافلتين في نفس الوقت، أو تحديد المقامات المشتركة لجمع الكسور، أو جدولة المهام المتكررة، أو التخطيط عند محاذاة التروس ذات أعداد الأسنان المختلفة.

قسِّم كل عدد إلى عوامل أولية، ثم اضرب العوامل المشتركة مع أقل القوى. على سبيل المثال، 48 = 2^4 × 3 و18 = 2 × 3^2. العوامل المشتركة هي 2^1 و3^1، لذا فإن إجمالي الناتج المحلي = 2 × 3 = 6.

قسِّم كل عدد إلى عوامل أولية، ثم اضرب جميع العوامل باستخدام أعلى القوى. بالنسبة للعدد 12 = 2^2 × 3 و18 = 2 × 3^2، خذ 2^2 و3^2، إذن LCM = 4 × 9 = 36.

تعمل الخوارزمية الإقليدية على إيجاد GCD بكفاءة عن طريق القسمة المتكررة وأخذ الباقي. بالنسبة إلى GCD(48،18): 48÷18= 2 الباقي 12، 18÷12= 1 الباقي 6، 12÷6= 2 الباقي 0. عندما يكون الباقي 0، يكون المقسوم عليه الأخير (6) هو إجمالي الناتج العام.