دالة أويلر φ(n) تعد القيم الأولية نسبيًا مع n الصحيح الموجب. [1]
الخلاصة السريعة
عد الصحيح الموجب k≤n إذا كان القاسم المشترك الأكبر gcd(k,n)=1. [1]
ما الذي يدخل العد؟
أوليان نسبيًا يعني gcd=1. قواسم 25 هي 1 و5 و25؛ مشتركها مع قواسم 36 هو 1 وحده. [1]
الرسم يعرض المقبول. نستبعد العدد الأولي 2 لأن gcd(2,36)=2. [1]
استخدم العوامل المتميزة
التحليل 36=2²×3² يعطي العاملين المتميزين 2 و3. لذلك φ(36)=36×(1−1/2)×(1−1/3)=12. [2]
الأسس جزء من العدد 36؛ لكنها لا تعني تكرار عامل النسبة. كررنا كل نسبة مرتين خطأً فحصلنا على 36×(1/2)²×(2/3)²=4 بدل 12. [2]
صحح تقاطع المضاعفات
نعد حتى 36: مضاعفات 2 عددها 18، ومضاعفات 3 عددها 12. التقاطع مضاعفات 6 وعددها 6؛ طرحناه مرتين. [1] [2]
نعيد عدد التقاطع مرة: 36−18−12+6=12؛ دون إعادة قبول مضاعفات 6. [1] [2]
حد النطاق
للحالة n=1 نقبل 1 وحدها، فيكون φ(1)=1. لا عوامل أولية لها. [1]
المثال لا يقيس أداء برنامج. [1]
المراجع
- NIST DLMF: تعريف دالة أويلر
- CP Algorithms: صيغة دالة أويلر
- موضوع: الأعداد الأولية — مفردات
- موضوع: العامل المشترك — مفردات
أُعدّ هذا المقال بمساعدة الذكاء الاصطناعي، وخضع لمراجعة ذاتية بالأداة نفسها. لا يُنسب إلى مراجع بشري أو خبير مستقل. منهجية المحتوى.