شرح دالة أويلر

اكتب الأعداد من 1 إلى 10 واشطب كل عدد يشترك مع 10 في قاسم. يبقى أربعة: 1 و3 و7 و9. هذا العدد، ⁦φ(10) = 4⁩، هو دالة أويلر، إحدى أكثر الدوال استخدامًا في نظرية الأعداد، من الكسور والساعات إلى التشفير الذي يحمي المدفوعات عبر الإنترنت.

الأعداد من 1 إلى 30 في شبكة، والثمانية الأولية مع 30 مملوءة، والصيغة ⁦φ(30) = 30 × 1/2 × 2/3 × 4/5 = 8⁩، ورسم لـ ⁦φ(k)⁩ تقع فيه الأعداد الأولية على خط مستقيم
الأعداد من 1 إلى 30 في شبكة، والثمانية الأولية مع 30 مملوءة، والصيغة ⁦φ(30) = 30 × 1/2 × 2/3 × 4/5 = 8⁩، ورسم لـ ⁦φ(k)⁩ تقع فيه الأعداد الأولية على خط مستقيم

عدّ الأعداد الأولية فيما بينها

يكون عددان أوليين فيما بينهما عندما يكون قاسمهما المشترك الأكبر 1. تعدّ ⁦φ(n)⁩ الأعداد k من 1 إلى n التي تحقق ⁦gcd(k, n) = 1⁩: ⁦φ(9) = 6⁩ و⁦φ(10) = 4⁩ و⁦φ(12) = 4⁩ و⁦φ(1) = 1⁩. ويظهر العدد نفسه في مواضع كثيرة. فهو عدد الكسور ⁦k/n⁩ بين 0 و1 التي هي أصلًا في أبسط صورة، وعدد أطوال الخطوات التي تمرّ بعقرب ساعة ذات n ساعة على كل ساعة، وعدد الأعداد k التي لها معكوس بمقياس n، بحيث يكون للمعادلة ⁦k × x ≡ 1 (mod n)⁩ حل.

صيغة الجداء

إذا كانت الأعداد الأولية التي تقسم n هي ⁦p₁, p₂ …⁩، فإن ⁦φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …⁩. والسبب غربال. نصف الأعداد كلها زوجي، لذا يترك حذف مضاعفات 2 النسبة ⁦1 − 1/2⁩؛ ومن الأعداد الباقية يكون واحد من كل ثلاثة مضاعفًا للعدد 3، وهكذا. وبحسب مبرهنة الباقي الصينية تكون الشروط الخاصة بأعداد أولية مختلفة مستقلة، فتُضرب النسب ببساطة. للعدد ⁦100 = 2² × 5²⁩ يعطي ذلك ⁦100 × 1/2 × 4/5 = 40⁩. وتعطي خاصيتان النتيجة نفسها بصورة أخرى: ⁦φ(p^k) = p^(k−1)(p − 1)⁩، و⁦φ(mn) = φ(m) φ(n)⁩ عندما يكون m وn أوليين فيما بينهما، لذا ⁦φ(100) = φ(4) × φ(25) = 2 × 20 = 40⁩.

مبرهنة أويلر

لاحظ فيرما عام 1640 أن ⁦a^(p−1) ≡ 1 (mod p)⁩ لعدد أولي p ولكل a لا يقبل القسمة على p. وأثبت أويلر الصيغة العامة التي نُشرت عام 1763: ⁦a^φ(n) ≡ 1 (mod n)⁩ متى كان ⁦gcd(a, n) = 1⁩. والبرهان قصير. اضرب في a الأعداد الأولية مع n وعددها ⁦φ(n)⁩؛ فتكون الجداءات أولية مع n من جديد ومختلفة كلها بمقياس n، أي إنها الأعداد نفسها بترتيب آخر، وبمقارنة الجداءين يبقى ⁦a^φ(n) ≡ 1⁩. أصغر أسّ يصلح لعدد a معيّن هو رتبته، وهي تقسم ⁦φ(n)⁩ دائمًا؛ وأصغر أسّ يصلح لكل a في آن واحد هو دالة كارمايكل ⁦λ(n)⁩. للعدد ⁦561 = 3 × 11 × 17⁩ يقسم ⁦λ(561) = 80⁩ العدد 560، لذا ⁦a^560 ≡ 1 (mod 561)⁩ لكل a أولي مع 561 مع أن 561 ليس أوليًا. إنه أصغر عدد كارمايكل، وهو السبب في أن اختبار فيرما وحده لا يستطيع إثبات أن عددًا ما أولي.

