دالة أويلر توتيانت

Core idea

Overview

تحسب دالة أويلر توتيانت، المشار إليها بـ φ(n)، عدد الأعداد الصحيحة الموجبة حتى n التي تكون أولية نسبيًا لـ n. إنها دالة ضربية أساسية في نظرية الأعداد تُستخدم لاستكشاف خصائص الحساب النمطي والمجموعات الدورية.

When to use: استخدم هذه الدالة عند حساب رتبة المجموعة الضربية للأعداد الصحيحة نمطي n. إنها الأداة الأساسية لتطبيق نظرية أويلر في الأسس النمطية أو عند تحديد عدد المولدات في مجموعة دورية من الرتبة n.

Why it matters: هذه المعادلة هي حجر الزاوية الرياضي لخوارزمية تشفير RSA، التي تؤمن الاتصالات الرقمية الحديثة. إنها تسمح بحساب المفاتيح الخاصة عن طريق تحديد دالة توتيانت لحاصل ضرب عددين أوليين كبيرين.

Symbols

Variables

$ϕ$ (n) = Totient Value, n = Input Integer

ϕ (n)

Totient Value

Variable

n

Input Integer

Variable

Walkthrough

Derivation

استنتاج/فهم دالة أويلر للمؤشر

يوضح هذا الاستنتاج كيف يمكن التعبير عن دالة أويلر للمؤشر، والتي تحسب الأعداد الصحيحة الموجبة حتى عدد صحيح معين n والمتناسبة مع n، باستخدام التحليل الأولي لـ n.

n عدد صحيح موجب.
p يمثل عددًا أوليًا.

1

التعريف والخاصية الضربيات:

نبدأ بتعريف دالة أويلر للمؤشر وبيان خاصيتها الضربية الحاسمة، والتي تسمح لنا بتقسيم الحساب للأعداد المركبة إلى حسابات لعواملها الأولية.

Euler’s totient function ϕ (n) counts the positive integers up to n that are relatively prime to n . It is a multiplicative function, meaning if g cd (m, n) = 1, then ϕ (mn) = ϕ (m) ϕ (n) .

2

حالة القوة الأولية:

بالنسبة للقوة الأولية $p^{k}$ ، فإن الأعداد الوحيدة غير المتناسبة معها هي مضاعفاتها من $p$ . طرح هذه من إجمالي $p^{k}$ عدد يعطي الصيغة لـ $ϕ (p^{k})$ .

Consider n = p^{k} for a prime p and integer k \geq 1. The integers not relatively prime to p^{k} are multiples of p : p, 2 p, \dots, p^{k - 1} p . There are p^{k - 1} such multiples up to p^{k} . ϕ (p^{k}) = p^{k} - p^{k - 1} = p^{k} (1 - \frac{1}{p}) .

3

الحالة العامة باستخدام التحليل الأولي:

باستخدام نظرية الحساب الأساسية، يمكن التعبير عن أي عدد صحيح موجب $n$ بشكل فريد كحاصل ضرب قوى أولية. تسمح لنا الخاصية الضربية لـ $ϕ (n)$ بتطبيق صيغة القوة الأولية على كل عامل.

Let the prime factorization of n be n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}} . Due to the multiplicative property, we can write: ϕ (n) = ϕ (p_{1}^{k_{1}}) ϕ (p_{2}^{k_{2}}) \dots ϕ (p_{r}^{k_{r}}) .

4

التعويض والتبسيط:

عن طريق تعويض الصيغة المشتقة لـ $ϕ (p^{k})$ لكل عامل قوة أولية وإعادة ترتيب المصطلحات، نصل إلى صيغة المنتج لدالة أويلر للمؤشر، حيث يتم أخذ المنتج على جميع العوامل الأولية المميزة $p$ لـ $n$ .

Substitute the formula for ϕ (p^{k}) into the expression: ϕ (n) = p_{1}^{k_{1}} (1 - \frac{1}{p _{1}}) \cdot p_{2}^{k_{2}} (1 - \frac{1}{p _{2}}) \dots p_{r}^{k_{r}} (1 - \frac{1}{p _{r}}) ϕ (n) = (p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}) (1 - \frac{1}{p _{1}}) (1 - \frac{1}{p _{2}}) \dots (1 - \frac{1}{p _{r}}) Recognizing that n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}, we get: ϕ (n) = n p ∣ n \prod (1 - \frac{1}{p}) .

Result

Substitute the formula for ϕ (p^{k}) into the expression: ϕ (n) = p_{1}^{k_{1}} (1 - \frac{1}{p _{1}}) \cdot p_{2}^{k_{2}} (1 - \frac{1}{p _{2}}) \dots p_{r}^{k_{r}} (1 - \frac{1}{p _{r}}) ϕ (n) = (p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}) (1 - \frac{1}{p _{1}}) (1 - \frac{1}{p _{2}}) \dots (1 - \frac{1}{p _{r}}) Recognizing that n = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{r}^{k_{r}}, we get: ϕ (n) = n p ∣ n \prod (1 - \frac{1}{p}) .

Source: Rosen, K. H. (2011). Elementary Number Theory and Its Applications (6th ed.). Pearson.

Why it behaves this way

Intuition

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

Term

عدد الأعداد الصحيحة الموجبة الأقل من أو تساوي n والتي هي متناسبة مع n.

يمثل 'كثافة الأعداد الأولية نسبيًا' أو 'الأولية النسبية' للأعداد حتى n.

ϕ

(n) الأعلى يعني أن عددًا أكبر من الأعداد لا تشترك في عوامل أولية مع n.

Term

