GCF Calculator – Greatest Common Factor

ما هو العامل المشترك الأعظم (GCF)?

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

مثال: عوامل 24 هي: 1، 2، 3، 4، 6، 8، 12، 24. عوامل 36 هي: 1، 2، 3، 4، 6، 9، 12، 18، 36. العوامل المشتركة هي: 1، 2، 3، 4، 6، 12. الأكبر من هذه هو 12، لذا GCF(24، 36) = 12.

العامل المشترك الأعظم يرتبط بالعدد الأقل الأقل مشترك (LCM) من خلال الهوية الأساسية: GCF(a، b) × LCM(a، b) = a × b. وهذا يعني بمعرفة العامل المشترك الأعظم يمكنك حساب العدد الأقل الأقل مشترك بسرعة، والعكس صحيح. بالنسبة ل 24 و 36: GCF = 12، LCM = 24 × 36/12 = 72.

طرق حساب العامل المشترك الأعظم

هناك ثلاث طرق رئيسية لحساب العامل المشترك الأعظم. لكل منها فوائدها حسب حجم الأعداد المعنية.

طريقة 1: قائمة العوامل

قائمة جميع العوامل لكل عدد، ثم احدد أكبر منها المشترك. هذا يعمل جيدًا للأعداد الصغيرة ولكن يصبح معقدًا للأعداد الكبيرة.

مثال: GCF(18، 24). عوامل 18: 1، 2، 3، 6، 9، 18. عوامل 24: 1، 2، 3، 4، 6، 8، 12، 24. مشترك: 1، 2، 3، 6. GCF = 6.

طريقة 2: التمثيل بالعوامل الأولية

أعبر كل عدد كمنتج من العوامل الأولية، ثم ضرب العوامل الأولية المشتركة (استخدام الأدنى من القوة لكل منها).

مثال: GCF(120، 180). 120 = 2³ × 3 × 5. 180 = 2² × 3² × 5. العوامل الأولية المشتركة: 2² × 3 × 5 = 4 × 3 × 5 = 60. GCF(120، 180) = 60.

طريقة 3: خوارزمية أوروبا

خوارزمية أوروبا هي الطريقة الأكثر كفاءة، خاصة للأعداد الكبيرة. تعتمد على الخاصية التي GCF(a، b) = GCF(b، a mod b). كرر حتى يصبح الباقي 0؛ العدد غير الصفر الأخير هو العامل المشترك الأعظم.

مثال: GCF(252، 105). خطوة 1: 252 = 2 × 105 + 42. خطوة 2: 105 = 2 × 42 + 21. خطوة 3: 42 = 2 × 21 + 0. GCF = 21.

جدول مرجعي للعامل المشترك الأعظم: الأزواج العددية الشائعة

هنا هي قيم GCF للزوجات العددية الشائعة في المشكلات الرياضية والبساطة الفروع:

انتبه إلى أن GCF(a، b) = b، بحيث أن b يُقسم a بشكل متساوي. عندما GCF(a، b) = 1، فإن الأعداد متطابقة - لا يوجد عوامل مشتركة سوى 1. الأعداد المتطابقة مهمة في التشفير، خاصة في التشفير RSA حيث يلزم اختيار أعداد متطابقة لإنشاء المفتاح.

تسهيل الأعداد المتناسبة باستخدام أقل مشترك

الاستخدام الشائع للأقل مشترك هو تسهيل الأعداد المتناسبة إلى أدنى صورة. لتحويل عدد متناسب إلى صيغة أدنى، قسمة الرقم النumerator والزائد denominator على أقل مشترك(a, b).

أمثلة:

• 48/60: أقل مشترك(48, 60) = 12. → 48÷12 / 60÷12 = 4/5 ✓
• 56/84: أقل مشترك(56, 84) = 28. → 56÷28 / 84÷28 = 2/3 ✓
• 75/100: أقل مشترك(75, 100) = 25. → 75÷25 / 100÷25 = 3/4 ✓
• 144/360: أقل مشترك(144, 360) = 72. → 144÷72 / 360÷72 = 2/5 ✓

