آخر تحديث: 2026-07-13

التعريف

دالة أويلر $\varphi(n)$ تَعُدّ كم عددًا صحيحًا من $1$ إلى $n$ يكون أوليًا نسبيًا مع $n$ — أي لا يشترك مع $n$ في أي عامل سوى $1$. ويكون عددان صحيحان أوليَّين نسبيًا عندما يكون قاسمهما المشترك الأكبر $1$.

مثلًا، $\varphi(9) = 6$: من بين $1, 2, \dots, 9$، القيم $1, 2, 4, 5, 7, 8$ أولية نسبيًا مع $9$، بينما $3, 6, 9$ ليست كذلك.

سُمِّيت الدالة باسم ليونهارت أويلر الذي قدَّمها عام 1763. وتُكتب أيضًا $\phi(n)$، وتُعرَف بـدالة phi.

صيغة الجداء

لا حاجة إطلاقًا إلى اختبار كل عدد صحيح حتى $n$. فبمجرد تحليل $n$ إلى عوامله الأولية المتمايزة، تنتج الدالة مباشرة:

$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$

يمتد الجداء على الأعداد الأولية المتمايزة التي تقسم $n$ — ولا تظهر الأُسُس. كل عدد أولي $p$ يزيل الكسر $1/p$ من الأعداد (تلك القابلة للقسمة على $p$)، ولأن الأعداد الأولية تعمل باستقلال، تتضاعف الكسور.

مثال محلول — n = 36. التحليل الأولي هو $36 = 2^2 \cdot 3^2$، فالعوامل الأولية المتمايزة هي $2$ و$3$:

$\varphi(36) = 36\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12$

والأعداد الصحيحة الاثنا عشر الأولية نسبيًا مع $36$ هي $1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35$.

الأعداد الأولية وقواها

حالتان أساسيتان تجعلان الصيغة سهلة الفهم:

• العدد الأولي $p$: كل عدد صحيح من $1$ إلى $p - 1$ أولي نسبيًا مع $p$، لذا $\varphi(p) = p - 1$. مثلًا $\varphi(7) = 6$.
• قوة العدد الأولي $p^k$: الأعداد الوحيدة غير الأولية نسبيًا مع $p^k$ هي مضاعفات $p$، وعددها $p^{k-1}$. ومن ثَمّ

$\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$

فيكون $\varphi(8) = \varphi(2^3) = 2^2(2 - 1) = 4$ و$\varphi(27) = \varphi(3^3) = 3^2(3 - 1) = 18$.

الضربية

الدالة ضربية: كلما كان $m$ و$n$ أوليَّين نسبيًا،

$\varphi(mn) = \varphi(m)\,\varphi(n)$

ولهذا تعمل صيغة الجداء — نكتب $n$ جداءَ قوى أولية، ونطبِّق $\varphi(p^k) = p^{k-1}(p-1)$ على كل منها، ثم نضرب. مثلًا $36 = 4 \cdot 9$ مع $\gcd(4, 9) = 1$، فيكون $\varphi(36) = \varphi(4)\,\varphi(9) = 2 \cdot 6 = 12$.

لاحظ شرط الأولية النسبية: قد يفشل $\varphi(mn) = \varphi(m)\varphi(n)$ إذا اشترك $m$ و$n$ في عامل. مثلًا $\varphi(2 \cdot 2) = \varphi(4) = 2$، لا $\varphi(2)\varphi(2) = 1$.

مبرهنة أويلر

تحكم الدالة الأُسَّ التوافقي. تنص مبرهنة أويلر على أنه إذا كان $\gcd(a, n) = 1$، فإن

$a^{\varphi(n)} \equiv 1 \pmod{n}$

وهذا تعميم لـمبرهنة فيرما الصغرى ($a^{p-1} \equiv 1 \pmod p$ من أجل عدد أولي $p$)، وهي مجرد الحالة الخاصة $n = p$ حيث $\varphi(p) = p - 1$.

مثال. خذ $a = 3$، $n = 10$. هنا $\varphi(10) = 4$، فيكون $3^4 = 81 \equiv 1 \pmod{10}$ — والواقع أن $81$ ينتهي بـ$1$. تتيح المبرهنة اختزال الأُسُس الضخمة بمقياس $\varphi(n)$ قبل الحساب.

التطبيق في RSA

يُبنى تعمية المفتاح العام RSA مباشرة على هذه الدالة. يُكوَّن القياس من عددين أوليين كبيرين $n = p \cdot q$، فينتج

$\varphi(n) = (p - 1)(q - 1)$

ويُختار الأُسّ العام $e$ والأُسّ الخاص $d$ بحيث $e \cdot d \equiv 1 \pmod{\varphi(n)}$. عندئذٍ تضمن مبرهنة أويلر أن فكّ التعمية يعكس التعمية: $(m^e)^d \equiv m \pmod n$.

