دالة أويلر الموجبة

في نظرية الأعداد ، تقوم دالة أويلر بحساب الأعداد الصحيحة الموجبة حتى عدد صحيح معين.${\displaystyle n}$التي تعتبر ذات أولوية نسبية لـ${\displaystyle n}$تُكتب باستخدام الحرف اليوناني فاي كما يلي:${\displaystyle \varphi (n)}$أو${\displaystyle \phi (n)}$ويمكن تسميتها أيضاً بدالة أويلر فاي . بعبارة أخرى، هي عدد الأعداد الصحيحة.${\displaystyle k}$في النطاق${\displaystyle 1\leq k\leq n}$القاسم المشترك الأكبر${\displaystyle \gcd(n,k)}$يساوي 1. ^{[ 2 ] [ 3 ]} الأعداد الصحيحة${\displaystyle k}$يُشار أحيانًا إلى هذا الشكل باسم إجماليات${\displaystyle n}$.

على سبيل المثال، المجموع الكلي لـ${\displaystyle n=9}$الأعداد الستة هي 1 و2 و4 و5 و7 و8. جميعها أولية نسبياً مع 9، لكن الأعداد الثلاثة الأخرى في هذا النطاق، وهي 3 و6 و9، ليست كذلك، لأن${\displaystyle \gcd(9,3)=\gcd(9,6)=3}$و${\displaystyle \gcd(9,9)=9}$. لذلك،${\displaystyle \varphi (9)=6}$كمثال آخر،${\displaystyle \varphi (1)=1}$منذ ذلك الحين${\displaystyle n=1}$العدد الصحيح الوحيد في النطاق من 1 إلى${\displaystyle n}$هو 1 نفسه، و${\displaystyle \gcd(1,1)=1}$.

دالة أويلر هي دالة ضربية ، مما يعني أنه إذا كان عددان${\displaystyle m}$و${\displaystyle n}$إذا كانت أولية نسبياً،${\displaystyle \varphi (mn)=\varphi (m)\varphi (n)}$^{[ 4 ] [ 5 ]} تُعطي هذه الدالة رتبة المجموعة الضربية للأعداد الصحيحة بتردد n ( مجموعة الوحدات في الحلقة ) .${\displaystyle \mathbb {Z} /n\mathbb {Z} }$). ^{[ 6 ]} كما يستخدم أيضًا لتعريف نظام تشفير RSA .

قدّم ليونارد أويلر هذه الدالة عام 1763. ^{[ 7 ] [ 8 ] [ 9 ]} إلا أنه لم يختر آنذاك رمزًا محددًا للدلالة عليها. وفي منشور عام 1784، درس أويلر الدالة بتعمق أكبر، واختار الحرف اليوناني${\displaystyle \pi }$للدلالة على ذلك: كتب${\displaystyle \pi D}$لـ "كثرة الأعداد الأقل من${\displaystyle D}$والتي ليس لها قاسم مشترك معها". ^{[ 10 ]} يختلف هذا التعريف عن التعريف الحالي لدالة التدوير عند${\displaystyle D=1}$لكنها متطابقة فيما عدا ذلك. التدوين القياسي الحالي ^{[ 8 ] [ 11 ]}${\displaystyle \varphi (A)}$يأتي هذا من أطروحة غاوس عام 1801 بعنوان Disquisitiones Arithmeticae ، ^{[ 12 ] [ 13 ]} على الرغم من أن غاوس لم يستخدم أقواسًا حول الحجة وكتب${\displaystyle \varphi A}$لذلك، غالباً ما يطلق عليها دالة أويلر فاي أو ببساطة دالة فاي .

في عام 1879، صاغ جيه جيه سيلفستر مصطلح " الدالة المؤثرة" لهذه الدالة، ^{[ 14 ] [ 15 ]} ولذلك يُشار إليها أيضًا باسم دالة أويلر المؤثرة ، أو دالة أويلر المؤثرة ، أو دالة أويلر المؤثرة . ^{[ 16 ]} تُعد دالة جوردان المؤثرة تعميمًا لدالة أويلر المؤثرة.

المكون المشترك لـ${\displaystyle n}$يُعرَّف بأنه${\displaystyle n-\varphi (n)}$يحسب عدد الأعداد الصحيحة الموجبة الأقل من أو تساوي${\displaystyle n}$التي تشترك في عامل أولي واحد على الأقل مع${\displaystyle n}$.

توجد عدة صيغ لحساب${\displaystyle \varphi (n)}$.

يتم عرض أول 100 قيمة (التسلسل A000010 في OEIS ) في الجدول والرسم البياني أدناه:

φ ( n ) لـ 1 ≤ n ≤ 100