ليونهارت أويلر في صورة رسمها ياكوب إيمانويل هاندمان. نشر عام 1763 الصيغة العامة لملاحظة فيرما: a^φ(n) ≡ 1 (mod n) عندما يكون a و n أوليين فيما بينهما.
ليونهارت أويلر في صورة رسمها ياكوب إيمانويل هاندمان. نشر عام 1763 الصيغة العامة لملاحظة فيرما: a^φ(n) ≡ 1 (mod n) عندما يكون a و n أوليين فيما بينهما.

مجموع غاوس على القواسم والمتوسط

اجمع ⁦φ(d)⁩ على قواسم n تحصل دائمًا على n من جديد: للعدد 12، ⁦φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12⁩. أثبت غاوس ذلك في كتابه «بحوث حسابية» عام 1801؛ ويظهر ذلك عند اختزال الكسور ⁦1/12, 2/12 … 12/12⁩ وفرزها بحسب مقاماتها. وفي المتوسط تكون ⁦φ(k)⁩ نحو ⁦0.61 k⁩: يقترب متوسط ⁦φ(k)/k⁩ من ⁦6/π² ≈ 0.6079⁩، وهو أيضًا احتمال أن يكون عددان صحيحان عشوائيان أوليين فيما بينهما، ويقترب ⁦φ(1) + … + φ(N)⁩ من ⁦3N²/π²⁩. مع ⁦N = 1,000⁩ يكون المجموع 304,192، مقابل ⁦3N²/π² ≈ 303,964⁩.

كارل فريدريش غاوس في صورة رسمها كريستيان ألبرشت ينسن عام 1840. أدخل رمز التطابق a ≡ b (mod n) في كتابه Disquisitiones Arithmeticae عام 1801.
كارل فريدريش غاوس في صورة رسمها كريستيان ألبرشت ينسن عام 1840. أدخل رمز التطابق a ≡ b (mod n) في كتابه Disquisitiones Arithmeticae عام 1801.

قيم لا تظهر أبدًا

⁦φ(n)⁩ زوجي لكل n بدءًا من 3، لأن الأعداد الأولية مع n تأتي أزواجًا k و⁦n − k⁩. وليس كل عدد زوجي قيمةً أيضًا: 14 و26 و34 و38 و50 هي أولى القيم التي لا تظهر أبدًا، بينما 24 قيمة لعشرة أعداد مختلفة، من 35 إلى 90. والعثور عليها بحث منتهٍ، لأن ⁦p − 1⁩ يجب أن يقسم ⁦φ(n)⁩ لكل عدد أولي p يقسم n. في عام 1907 ادّعى روبرت كارمايكل أنه لا توجد قيمة تؤخذ مرة واحدة بالضبط. كان برهانه خاطئًا، وما زال الادعاء مفتوحًا، وأي استثناء يجب أن يكون أكبر من ⁦10^(10^10)⁩. وسأل د. هـ. ليمر عام 1932 هل يمكن أن تقسم ⁦φ(n)⁩ العدد ⁦n − 1⁩ لعدد n مؤلف؛ ولا يُعرف أي مثال.

دالة أويلر في RSA