الأعداد المتناسبة في صيغة أدنى (أقل صورة) عندما يكون أقل مشترك(النسبة، الزائد) = 1. على سبيل المثال، 3/5 هي بالفعل في صيغة أدنى لأن أقل مشترك(3, 5) = 1. لا تكون الأعداد المتناسبة 6/10 في صيغة أدنى لأن أقل مشترك(6, 10) = 2 → 3/5.

في الطبخ، يساعد أقل مشترك على تقليل الوصفات. إذا كانت الوصفة تخدم 24 شخصًا ولكنك تريد تناول 18 شخصًا، تحتاج إلى 18/24 = 3/4 من كل مكون. أقل مشترك(18, 24) = 6، لذا 18/24 → 3/4. ضع كل كميات مضروبة في 3/4.

أقل مشترك في التطبيقات الحياتية

خارج تسهيل الأعداد المتناسبة، ي حل أقل مشترك عدة أنواع من المشكلات العملية:

التوزيع المتساوي: لديك 36 تفاحة و48 برتقالة لتعبئتها في خيام، مع كل خيمة تحتوي على نفس عدد من كل الفاكهة ولا يبقى أي فاكهة. أكبر عدد من الخيام هو أقل مشترك(36, 48) = 12. كل خيمة تحصل على 3 تفاحات و 4 برتقال.

مشكلات الترميز: تريد تلوين 120 سم × 180 سم من الأرض بلاطات مربعة متطابقة، مما يقلل من الفائض. أكبر بلاطة مربعة يمكن استخدامها بشكل مثالي لها طول جانب أقل مشترك(120, 180) = 60 سم. تحتاج إلى (120/60) × (180/60) = 2 × 3 = 6 بلاطات.

التخطيط: حدث A يكرر كل 12 يومًا، حدث B كل 18 يومًا. سيحدثا معًا بعد LCM(12, 18) = 36 يومًا. أقل مشترك(12, 18) = 6 يخبرك بالدورة الوحدة؛ LCM = 12×18/6 = 36.

تشفير: يتطلب تشفير RSA اختيار أعداد أولية كبيرة p و q. المفتاح العام n = p×q و φ(n) = (p-1)(q-1). يجب أن يكون العامل المخفي e آمنًا إذا كان coprime إلى φ(n) - أي، أقل مشترك(e, φ(n)) = 1. يتم التحقق من coprimality باستخدام الخوارزمية الأوروبية.

خوارزمية أقليدس: التاريخ والبرهان

خوارزمية أقليدس، التي وصفها أقليدس في أصوله (كتاب السابع، المقال 2، قبل الميلاد 300)، واحدة من أشهر الخوارزميات في الرياضيات - قبل معظم الرياضيات الحديثة بآلاف السنين. لا تزال تستخدم على نطاق واسع في الحوسبة اليوم، وشهادة على جمالها وفعاليتها.

الخوارزمية: لتحديد أقل القواسم المشتركين (GCF) (a, b) حيث a > b: قسمة a على b، حصل على القسمة q والباقي r. ثم GCF(a, b) = GCF(b, r). كرر حتى r = 0؛ الباقي غير الصفر هو GCF.

لماذا تعمل: إذا كان d يتقسم كلا (a و b)، ثم d يتقسم a - q × b = r. بالعكس، إذا كان d يتقسم كلا (b و r)، ثم d يتقسم b × q + r = a. لذلك مجموعة القواسم المشتركين (a, b) تساوي مجموعة القواسم المشتركين (b, r). يجب أن تكون أقل القواسم المشتركة لهما متساوية.