+	1	2	3	4	5	6	7	8	9	10
0	1	1	2	2	4	2	6	4	6	4
10	10	4	12	6	8	8	16	6	18	8
20	12	10	22	8	20	12	18	12	28	8
30	30	16	20	16	24	12	36	18	24	16
40	40	12	42	20	24	22	46	16	42	20
50	32	24	52	18	40	24	36	28	58	16
60	60	30	36	32	48	20	66	32	44	24
70	70	24	72	36	40	36	60	24	78	32
80	54	40	82	24	64	42	56	40	88	24
90	72	44	60	46	72	32	96	42	60	40

في الرسم البياني على اليمين، يمثل الخط العلوي y = n − 1 حدًا أعلى صالحًا لجميع قيم n باستثناء الواحد، ويتحقق فقط إذا كان n عددًا أوليًا. أما الحد الأدنى البسيط فهو${\displaystyle \varphi (n)\geq {\sqrt {n/2}}}$، وهو أمر فضفاض إلى حد ما: في الواقع، الحد الأدنى للرسم البياني يتناسب مع ⁠ n / log log n ⁠ . ^{[ 21 ]}

ينص هذا على أنه إذا كان a و n عددين أوليين فيما بينهما فإن

${\displaystyle a^{\varphi (n)}\equiv 1\mod n.}$

الحالة الخاصة التي يكون فيها n عددًا أوليًا تُعرف باسم نظرية فيرما الصغرى .

ويتبع هذا من نظرية لاغرانج وحقيقة أن φ ( n ) هي رتبة المجموعة الضربية للأعداد الصحيحة modulo n .

يعتمد نظام تشفير RSA على هذه النظرية: فهي تنص على أن معكوس الدالة a ↦ a ^e mod n ، حيث e هو أس التشفير (العام)، هو الدالة b ↦ b ^d mod n ، حيث d هو أس فك التشفير (الخاص)، وهو المعكوس الضربي لـ e modulo φ ( n ) . وبالتالي، فإن صعوبة حساب φ ( n ) دون معرفة تحليل n إلى عوامله الأولية هي صعوبة حساب d : تُعرف هذه المسألة بمشكلة RSA التي يمكن حلها بتحليل n إلى عوامله الأولية . يعرف مالك المفتاح الخاص هذا التحليل، لأن مفتاح RSA الخاص يُنشأ باختيار n كحاصل ضرب عددين أوليين كبيرين (يتم اختيارهما عشوائيًا) p و q . يُفصح عن n فقط للعامة، ونظرًا لصعوبة تحليل الأعداد الكبيرة إلى عواملها الأولية، نضمن عدم معرفة أي شخص آخر لهذا التحليل.

• ${\displaystyle a\mid b\implies \varphi (a)\mid \varphi (b)}$
• ${\displaystyle m\mid \varphi (a^{m}-1)}$
• ${\displaystyle \varphi (mn)=\varphi (m)\varphi (n)\cdot {\frac {d}{\varphi (d)}}\quad {\text{where }}d=\operatorname {gcd} (m,n)}$
  • بخاصة:
• ${\displaystyle \varphi (2m)={\begin{cases}2\varphi (m)&{\text{ if }}m{\text{ is even}}\\\varphi (m)&{\text{ if }}m{\text{ is odd}}\end{cases}}}$
• ${\displaystyle \varphi \left(n^{m}\right)=n^{m-1}\varphi (n)}$
• ${\displaystyle \varphi (\operatorname {lcm} (m,n))\cdot \varphi (\operatorname {gcd} (m,n))=\varphi (m)\cdot \varphi (n)}$

قارن هذا بالصيغة${\textstyle \operatorname {lcm} (m,n)\cdot \operatorname {gcd} (m,n)=m\cdot n}$ (انظر المضاعف المشترك الأصغر ).

• تكون φ ( n ) زوجية عندما يكونn ≥ 3. علاوة على ذلك، إذاكان للعدد n عدد r من العوامل الأولية الفردية المختلفة، ^فإن 2r | φ ( n )
• لأي a > 1 و n > 6 بحيث 4 ∤ n يوجد l ≥ 2 n بحيث l | φ ( a ⁿ − 1) .
• ${\displaystyle {\frac {\varphi (n)}{n}}={\frac {\varphi (\operatorname {rad} (n))}{\operatorname {rad} (n)}}}$

حيث rad( n ) هو الجذر لـ n (ناتج ضرب جميع الأعداد الأولية المختلفة التي تقسم n ).

