- الأعداد الأولية، على المستقيم φ(p) = p − 1
- أعداد أخرى
- عددك n
حاسبة دالة أويلر
من بين الأعداد من 1 إلى 12، ليس لـ 1 و5 و7 و11 وحدها أي قاسم مشترك مع 12، لذا φ(12) = 4. تعدّ دالة أويلر هذه الأعداد الأولية مع n لأي n. أدخل عددًا حتى 10^18 لتحصل على φ(n) مع عوامله الأولية وصيغة الجداء مكتوبة كاملة، وترى الأعداد من 1 إلى n مع إبراز الأولية منها مع n، وتتحقق من مبرهنة أويلر، وترسم φ(k) لما يصل إلى 100,000 عدد دفعة واحدة، أو تجد كل n له قيمة φ(n) معطاة. أدخل عددًا صحيحًا n حتى 10^18، أو اختر مثالًا محلولًا. تعرض البطاقات φ(n) والعوامل الأولية للعدد n ونسبة الأعداد من 1 إلى n الأولية مع n وعدد القواسم، وتكتب الخطوات صيغة الجداء بأعدادك. حتى n = 500 تُرسم الأعداد من 1 إلى n: الأعداد الأولية مع n مملوءة، والباقي بلون أصغر عدد أولي تشترك فيه مع n. أشر إلى عدد لترى قاسمه المشترك الأكبر gcd مع n، وانقر عليه لاستخدامه بوصفه a في مبرهنة أويلر. يعرض «الرسم» φ(k) لكل k حتى حدّ معيّن؛ انقر على نقطة لفتح ذلك العدد. ويسرد «العكس» كل n يحقق φ(n) = m؛ انقر على أحدها لفتحه.
كيف يعمل
- أدخل عددًا صحيحًا n حتى 10^18، أو اختر مثالًا محلولًا مثل φ(60) أو مقياس RSA أو عدد كارمايكل 561.
- اقرأ φ(n) والعوامل الأولية وصيغة الجداء بأعدادك. وحتى 500، أشر إلى الأعداد من 1 إلى n لترى قاسمها المشترك الأكبر مع n، وانقر على أحدها لتتحقق به من مبرهنة أويلر.
- انتقل إلى «الرسم» لترى φ(k) لكل k حتى 100,000، أو إلى «العكس» لتسرد كل n يحقق φ(n) = m.
كيف تُحسب φ(n)
حلّل n إلى عوامله الأولية واضرب n في (1 − 1/p) لكل عدد أولي p يقسمه. للعدد 60 = 2² × 3 × 5 يعطي ذلك 60 × 1/2 × 2/3 × 4/5 = 16. والشطب يعطي العدد نفسه: من الأعداد الستين 30 زوجية؛ ومن الأعداد الفردية الثلاثين 10 مضاعفات للعدد 3؛ ومن العشرين الباقية 4 مضاعفات للعدد 5، فيبقى 16. ولقوة عدد أولي تكون الصيغة φ(p^k) = p^(k−1)(p − 1)، وتُضرب القيم معًا: φ(60) = 2 × 2 × 4. الجزء الصعب هو التحليل إلى العوامل. تستخدم الحاسبة القسمة التجريبية واختبار ميلر–رابين للأولية وطريقة رو لبولارد، لذا حتى جداء من 18 رقمًا لعددين أوليين من 9 أرقام يستغرق جزءًا من الثانية.
أين تُستخدم دالة أويلر
تعدّ φ(n) الكسور k/n بين 0 و1 التي هي أصلًا في أبسط صورة، وأطوال الخطوات التي تمرّ بعقرب ساعة ذات n ساعة على كل ساعة (1 و5 و7 و11 على ساعة من 12 ساعة)، والأعداد التي لها معكوس بمقياس n. أثبت أويلر أن a^φ(n) ≡ 1 (mod n) لكل a أولي مع n، وعلى ذلك يقوم تشفير RSA: مع n = 3233 = 61 × 53 يكون φ(n) = 60 × 52 = 3,120، وللأسّ العام 17 شريك خاص هو 2,753، لأن 17 × 2,753 = 15 × 3,120 + 1.
الأسئلة المتداولة
ما دالة أويلر؟
φ(n) هي عدد الأعداد الصحيحة من 1 إلى n التي ليس لها مع n قاسم مشترك غير 1. φ(9) = 6، لأن 1 و2 و4 و5 و7 و8 أولية مع 9، بينما تشترك 3 و6 و9 في العامل 3. وبالاصطلاح φ(1) = 1. درس أويلر هذه الدالة في ستينيات القرن الثامن عشر؛ وأعطاها غاوس الرمز φ عام 1801، ومنحها جيمس جوزيف سيلفستر اسمها الإنجليزي totient عام 1879.
ما قيمة φ لعدد أولي؟
p − 1، لأن كل عدد من 1 إلى p − 1 أولي مع العدد الأولي p، لذا φ(97) = 96. ولقوة عدد أولي φ(p^k) = p^k − p^(k−1)، لأن مضاعفات p وحدها تشترك معها في قاسم: φ(81) = 81 − 27 = 54.
ماذا تقول مبرهنة أويلر؟
إذا كان a وn أوليين فيما بينهما، فإن باقي قسمة a^φ(n) على n هو 1. مع n = 60 وa = 7: φ(60) = 16، و7^16 ≡ 1 (mod 60). ومبرهنة فيرما الصغرى هي حالة n أولي. وكثيرًا ما يكفي أسّ أصغر: 7^4 = 2,401 = 40 × 60 + 1. وأصغر أسّ يصلح لكل a أولي مع n هو دالة كارمايكل λ(n)، وقيمتها للعدد 60 هي 4.
هل يمكن أن يكون لعددين القيمة نفسها لدالة أويلر؟
نعم، وعادةً تكون لعدة أعداد: φ(n) = 24 عندما n = 35, 39, 45, 52, 56, 70, 72, 78, 84, 90. بعض الأعداد الزوجية لا تكون أبدًا قيمة للدالة φ، وأصغرها 14، ولا يكون أي عدد فردي أكبر من 1 قيمة لها، لأن φ(n) زوجي بدءًا من n = 3. ادّعى روبرت كارمايكل عام 1907 أنه لا توجد قيمة تؤخذ مرة واحدة بالضبط. ولم يُثبت ذلك حتى الآن، وبيّن كيفن فورد عام 1998 أن أي استثناء يجب أن يكون أكبر من 10^(10^10).
ما أكبر عدد يمكنني إدخاله؟
أي عدد صحيح حتى 10^18. تحلّله الحاسبة إلى عوامله بحساب صحيح دقيق في متصفحك، لذا تأتي φ(10^18) = 4 × 10^17 وφ(999,999,866,000,004,473) = 999,999,864,000,004,608 صحيحة حتى آخر رقم. تُرسم الأعداد من 1 إلى n حتى 500، ويصل الرسم إلى 100,000، ويعمل العكس للقيم حتى 10^10.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
الانتقال إلى المحرر