حاسبة GCD

أوجد القاسم المشترك الأكبر لأي رقم

القاسم المشترك الأكبر (GCD) - ويسمى أيضًا العامل المشترك الأكبر (GCF) أو العامل المشترك الأعلى (HCF) - هو أكبر رقم يقسم جميع الأرقام المعطاة دون ترك باقي. أدخل رقمين أو أكثر مفصولين بفواصل وسيتم حساب GCD على الفور باستخدام الخوارزمية الإقليدية.

التعريف والأمثلة

• GCD(12, 18) = 6 — لأن 6 هو أكبر رقم يقسم كلا من 12 و18.
• GCD(48, 36, 24) = 12 — أكبر عدد يقسم الثلاثة.
• GCD(7, 13) = 1 — هذه هي coprime (لا يوجد عامل مشترك غير 1).

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

الطريقة الأكثر شهرة لحساب GCD هي الخوارزمية الإقليدية، التي وصفها إقليدس حوالي 300 قبل الميلاد في كتابه العناصر. تنص الخوارزمية على أن GCD(a, b) = GCD(b, a mod b)، وتتكرر حتى b = 0. على سبيل المثال: GCD(48, 36) → GCD(36, 12) → GCD(12, 0) = 12.

تبسيط الكسور

الاستخدام اليومي الأكثر شيوعًا لـ GCD هو تبسيط الكسور إلى أدنى الحدود. لتبسيط 48/72، احسب GCD(48, 72) = 24، ثم اقسم كليهما على 24: 2/3. تم تقليل النتيجة بالكامل لأن البسط والمقام أصبحا الآن أوليين.

التشفير

يعتمد تشفير RSA، وهو الخوارزمية التي تؤمن معظم اتصالات الإنترنت، بشكل أساسي على نظرية الأعداد التي تتضمن أرقام GCD وأرقام coprime. تتطلب خوارزمية إنشاء مفتاح RSA اختيار رقمين أوليين كبيرين، يكونان دائمًا أوليين لبعضهما البعض ولمنتجاتهما.

تقسيم الأشياء إلى مجموعات متساوية

الاستخدام العملي للغاية لـ GCD هو تقسيم المجموعات ذات الأحجام المختلفة إلى أكبر عدد ممكن من المجموعات المتماثلة دون ترك أي شيء. إذا كان لديك 48 تفاحة و36 برتقالة وتريد عمل سلال فواكه متطابقة باستخدام كل الفاكهة دون بقايا طعام، فإن أكبر عدد من السلال التي يمكنك صنعها هو GCD(48, 36) = 12، تحتوي كل منها على 4 تفاحات و3 برتقالات. وينطبق هذا المنطق نفسه على قطع أطوال القماش أو الخشب إلى قطع متساوية، أو ترتيب الكراسي في صفوف متساوية عبر غرف ذات أحجام مختلفة، أو تقسيم الميزانية عبر الأقسام بأكبر أقساط متساوية ممكنة.

الهندسة

في الهندسة الميكانيكية، يحدد عدد الأسنان GCD على ترسين عدد مرات التقاء نفس زوج الأسنان. إذا كان الترس A به 48 سنًا والترس B به 36 سنًا، فإن GCD(48, 36) = 12، مما يعني أن كل 12 سنًا على الترس A مع كل 12 سنًا على الترس B.

كيفية استخدام الآلة الحاسبة

اكتب أرقامك في المربع المفصول بفواصل — رقمين، أو أي عدد تريده. اضغط على "حساب" وسيظهر GCD للمجموعة بأكملها على الفور، جنبًا إلى جنب مع الاختزال الإقليدي خطوة بخطوة حتى تتمكن من رؤية كيفية الوصول إلى الإجابة بالضبط بدلاً من التعامل معها كمربع أسود. يتم التعامل مع إدخال رقم واحد، أو أرقام لا تشترك في أي عامل مشترك يتجاوز 1، بأمان: تقوم الأداة ببساطة بالإبلاغ عن GCD بقيمة 1 في الحالة الأخيرة، مما يؤكد أن الأرقام هي coprime.

