حاسبة القاسم المشترك والمضاعف المشترك

احسب القاسم المشترك الأكبر والمضاعف المشترك الأصغر مع خطوات الخوارزمية الإقليدية.

ما هي حاسبة القاسم المشترك والمضاعف المشترك؟

القاسم المشترك الأكبر (ق.م.أ) والمضاعف المشترك الأصغر (م.م.أ) هما من أهم المفاهيم في نظرية الأعداد الأولية، بتطبيقات تتراوح من تبسيط الكسور في المرحلة المتوسطة إلى خوارزميات التشفير التي تؤمن الإنترنت.

خوارزمية إقليدس، التي وصفها إقليدس حوالي عام 300 قبل الميلاد، هي واحدة من أقدم الخوارزميات وأكثرها كفاءة في الرياضيات. تحسب القاسم المشترك الأكبر في O(log(min(a,b))) خطوة، وتنتهي بسرعة حتى للأعداد الكبيرة جدًا. تطبق الخوارزمية المتطابقة: ق.م.أ(a, b) = ق.م.أ(b, a mod b) مرارًا حتى يصبح الباقي صفرًا.

تعرض هذه الحاسبة خوارزمية إقليدس كاملة خطوة بخطوة لعددين، وتحسب أيضًا القاسم المشترك الأكبر والمضاعف المشترك الأصغر لقوائم من أعداد متعددة باستخدام التعميم: ق.م.أ(a, b, c) = ق.م.أ(ق.م.أ(a, b), c).

الصيغة

خوارزمية إقليدس:

ق.م.أ(a, b) = ق.م.أ(b, a mod b) حتى b = 0

المضاعف المشترك الأصغر من القاسم المشترك الأكبر:

م.م.أ(a, b) = |a × b| / ق.م.أ(a, b)

لأعداد متعددة:

ق.م.أ(a, b, c) = ق.م.أ(ق.م.أ(a, b), c)

م.م.أ(a, b, c) = م.م.أ(م.م.أ(a, b), c)

كيفية الحساب

أدخل عددين صحيحين موجبين a و b.
طبّق القسمة الصحيحة: a = q×b + r.
استبدل a بـ b و b بـ r. كرر حتى r = 0.
آخر باقٍ غير صفري هو القاسم المشترك الأكبر.
احسب م.م.أ = |a × b| / ق.م.أ باستخدام المتطابقة الأساسية.
استخدم وضع الأعداد المتعددة لثلاثة أعداد أو أكثر.

مثال

جد ق.م.أ(48, 18): 48 = 2×18 + 12 → 18 = 1×12 + 6 → 12 = 2×6 + 0. ق.م.أ = 6. م.م.أ = |48×18|/6 = 864/6 = 144. تحقق: 144/48 = 3 ✓، 144/18 = 8 ✓.

شرح المصطلحات الأساسية

ق.م.أ: أكبر عدد صحيح يقسم كلا العددين بدون باقٍ
م.م.أ: أصغر عدد صحيح موجب يقبل القسمة على كلا العددين
أوليان نسبيًا: عددان قاسمهما المشترك الأكبر = 1، لا يشتركان في أي عوامل أولية
خوارزمية إقليدس: خوارزمية قديمة لحساب القاسم المشترك الأكبر بالقسمة المتكررة
عملية المودولو: a mod b هو الباقي عند قسمة a على b
قابلية القسمة: a يقسم b إذا كان b/a بدون باقٍ

حالات الاستخدام الشائعة

تبسيط الكسور: اختزل a/b بقسمة كلٍ منهما على ق.م.أ(a, b)
جمع الكسور ذات المقامات المختلفة: جد م.م.أ للمقامات
الجدولة: إيجاد موعد تلاقي حدثين دوريين
توليد مفاتيح RSA: التحقق من أن الأس e أولي نسبيًا مع φ(n)
مسائل نسبة التروس في الهندسة الميكانيكية
تصميم أنماط البلاط: إيجاد أصغر وحدة متكررة

الأسئلة الشائعة

ما هو القاسم المشترك الأكبر (ق.م.أ) وكيف يُحسب؟

القاسم المشترك الأكبر (ق.م.أ) هو أكبر عدد صحيح موجب يقسم كلاً من a و b بدون باقٍ. تحسبه خوارزمية إقليدس بكفاءة: استبدل (a, b) بـ (b, a mod b) مرارًا حتى يصبح b = 0. آخر قيمة غير صفرية هي القاسم المشترك الأكبر.

ما هو المضاعف المشترك الأصغر (م.م.أ) وما استخداماته؟

المضاعف المشترك الأصغر (م.م.أ) هو أصغر عدد صحيح موجب يقبل القسمة على كلٍ من a و b. يُستخدم في جمع الكسور ذات المقامات المختلفة، مسائل الجدولة، ونظرية الموسيقى.

ما العلاقة بين القاسم المشترك الأكبر والمضاعف المشترك الأصغر؟

ق.م.أ(a, b) × م.م.أ(a, b) = |a × b|. بمجرد معرفة القاسم المشترك الأكبر، يكون المضاعف المشترك الأصغر ببساطة |a × b| / ق.م.أ(a, b). هذه الطريقة أكثر كفاءة من سرد المضاعفات.

ماذا يعني أن عددين أوليان نسبيًا؟

يكون عددان أوليين نسبيًا إذا كان قاسمهما المشترك الأكبر يساوي 1 — أي لا يشتركان في أي عوامل أولية مشتركة. الأولية النسبية أساسية في الحساب النمطي، التشفير، ونظرية الباقي الصينية.