دالة أويلر φ(n) – عدّ الأوليات نسبياً

دالة أويلر تعدّ كم عدداً من 1 إلى n لا يشترك مع n في أي عامل. للعدد 12 = 2²×3: φ(12) = 12×(1−½)×(1−⅓) = 12×½×⅔ = 4 — الأوليون نسبياً 1 و5 و7 و11 وتسردهم الحاسبة. وللقوى الأولية φ(9) = 9−3 = 6 (بحذف مضاعفات 3). والأوليات قصوى: φ(13) = 12 إذ لا شيء تحت 13 يشترك معه. والدالة ضربية على العوامل الأولية نسبياً: φ(10) = φ(2)×φ(5) = 1×4 = 4. تفكك الأداة n وتطبق صيغة الجداء مع عرض كل (1−1/p) وتسرِد الأوليات نسبياً للأعداد الصغيرة وتعرض مبرهنة أويلر: a^φ(n) ≡ 1 (mod n) عندما gcd(a,n)=1 — محرك RSA حيث ed ≡ 1 (mod φ(n)).

1. 1

   أدخل n

   أي عدد صحيح موجب

2. 2

   فكّك

   تُستخرج الأوليات المميزة (12 → 2, 3)

3. 3

   طبّق صيغة الجداء

   n·Π(1−1/p) مع تقييم كل عامل

4. 4

   اسرد الأوليين نسبياً

   الأعداد الصغيرة تعرض المجموعة فعلياً (1, 5, 7, 11)

• 1

  φ(p) = p−1 لكل أولي p

• 2

  صيغة الجداء: φ(12) = 12·(1−½)·(1−⅓) = 4

• 3

  φ ضربية على المدخلات الأولية نسبياً

• حساب φ(pᵏ) كـ pᵏ−1 بدل pᵏ−pᵏ⁻¹

• استخدام كل العوامل مع التكرار — فقط المميزة تدخل الصيغة

• افتراض جمعية φ: فالعلاقة φ(m+n) ≠ φ(m)+φ(n) عموماً

• نسيان φ(1) = 1