ما هي دالة أويلر الكلية؟
دالة أويلر الكلية، ويُرمز لها بالرمز \(\varphi(n)\)، تحسب عدد الأعداد الصحيحة الموجبة من 1 إلى n التي لا تشترك مع n في أي عامل مشترك غير الواحد — أي الأعداد الأولية نسبيًا مع n. على سبيل المثال، \(\varphi(9) = 6\) لأن الأعداد 1 و2 و4 و5 و7 و8 جميعها أولية نسبيًا مع 9. وتُعدّ هذه الدالة من الركائز الأساسية في نظرية الأعداد، كما تظهر بكثرة في علم التشفير، وأشهر تطبيقاتها خوارزمية RSA حيث تحدد \(\varphi(n)\) المعكوس الضربي القياسي (modular inverse) المستخدم في توليد المفاتيح.
كيفية استخدام الحاسبة
أدخل أي عدد صحيح موجب n ثم اضغط على زر الحساب. تقوم الأداة بتحليل n إلى عوامله الأولية المتمايزة وتطبّق الصيغة الضربية لتعيد لك قيمة \(\varphi(n)\) فورًا، إلى جانب قائمة بالعوامل الأولية المتمايزة التي عثرت عليها. وهي تعمل مع الأعداد الصغيرة والكبيرة جدًا حتى مليار.
شرح الصيغة
الطريقة الفعّالة لحساب الدالة الكلية هي الصيغة الضربية:
$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$محسوبة على كل عدد أولي متمايز p يقسم n.
كل ما تحتاجه هو الأعداد الأولية المتمايزة، لا تكراراتها. وكل عامل \(\left(1 - \frac{1}{p}\right)\) يستبعد نسبة الأعداد القابلة للقسمة على هذا العدد الأولي.
مثال محلول
لنأخذ n = 36. تحليله إلى عوامل أولية هو \(2^2 \times 3^2\)، إذًا فالعوامل الأولية المتمايزة هي 2 و3. ومن ثم:
$$\varphi(36) = 36 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 36 \times \frac{1}{2} \times \frac{2}{3} = 36 \times \frac{1}{3} = \mathbf{12}$$إذًا هناك 12 عددًا بالضبط بين 1 و36 تكون أولية نسبيًا مع 36.
أمثلة عملية إضافية
المثال 1: عدد أولي، φ(13)
العدد 13 أولي، لذا عامله الأولي الوحيد هو 13 نفسه:
\(\varphi(13) = 13\left(1-\frac{1}{13}\right) = 13 \cdot \frac{12}{13} = \)12. هذا يتفق مع الاختصار الخاص بالأعداد الأولية \(\varphi(p) = p-1\).
المثال 2: قوة أولية، φ(32)
التحليل: \(32 = 2^5\). العدد الأولي المميز الوحيد هو 2.
\(\varphi(32) = 32\left(1-\frac{1}{2}\right) = 32 \cdot \frac{1}{2} = \)16.
الصيغة المكافئة للقوة الأولية: \(\varphi(p^k) = p^k - p^{k-1}\)، إذن \(\varphi(2^5) = 2^5 - 2^4 = 32 - 16 = 16\). وهذه هي الأعداد الفردية من 1 إلى 31 بالضبط.
المثال 3: ثلاثة أعداد أولية مختلفة أو أكثر، φ(210)
التحليل: \(210 = 2 \cdot 3 \cdot 5 \cdot 7\).
- ابدأ بـ \(210\).
- اضرب في \(1-\frac{1}{2} = \frac{1}{2}\): \(210 \cdot \frac{1}{2} = 105\).
- اضرب في \(1-\frac{1}{3} = \frac{2}{3}\): \(105 \cdot \frac{2}{3} = 70\).
- اضرب في \(1-\frac{1}{5} = \frac{4}{5}\): \(70 \cdot \frac{4}{5} = 56\).
- اضرب في \(1-\frac{1}{7} = \frac{6}{7}\): \(56 \cdot \frac{6}{7} = 48\).
إذن \(\varphi(210) = \)48. لاحظ أن قاعدة الضرب تستخدم كل عدد أولي مختلف مرة واحدة فقط. على سبيل المثال، \(60 = 2^2 \cdot 3 \cdot 5\) يعطي \(60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 16\).
تفسير φ(n) واستخداماتها
- الارتباط بالعدد الأولي: بالنسبة إلى \(n \ge 2\)، يكون \(\varphi(n) = n-1\) إذا وفقط إذا كان \(n\) عددًا أوليًا. كل عدد أصغر من عدد أولي يكون أوليًا معه. إذا كان \(n\) مركبًا، فإن عددًا واحدًا على الأقل أصغر منه يشترك معه في عامل، لذا \(\varphi(n) < n-1\).
- زمرة الوحدات: \(\varphi(n)\) هو عدد عناصر زمرة الوحدات بترديد \(n\)، أي البواقي التي لها معكوس ضربي بترديد \(n\). بالنسبة إلى \(n = 15\) هذه هي 1, 2, 4, 7, 8, 11, 13, 14، أي 8 عناصر.
- مبرهنة أويلر: إذا كان \(\gcd(a, n) = 1\)، فإن \(a^{\varphi(n)} \equiv 1 \pmod{n}\). مثال: \(a = 2\)، \(n = 15\)، \(\varphi(15) = \)8، و\(2^8 = 256 = 17 \cdot 15 + 1 \equiv 1 \pmod{15}\). مبرهنة فيرما الصغرى هي الحالة الخاصة عندما \(n = p\) عددًا أوليًا.
- RSA: عندما \(n = pq\) حيث \(p\) و\(q\) عددان أوليان مختلفان، فإن \(\varphi(n) = (p-1)(q-1)\). مع \(n = 15 = 3 \cdot 5\): \(\varphi(15) = 2 \cdot 4 = 8\). يجب أن يكون الأس العام \(e\) أوليًا مع \(\varphi(n)\)، والأس الخاص \(d\) يحقق \(ed \equiv 1 \pmod{\varphi(n)}\). تستخدم خوارزمية RSA الحقيقية أعدادًا أولية يبلغ طولها مئات الأرقام. من يستطيع تحليل \(n\) إلى عوامله يستطيع حساب \(\varphi(n)\)، ولهذا يعتمد الأمان على صعوبة التحليل.
- النسبة تعتمد فقط على الأعداد الأولية المميزة: \(\dfrac{\varphi(n)}{n} = \prod_{p \mid n}\left(1-\frac{1}{p}\right)\). الأسس لا تهم. على سبيل المثال، للعددين 6 و12 مجموعة الأعداد الأولية نفسها {2, 3}، لذا \(\varphi(6)/6 = 2/6 = 1/3\) و\(\varphi(12)/12 = 4/12 = 1/3\).
الأسئلة الشائعة
ما قيمة \(\varphi(1)\)؟ اصطلاحًا \(\varphi(1) = 1\)، لأن العدد 1 يُعدّ أوليًا نسبيًا مع نفسه.
ما قيمة \(\varphi\) لعدد أولي p؟ لأي عدد أولي p فإن \(\varphi(p) = p - 1\)، لأن كل عدد صحيح من 1 إلى p−1 يكون أوليًا نسبيًا مع p.
هل دالة \(\varphi\) ضربية؟ نعم. إذا كان القاسم المشترك الأكبر \(\gcd(a, b) = 1\) فإن \(\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)\)، وهذا بالضبط هو السبب الذي يجعل الجداء على العوامل الأولية المتمايزة صحيحًا.