يختار RSA عددين أوليين كبيرين p وq وينشر ⁦n = pq⁩ وأسًّا e. وبما أن ⁦φ(n) = (p − 1)(q − 1)⁩، فإن من يستطيع تحليل n يستطيع حساب ⁦φ(n)⁩، ومنها الأسّ الخاص d الذي يحقق ⁦e × d ≡ 1 (mod φ(n))⁩؛ ثم تضمن مبرهنة أويلر أن ⁦(m^e)^d ≡ m (mod n)⁩. في مثال الكتب المدرسية ⁦n = 3233 = 61 × 53⁩ يكون ⁦φ(n) = 3,120⁩ و⁦e = 17⁩ و⁦d = 2,753⁩. وتستخدم تطبيقات كثيرة بدلًا من ذلك ⁦λ(n) = lcm(p − 1, q − 1)⁩، وهي هنا 780، فتعطي ⁦d = 413⁩ الأصغر. وحساب ⁦φ(n)⁩ لمقياس RSA من 600 رقم صعب بقدر تحليله: فمن n و⁦φ(n)⁩ يُستخرج العددان الأوليان بجذر تربيعي واحد.

رون ريفيست وأدي شامير ولين أدليمان (من اليسار إلى اليمين)
رون ريفيست وأدي شامير ولين أدليمان (من اليسار إلى اليمين)

استكشف بنفسك

افتح الحاسبة وأدخل أي n حتى ⁦10^18⁩ لترى ⁦φ(n)⁩ مع عوامله الأولية والصيغة. وحتى 500 تُرسم الأعداد من 1 إلى n، الأولية مع n مملوءة والباقي ملوّن بحسب أصغر عدد أولي تشترك فيه مع n، فتصبح صيغة الجداء غربالًا يمكن عدّه. اختر عددًا a لتتحقق من مبرهنة أويلر، أو انتقل إلى «الرسم» لترى ⁦φ(k)⁩ حتى 100,000 والأعداد الأولية على المستقيم ⁦φ(p) = p − 1⁩، أو إلى «العكس» لتجد كل n يحقق ⁦φ(n) = m⁩.

الأسئلة المتداولة

لماذا ⁦φ(1) = 1⁩؟

لأن ⁦gcd(1, 1) = 1⁩: العدد الوحيد من 1 إلى 1 أولي مع 1. ويُبقي هذا الاصطلاح الصيغ صحيحة أيضًا، مثل مجموع غاوس على قواسم n، الذي يساوي ببساطة ⁦φ(1) = 1⁩ عندما ⁦n = 1⁩.

هل φ هي نفسها دالة عدّ الأعداد الأولية؟

لا. تعدّ ⁦π(n)⁩ الأعداد الأولية حتى n، بينما تعدّ ⁦φ(n)⁩ الأعداد حتى n الأولية مع n. ⁦φ(10) = 4⁩ تعدّ 1 و3 و7 و9، بينما ⁦π(10) = 4⁩ تعدّ 2 و3 و5 و7. وتساويهما هنا مصادفة: ⁦φ(12) = 4⁩، لكن ⁦π(12) = 5⁩.

ما مدى سرعة حساب ⁦φ(n)⁩؟

بسرعة تحليل n إلى عوامله. إذا عُرفت العوامل الأولية تكفي بضع عمليات ضرب؛ ومن دونها لا تُعرف طريقة سريعة، وعلى هذا يعتمد RSA. للأعداد حتى ⁦10^18⁩ يستغرق التحليل أجزاء من الألف من الثانية في المتصفح، أما الأعداد ذات مئات الأرقام فقد يستغرق تحليلها سنوات.

ما الأعداد التي تكون ⁦φ(n)⁩ فيها أصغر ما يمكن مقارنة بـ n؟

الأعداد التي لها عوامل أولية صغيرة كثيرة. ⁦φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)…⁩ تعتمد فقط على الأعداد الأولية التي تقسم n، لا على قواها: لكل قوة للعدد 2 تساوي ⁦1/2⁩ بالضبط، وللعدد ⁦30 = 2 × 3 × 5⁩ تساوي ⁦8/30⁩، أي نحو 27%. وجداء أول 15 عددًا أوليًا، 614,889,782,588,491,410، له ⁦φ(n)/n ≈ 14%⁩، وهي أدنى قيمة بين جميع الأعداد حتى ⁦10^18⁩.

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

افتح حاسبة دالة أويلر