المجموع والقاسم المشترك الأكبر: كيف تجد كل زوج ممكن؟

إيجاد عددين من مجموعهما والقاسم المشترك لا يضمن زوجًا واحدًا. نختزل المسألة، ونسرد الحلول دون تكرار، ثم نفسر عددها بدالة أويلر. [1][2]

الخلاصة السريعة

اختزل المجموع بالقاسم، وابحث عن جزأين أوليين نسبيًا؛ قد يبقى أكثر من زوج. [1]

• المجهولان a≤b صحيحان موجبان؛ والمجموع S والقاسم G صحيحان موجبان. نطلب a+b=S وgcd(a,b)=G؛ gcd القاسم الأكبر. تبديل العددين لا يضيف حلًا. [1]
• يلزم أن يقسم G المجموع S وأن S≥2G. الشرطان كافيان: ضع N=S/G≥2؛ الزوج (G,G(N−1)) يحقق المطلوب. [1]
• اكتب a=Gu وb=Gv؛ يلزم u+v=N وgcd(u,v)=1. بالجمع والطرح، قواسم u وN−u المشتركة هي قواسم u وN المشتركة. اختبر 1≤u≤⌊N/2⌋ وgcd(u,N)=1، وأعد (Gu,G(N−u)). [1]
• مثال مؤلف: G=5 وS=60 يعطيان N=12. لقيم u=1,2,3,4,5,6، قواسم الأزواج (u,12−u) الكبرى 1,2,3,4,1,6. نقبل u=1 وu=5 فقط؛ كل الحلول (5,55) و(25,35). [1]
• عند N>2، تعد φ(N) القيم الأولية نسبيًا مع N من 1 إلى N−1. يقابل كل u العدد N−u؛ لا يتساويان في زوج مقبول، لأن u=N/2 حينئذ له قاسم u>1. لذلك عدد الأزواج φ(N)/2. في المثال المقبولون 1،5،7،11؛ φ(12)=4، فالعدد 2. [2]
• عند N=2، الحل (G,G) وحده؛ φ(2)=1 فلا تنطبق القسمة على اثنين. مع G=5: S=10 يعطي (5,5)، وS=61 لا يقبل القسمة على G، وS=5<2G؛ الأخيران بلا حل موجب. [1][2]

المراجع

1. MathWorld: القاسم وتكبيره
2. MathWorld: دالة أويلر

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

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