يقوم الأمان على فجوة: يستطيع أي أحد نشر $n$، لكن حساب $\varphi(n) = (p-1)(q-1)$ يتطلب معرفة $p$ و$q$. واستعادتهما من $n$ وحده هو تحليل شبه-أولي كبير — ويُعتقد أنه غير قابل للحساب عمليًا من أجل أعداد أولية كبيرة بما يكفي. وفي الواقع، معرفة $\varphi(n)$ تكافئ تحليل $n$.

أمثلة محلولة

$n$	التحليل	صيغة الجداء	$\varphi(n)$
$10$	$2 \cdot 5$	$10\,(1 - \tfrac12)(1 - \tfrac15)$	$4$
$12$	$2^2 \cdot 3$	$12\,(1 - \tfrac12)(1 - \tfrac13)$	$4$
$36$	$2^2 \cdot 3^2$	$36\,(1 - \tfrac12)(1 - \tfrac13)$	$12$
$100$	$2^2 \cdot 5^2$	$100\,(1 - \tfrac12)(1 - \tfrac15)$	$40$
$101$	$101$ (أولي)	$101\,(1 - \tfrac{1}{101})$	$100$

حالات خاصة

• $n = 1$: اصطلاحًا $\varphi(1) = 1$. العدد الوحيد في المجال، $1$، أولي نسبيًا مع نفسه.
• $n$ أولي: $\varphi(n) = n - 1$، وهو الأقصى لهذا الحجم — فالأعداد الأولية لها أكبر عدد من البواقي الأولية نسبيًا.
• $n$ زوجي: يزيل العامل $(1 - \tfrac12)$ نصف الأعداد على الأقل، لذا $\varphi(n) \le n/2$.
• المجموع على القواسم: مجموع دوال أويلر لجميع قواسم $n$ يساوي $n$ نفسه: $\sum_{d \mid n} \varphi(d) = n$. من أجل $n = 12$: $\varphi(1) + \varphi(2) + \varphi(3) + \varphi(4) + \varphi(6) + \varphi(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12$.

مرجع سريع

المفهوم	الصيغة
التعريف	$\varphi(n) = \#\{\, k : 1 \le k \le n,\ \gcd(k, n) = 1 \,\}$
صيغة الجداء	$\varphi(n) = n \prod_{p \mid n} (1 - 1/p)$
عدد أولي	$\varphi(p) = p - 1$
قوة عدد أولي	$\varphi(p^k) = p^{k-1}(p - 1)$
ضربية	$\varphi(mn) = \varphi(m)\varphi(n)$ إذا $\gcd(m, n) = 1$
مبرهنة أويلر	$a^{\varphi(n)} \equiv 1 \pmod n$ إذا $\gcd(a, n) = 1$
مجموع القواسم	$\sum_{d \mid n} \varphi(d) = n$

الأسئلة الشائعة (FAQ)

ما هي دالة أويلر (φ)؟

دالة أويلر φ(n) تَعُدّ الأعداد الصحيحة الموجبة حتى n الأولية نسبيًا مع n — أي التي لا تشترك مع n في أي عامل سوى 1. مثلًا φ(9) = 6، لأن 1 و2 و4 و5 و7 و8 كلٌّ منها أولي نسبيًا مع 9، بينما 3 و6 و9 ليست كذلك. واصطلاحًا φ(1) = 1.

كيف تُحسب φ(n)؟

حلِّل n إلى عوامله الأولية المتمايزة p₁ وp₂ و… وpₖ، ثم طبِّق φ(n) = n · ∏(1 − 1/p) على تلك العوامل. من أجل n = 36 = 2² · 3²، فإن φ(36) = 36 · (1 − 1/2) · (1 − 1/3) = 36 · 1/2 · 2/3 = 12. المهم هو العوامل الأولية المتمايزة فقط، لا أُسُسها.

كم قيمة دالة أويلر لعدد أولي؟

من أجل عدد أولي p، كل عدد صحيح من 1 إلى p − 1 أولي نسبيًا مع p، لذا φ(p) = p − 1. ومن أجل قوة أولية pᵏ تعطي الصيغة φ(pᵏ) = pᵏ − pᵏ⁻¹ = pᵏ⁻¹(p − 1). مثلًا φ(7) = 6 وφ(8) = φ(2³) = 8 − 4 = 4.

لماذا تهم دالة أويلر في RSA ومبرهنة أويلر؟

تنص مبرهنة أويلر على أنه إذا كان gcd(a, n) = 1، فإن a^φ(n) ≡ 1 (mod n)، وهي تعميم لمبرهنة فيرما الصغرى. ويعتمد تعمية RSA على ذلك: من أجل قياس n = p·q من عددين أوليين، يكون φ(n) = (p − 1)(q − 1)، ويُختار الأُسّان العام والخاص بحيث e·d ≡ 1 (mod φ(n)). ومعرفة φ(n) تكافئ تحليل n إلى عوامله، وهذا ما يجعل RSA آمنًا.