العدد الصحيح الموجب الذي يتم حساب مؤشره.

الحد الأعلى لنطاق الأعداد الصحيحة قيد النظر؛ 'الكون' من الأعداد من 1 إلى n.

Term

عامل أولي مميز لـ n.

هذه هي اللبنات الأولية الأساسية لـ n، والتي إذا تمت مشاركتها، تمنع الأعداد الأخرى من أن تكون أولية نسبيًا مع n.

Term

نسبة الأعداد حتى n التي لا تقبل القسمة على p.

يعمل هذا العامل على 'إزالة' الأعداد التي تشارك العامل الأولي p مع n، مما يؤدي إلى تصفية الأعداد غير الأولية نسبيًا بناءً على p.

Signs and relationships

(1 - \frac{1}{p}): يمثل الطرح '1 - ...' مبدأ الاستبعاد. من المجموعة الكلية (الممثلة بـ 1)، نسبة الأعداد القابلة للقسمة على عامل أولي p (وهي 1/p)

Free study cues

Insight

Canonical usage

تعمل دالة أويلر الكلية على أعداد صحيحة وتعطي أعدادًا صحيحة، وهي كميات لا بعدية بطبيعتها من الناحية الفيزيائية.

Dimension note

تحسب الدالة عددًا من الأعداد الصحيحة، مما يجعل كلا من المدخلات والمخرجات كميات لا بعدية بطبيعتها. لا تتضمن وحدات أو أبعاد فيزيائية.

One free problem

Practice Problem

يحتاج محلل إلى تحديد عدد الأعداد الصحيحة الأقل من 12 التي لا تشترك في أي عوامل مشتركة مع 12 بخلاف 1. احسب نتيجة دالة توتيانت لهذه القيمة.

Hint: العوامل الأولية لـ 12 هي 2 و 3.

The full worked solution stays in the interactive walkthrough.

Where it shows up

Real-World Context

في سياق تطبيقي، تُستخدم هذه المعادلة لتحويل القياسات إلى قيمة يمكن تفسيرها. تتجلى أهمية النتيجة لأنها تساعد على ربط الحساب بالشكل أو المعدل أو الاحتمالية أو القيد في النموذج. الرموز المحفوظة في الصيغة: \phi.

Study smarter

Tips

إذا كان n أوليًا، فإن φ(n) = n - 1.
حدد العوامل الأولية الفريدة فقط؛ لا تكرر العوامل إذا ظهرت عدة مرات في التحليل.
للقوة الأولية pᵏ، القيمة هي pᵏ - pᵏ⁻¹.
الدالة ضربية: φ(m ×n) = φ(m) ×φ(n) إذا كان m و n أوليين نسبيًا.

Avoid these traps

Common Mistakes

تضمين جميع القواسم بشكل غير صحيح بدلاً من العوامل الأولية الفريدة فقط في صيغة المنتج.
الخلط بين phi(n) وعدد القواسم $τ$ (n).

Keep going

Related Formulas

Common questions

Frequently Asked Questions

يوضح هذا الاستنتاج كيف يمكن التعبير عن دالة أويلر للمؤشر، والتي تحسب الأعداد الصحيحة الموجبة حتى عدد صحيح معين n والمتناسبة مع n، باستخدام التحليل الأولي لـ n.

استخدم هذه الدالة عند حساب رتبة المجموعة الضربية للأعداد الصحيحة نمطي n. إنها الأداة الأساسية لتطبيق نظرية أويلر في الأسس النمطية أو عند تحديد عدد المولدات في مجموعة دورية من الرتبة n.

هذه المعادلة هي حجر الزاوية الرياضي لخوارزمية تشفير RSA، التي تؤمن الاتصالات الرقمية الحديثة. إنها تسمح بحساب المفاتيح الخاصة عن طريق تحديد دالة توتيانت لحاصل ضرب عددين أوليين كبيرين.

تضمين جميع القواسم بشكل غير صحيح بدلاً من العوامل الأولية الفريدة فقط في صيغة المنتج. الخلط بين phi(n) وعدد القواسم \tau(n).

في سياق تطبيقي، تُستخدم هذه المعادلة لتحويل القياسات إلى قيمة يمكن تفسيرها. تتجلى أهمية النتيجة لأنها تساعد على ربط الحساب بالشكل أو المعدل أو الاحتمالية أو القيد في النموذج. الرموز المحفوظة في الصيغة: \phi.

إذا كان n أوليًا، فإن φ(n) = n - 1. حدد العوامل الأولية الفريدة فقط؛ لا تكرر العوامل إذا ظهرت عدة مرات في التحليل. للقوة الأولية pᵏ، القيمة هي pᵏ - pᵏ⁻¹. الدالة ضربية: φ(m ×n) = φ(m) ×φ(n) إذا كان m و n أوليين نسبيًا.

References

Sources

Wikipedia: Euler's totient function
Rosen, Kenneth H. Elementary Number Theory and Its Applications. 6th ed. Pearson, 2011.
A Friendly Introduction to Number Theory by Joseph H. Silverman
Elementary Number Theory and Its Applications by Kenneth H. Rosen
Rosen, K. H. (2011). Elementary Number Theory and Its Applications (6th ed.). Pearson.

Overview

Variables

Derivation

التعريف والخاصية الضربيات:

حالة القوة الأولية:

الحالة العامة باستخدام التحليل الأولي:

التعويض والتبسيط:

Intuition

Insight

Practice Problem

Real-World Context

Tips

Common Mistakes

Related Formulas

Fermat's Little Theorem

Lagrange's Theorem

Frequently Asked Questions

Sources