لماذا تعتبر الخوارزمية الإقليدية فعالة جدًا؟

قبل طريقة إقليدس، كان العثور على GCD يعني إدراج كل عامل من كل رقم واختيار أكبر عامل مشترك بينهما - وهو أمر عملي بالنسبة للأعداد الصغيرة ولكنه بطيء للغاية بالنسبة للأعداد الكبيرة. بدلًا من ذلك، تقوم الخوارزمية الإقليدية باستبدال الرقم الأكبر بشكل متكرر بباقي عملية القسمة على الرقم الأصغر، مما يؤدي إلى تقليص المشكلة بسرعة. بالنسبة لرقمين من أي حجم واقعي، يتم الانتهاء عادةً في أقل من خمسين خطوة، ولهذا السبب تظل الطريقة القياسية التي يتم تدريسها اليوم والطريقة المضمنة في كل آلة حاسبة ووظيفة جدول بيانات ومكتبة لغة برمجة تقريبًا تحسب GCD.

يمتد إلى أكثر من رقمين

عند إدخال ثلاثة أرقام أو أكثر، لا تحتاج الآلة الحاسبة إلى خوارزمية جديدة - فهي ببساطة تطبق حالة الرقمين بشكل متكرر. GCD لقائمة كاملة يساوي GCD للرقمين الأولين مجتمعين مع الرقم الثالث، وهكذا: GCD(a, b, c) = GCD(GCD(a, b), c). يعمل هذا لأن أي رقم يقسم كل من a وb وc يجب أن يقسم GCD لأي زوج منهم أولاً، لذا فإن تقليل القائمة اثنين في كل مرة لا يفقد المعلومات أبدًا. إنه مثال جيد لكيفية تحجيم كتلة بناء بسيطة - GCD المكونة من رقمين - بشكل نظيف للتعامل مع قائمة طويلة بشكل تعسفي.

أرقام Coprime وما يخبرك به GCD من 1

عندما تشير الآلة الحاسبة إلى أن GCD يساوي 1، فإن الأرقام التي أدخلتها تسمى coprime، أو أولية نسبيًا، مما يعني أنها لا تشترك في أي عامل أكبر من 1 على الرغم من أن كل منها قد يحتوي على العديد من العوامل بشكل فردي. على سبيل المثال، 8 و15 هما كوبريم على الرغم من أن 8 = 2×2×2 و15 = 3×5 - إلا أنهما ببساطة لا يشتركان في نفس وحدات البناء الأولية. تظهر الأولوية المشتركة باستمرار في نظرية الأعداد والتشفير، لأن العديد من الخوارزميات تعتمد على اختيار الأرقام التي تضمن عدم مشاركة البنية المشتركة المخفية.

مثال عملي، خطوة بخطوة

شاهد الخوارزمية الإقليدية أثناء عملها لـ GCD(48, 18). أولاً، 48 = 2×18 + 12، وبالتالي تصبح المشكلة GCD(18, 12). بعد ذلك، 18 = 1×12 + 6، فيصبح GCD(12, 6). وأخيرًا، 12 = 2×6 + 0، وبالتالي يصل الباقي إلى الصفر وآخر باقي غير الصفر، 6، هو GCD. تعمل كل خطوة من خطوات الخوارزمية على تقليص الأرقام المعنية بسرعة، ولهذا السبب بالضبط تنتهي في عدد قليل من الخطوات حتى بالنسبة للأعداد الكبيرة جدًا، على عكس إدراج كل عامل، والذي يتباطأ بسرعة مع نمو الأرقام.

خاصة وفورية

يتم تشغيل جميع الحسابات بالكامل في متصفحك باستخدام الخوارزمية الإقليدية، بحيث تظهر النتيجة فورًا التي تكتبها ولا يتم إرسال أي أرقام تدخلها إلى الخادم أو تسجيلها أو مشاركتها. إنه يعمل دون اتصال بمجرد تحميل الصفحة، ويتم تجاهل كل عملية حسابية بمجرد إغلاق علامة التبويب أو إعادة تحميلها.