فعالية: في الحالة الأسوأ (الأعداد الفيبروناسية المتتالية)، تتطلب الخوارزمية O(log(min(a,b))) خطوات. GCF(F(n+1), F(n)) تتطلب خطواتًا exactly n - هذا هو لماذا تعتبر الأعداد الفيبروناسية المتتالية "الحالة الأسوأ" لخوارزمية أقليدس. ل GCF(144, 89): 144 = 1 × 89 + 55; 89 = 1 × 55 + 34; 55 = 1 × 34 + 21; 34 = 1 × 21 + 13; 21 = 1 × 13 + 8; 13 = 1 × 8 + 5; 8 = 1 × 5 + 3; 5 = 1 × 3 + 2; 3 = 1 × 2 + 1; 2 = 2 × 1 + 0. GCF = 1. (10 خطوات، كما هو متوقع من F(12)/F(11).)

GCF vs LCM: الاختلافات والارتباطات الرئيسية

GCF (أقل القواسم المشتركين) وLCM (أقل الأضلاع المشتركة) عمليات متعاكسة. فهم متى استخدام كل منها ضروري لعمليات الأعداد العددية.

لإضافة الأعداد العددية 1/12 + 1/18: حدد LCM(12, 18) = 36. تحويل: 3/36 + 2/36 = 5/36. لتبسيط 12/18: حدد GCF(12, 18) = 6. قسمة: 2/3.

الخوارزمية الأوروبية الممتدة و هوية بيزو

الخوارزمية الأوروبية الممتدة لا تقوم فقط بتحديد الأقل مشترك الأعظم (GCF) (a, b) ولكن أيضاً تحدد الأرقام الصحيحة x و y مثلًا: ax + by = GCF(a, b). وهذه هوية بيزو، و الأرقام x و y تعرفان ببيزو كوэфيسنت. وهذا له تطبيقات حاسمة في حسابات الموديولار والتشفير.

مثال: اكتشف x و y مثلًا: 24x + 36y = GCF(24, 36) = 12. العمل بالعكس من خلال خطوات الخوارزمية الأوروبية: 12 = 24 − 1×12 = 24 − 1×(36 − 1×24) = 2×24 − 1×36. لذلك x = 2، و y = -1. التحقق: 24×2 + 36×(−1) = 48 − 36 = 12 ✓.

الناقص الموديولي (a) يوجد إذا وفقط إذا كان GCF(a, m) = 1. إذا وجد، يمكن العثور عليه باستخدام الخوارزمية الأوروبية الممتدة. على سبيل المثال، العكس من 7 mod 11: GCF(7, 11) = 1 (مستقل)، لذلك يوجد العكس. 7×8 = 56 = 5×11 + 1 ≡ 1 (mod 11)، لذلك 7⁻¹ ≡ 8 (mod 11). وهذا هو الأساس لتشفير RSA و العديد من العمليات التشفيرية.

الأقل مشترك الأعظم (GCF) للنسب والتراتيب

الأقل مشترك الأعظم (GCF) لا يمكن الاستغناء عنه عند العمل مع النسب والتراتيب في سياقات اليومية. يمكن تقليل نسبة مثل 48:64 عن طريق قسمة كلا المقدارين على GCF(48, 64) = 16، مما يعطي النسبة المتساوية 3:4. هذه التقليل يجعل المقارنة أسهل و يظهر العلاقة الأساسية.

في الطهي والبسترة، غالبًا ما تحتاج الوصفات إلى التكبير. إذا كانت الوصفة تتطلب 450g من الدقيق و 300g من السكر، فإن النسبة هي 450:300. GCF(450, 300) = 150. النسبة المبسطة: 3:2. في أي حجم مخزون، استخدم الدقيق والسكر في نسبة 3:2.

تستخدم مقاييس الخريطة النسب. مقياس 1:50,000 يعني 1 وحدة خريطة = 50,000 وحدة حقيقية. إذا أردت تعبير عن قياس 150 سم على الخريطة كمسافة حقيقية 75,000 سم، تقلل 150:75,000. GCF(150, 75000) = 150. النسبة المبسطة: 1:500. لذلك مقياس الخريطة هو 1:500 لهذا القياس.