• ${\displaystyle \sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}}$ ^{[ 22 ]}
• ${\displaystyle \sum _{1\leq k\leq n-1 \atop gcd(k,n)=1}\!\!k={\tfrac {1}{2}}n\varphi (n)\quad {\text{for }}n>1}$
• ${\displaystyle \sum _{k=1}^{n}\varphi (k)={\tfrac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)}$ ( ^{[ 23 ]} المشار إليه في ^{[ 24 ]} )
• ${\displaystyle \sum _{k=1}^{n}\varphi (k)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {1}{3}}\right)}$[ليو (2016)]
• ${\displaystyle \sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor ={\frac {6}{\pi ^{2}}}n+O\left((\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)}$ ^{[ 23 ]}
• ${\displaystyle \sum _{k=1}^{n}{\frac {\varphi (k)}{k^{2}}}={\frac {6}{\pi ^{2}}}\log n+{\frac {6\gamma }{\pi ^{2}}}-{\frac {\zeta '(2)}{\zeta (2)^{2}}}+O\left({\frac {\log n}{n}}\right)}$^{[ 25 ]}
• ${\displaystyle \sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}n-{\frac {\log n}{2}}+O\left((\log n)^{\frac {2}{3}}\right)}$ ^{[ 26 ]}
• ${\displaystyle \sum _{k=1}^{n}{\frac {1}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}\left(\log n+\gamma -\sum _{p{\text{ prime}}}{\frac {\log p}{p^{2}-p+1}}\right)+O\left({\frac {(\log n)^{\frac {2}{3}}}{n}}\right)}$ ^{[ 26 ]} (حيثγهوثابت أويلر-ماسكيروني).

يمكن كتابة سلسلة ديريشليه لـ φ ( n ) بدلالة دالة زيتا لريمان على النحو التالي: ^{[ 28 ]}

${\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}}$

حيث يتقارب الجانب الأيسر لـ${\displaystyle \Re (s)>2}$.

الدالة المولدة لسلسلة لامبرت هي ^{[ 29 ]}

${\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}={\frac {q}{(1-q)^{2}}}}$

والتي تتقارب عندما تكون | q | < 1 .

وقد تم إثبات كليهما من خلال عمليات التلاعب بالمتسلسلات الأولية والصيغ الخاصة بـ φ ( n ) .

بحسب كلمات هاردي ورايت، فإن رتبة φ ( n ) هي "دائماً 'قريب من n '." ^{[ 30 ]}

أولاً ^{[ 31 ]}

${\displaystyle \lim \sup {\frac {\varphi (n)}{n}}=1,}$

لكن عندما يؤول n إلى اللانهاية، ^{[ 32 ]} لكل δ > 0

${\displaystyle {\frac {\varphi (n)}{n^{1-\delta }}}\rightarrow \infty .}$

يمكن إثبات هاتين الصيغتين باستخدام أكثر بقليل من صيغ φ ( n ) ودالة مجموع القواسم σ ( n ) .

في الواقع، أثناء إثبات الصيغة الثانية، المتباينة

${\displaystyle {\frac {6}{\pi ^{2}}}<{\frac {\varphi (n)\sigma (n)}{n^{2}}}<1,}$

صحيح بالنسبة لـ n > 1 ، وقد تم إثبات ذلك.

لدينا أيضًا ^{[ 21 ]}

${\displaystyle \lim \inf {\frac {\varphi (n)}{n}}\log \log n=e^{-\gamma }.}$

هنا γ هو ثابت أويلر ، γ = 0.577215665... لذا e ^γ = 1.7810724... و e ^{− γ} = 0.56145948... .

لا يتطلب إثبات ذلك بالضرورة نظرية الأعداد الأولية . ^{[ 33 ] [ 34 ]} بما أن log log n يؤول إلى اللانهاية، فإن هذه الصيغة تُظهر أن

${\displaystyle \lim \inf {\frac {\varphi (n)}{n}}=0.}$

في الواقع، الأمر أكثر من ذلك. ^{[ 35 ] [ 36 ] [ 37 ]}

${\displaystyle \varphi (n)>{\frac {n}{e^{\gamma }\;\log \log n+{\frac {3}{\log \log n}}}}\quad {\text{for }}n>2}$

و

${\displaystyle \varphi (n)<{\frac {n}{e^{\gamma }\log \log n}}\quad {\text{for infinitely many }}n.}$

أظهر جان لويس نيكولا المتباينة الثانية . يقول ريبنبوم : "إن طريقة البرهان مثيرة للاهتمام، إذ تُعرض المتباينة أولًا بافتراض صحة فرضية ريمان ، ثم بافتراض عكسها." ^{[ 37 ] : 173}

بالنسبة للترتيب المتوسط، لدينا ^{[ 23 ] [ 38 ]}

${\displaystyle \varphi (1)+\varphi (2)+\cdots +\varphi (n)={\frac {3n^{2}}{\pi ^{2}}}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)\quad {\text{as }}n\rightarrow \infty ,}$

بفضل أرنولد والفيش ، تم إثباتها باستخدام تقديرات على المجاميع الأسية من قِبل آي إم فينوغرادوف وإن إم كوروبوف . وبدمج طريقتي فان دير كوربوت وفينوغرادوف، قام إتش كيو ليو (حول دالة أويلر. وقائع الجمعية الملكية في إدنبرة، القسم أ 146 (2016)، العدد 4، 769-775) بتحسين حد الخطأ إلى

${\displaystyle O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {1}{3}}\right)}$

(هذا هو أفضل تقدير معروف حاليًا من هذا النوع). يشير مصطلح "Big O " إلى كمية محدودة بثابت مضروب في دالة n داخل الأقواس (وهي صغيرة مقارنةً بـ n² ⁾ .

يمكن استخدام هذه النتيجة لإثبات ^{[ 39 ]} أن احتمال كون عددين تم اختيارهما عشوائيا أوليين نسبيًا هو 6 / π ² .

في عام 1950 أثبت سوماياجولو ^{[ 40 ] [ 41 ]}

${\displaystyle {\begin{aligned}\lim \inf {\frac {\varphi (n+1)}{\varphi (n)}}&=0\quad {\text{and}}\\[5px]\lim \sup {\frac {\varphi (n+1)}{\varphi (n)}}&=\infty .\end{aligned}}}$

في عام 1954، عزز شينزل وسيربينسكي هذا، وأثبتا ^{[ 40 ] [ 41 ]} أن المجموعة

${\displaystyle \left\{{\frac {\varphi (n+1)}{\varphi (n)}},\;\;n=1,2,\ldots \right\}}$

كثيفة في الأعداد الحقيقية الموجبة. كما أثبتوا ^[ 40 ^{] أن} المجموعة

${\displaystyle \left\{{\frac {\varphi (n)}{n}},\;\;n=1,2,\ldots \right\}}$

كثيفة في الفترة (0،1).

العدد المُوَصِّل هو قيمة لدالة أويلر المُوَصِّلة: أي، قيمة m التي يوجد لها على الأقل قيمة n واحدة تحقق المعادلة φ ( n ) = m . تكافؤ أو تعددية العدد المُوَصِّل m هو عدد حلول هذه المعادلة. ^{[ 42 ]} العدد غير المُوَصِّل هو عدد طبيعي ليس عددًا مُوَصِّلًا. كل عدد فردي أكبر من 1 هو عدد غير مُوَصِّل بشكل بديهي. يوجد أيضًا عدد لا نهائي من الأعداد الزوجية غير المُوَصِّلة، ^{[ 43 ]} وبالفعل، لكل عدد صحيح موجب مضاعف هو عدد زوجي غير مُوَصِّل. ^{[ 44 ]}

الأرقام القليلة الأولى من الدالة هي${\displaystyle 1,2,4,6,8,10,12,16,18,20}$انظر التسلسل A002202 .

عدد أعداد الدوال حتى حد معين x هو

${\displaystyle {\frac {x}{\log x}}e^{{\big (}C+o(1){\big )}(\log \log \log x)^{2}}}$

لثابت C = 0.8178146... . ^{[ 45 ]}

إذا تم حسابها وفقًا للتعددية، فإن عدد أعداد الدوال حتى حد معين x هو

${\displaystyle {\Big \vert }\{n:\varphi (n)\leq x\}{\Big \vert }={\frac {\zeta (2)\zeta (3)}{\zeta (6)}}\cdot x+R(x)}$

حيث يكون حد الخطأ R من رتبة x / ( log x ) k على ^الأكثر لأي قيمة موجبة k . ^{[ 46 ]}

من المعروف أن تعدد m يتجاوز m ^δ مرات لا حصر لها لأي δ < 0.55655 . ^{[ 47 ] [ 48 ]}

• دالة كارمايكل (λ)
• دالة ديديكيند بسي (𝜓)
• دالة القاسم (σ)
• تخمين دافين-شايفر
• تعميمات لنظرية فيرما الصغرى
• عدد مركب للغاية
• المجموعة الضربية للأعداد الصحيحة بتردد n
• رامانوجان سوم
• دالة التجميع (𝛷)

• "دالة الشد" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]
• دالة أويلر فاي ونظرية الباقي الصينية - برهان على أن φ ( n ) دالة ضربية. مؤرشف بتاريخ 28 فبراير 2021 في أرشيف الإنترنت.
• حاسبة دالة أويلر باستخدام جافا سكريبت - حتى 20 رقمًا
• داينيفا، روسيكا، دالة أويلر، موبيوس، ودوال القواسم. مؤرشفة بتاريخ 16 يناير 2021 في أرشيف الإنترنت (Wayback Machine).
• بليتاج، لوميس، بولهيل يلخصون دالة أويلر فاي