نظرية أويلر

في نظرية الأعداد ، تنص نظرية أويلر (المعروفة أيضًا باسم نظرية فيرما-أويلر أو نظرية أويلر ) على أنه إذا كان n و a عددين صحيحين موجبين أوليين فيما بينهما ، فإن${\displaystyle a^{\varphi (n)}}$متطابق مع${\displaystyle 1}$modulo n ، حيث${\displaystyle \varphi }$ يرمز إلى دالة أويلر الموجبة ؛ أي

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

في عام 1736، نشر ليونارد أويلر برهانًا لنظرية فيرما الصغرى ^{[ 1 ]} (التي ذكرها فيرما دون برهان)، وهي عبارة عن تقييد لنظرية أويلر في حالة كون n عددًا أوليًا. لاحقًا، قدم أويلر براهين أخرى للنظرية، وبلغت ذروتها في بحثه المنشور عام 1763، حيث أثبت تعميمًا لها في حالة كون n عددًا غير أولي. ^{[ 2 ]}

وعكس نظرية أويلر صحيح أيضًا: إذا كانت المطابقة المذكورة أعلاه صحيحة، فإن${\displaystyle a}$و${\displaystyle n}$يجب أن يكون عدداً أولياً فيما بينه.

وقد تم تعميم هذه النظرية بشكل أكبر من خلال بعض نظريات كارمايكل .

يمكن استخدام هذه النظرية لتقليل قوى كبيرة بسهولة.${\displaystyle n}$على سبيل المثال، فكّر في إيجاد رقم الآحاد في العدد العشري${\displaystyle 7^{222}}$، أي${\displaystyle 7^{222}{\pmod {10}}}$العددان الصحيحان 7 و10 أوليان فيما بينهما، و${\displaystyle \varphi (10)=4}$إذن، تنص نظرية أويلر على ما يلي:${\displaystyle 7^{4}\equiv 1{\pmod {10}}}$ونحصل${\displaystyle 7^{222}\equiv 7^{4\times 55+2}\equiv (7^{4})^{55}\times 7^{2}\equiv 1^{55}\times 7^{2}\equiv 49\equiv 9{\pmod {10}}}$.

بشكل عام، عند تقليل قوة${\displaystyle a}$modulo${\displaystyle n}$(أين${\displaystyle a}$و${\displaystyle n}$(الأعداد الأولية فيما بينها)، يحتاج المرء إلى العمل بنظام باقي القسمة${\displaystyle \varphi (n)}$في أس${\displaystyle a}$:

لو${\displaystyle x\equiv y{\pmod {\varphi (n)}}}$، ثم${\displaystyle a^{x}\equiv a^{y}{\pmod {n}}}$.

تُشكّل نظرية أويلر أساس نظام التشفير RSA ، الذي يُستخدم على نطاق واسع في اتصالات الإنترنت . في هذا النظام، تُستخدم نظرية أويلر مع n كحاصل ضرب عددين أوليين كبيرين ، ويعتمد أمان النظام على صعوبة تحليل هذا العدد إلى عوامله الأولية.

1. يمكن إثبات نظرية أويلر باستخدام مفاهيم من نظرية الزمر : ^{[ 3 ]} تشكل فئات البواقي بتردد n، التي هي أولية فيما بينها مع n، زمرةً تحت الضرب (انظر مقالة " الزمرة الضربية للأعداد الصحيحة بتردد n" لمزيد من التفاصيل). رتبة هذه الزمرة هي φ ( n ) . تنص نظرية لاغرانج على أن رتبة أي زمرة جزئية من زمرة منتهية تقسم رتبة الزمرة بأكملها، وهي في هذه الحالة φ ( n ) . إذا كان a أي عدد أولي فيما بينه وبين n، ^{فإن a ينتمي إلى إحدى فئات البواقي هذه، وقواه a₁, a₂, ..., aₖ بتردد n تشكل زمرة جزئية من زمرة فئات البواقي، حيث aₖ} ≡ 1 ( mod n ) ^. تنص نظرية ^{لاغرانج} على أن k يجب أن يقسم φ ( n ) ، أي يوجد عدد صحيح M بحيث يكون kM = φ ( n ) . وهذا يستلزم،

${\displaystyle a^{\varphi (n)}=a^{kM}=(a^{k})^{M}\equiv 1^{M}=1{\pmod {n}}.}$

2. يوجد أيضًا برهان مباشر: ^{[ 4 ] [ 5 ]} ليكن R = { x1 , x2 _, ..., xφ _{( n )} } نظامًا مُختزلًا للباقي ( mod n ) _، وليكن a أي عدد صحيح أولي نسبيًا مع n . يعتمد البرهان على الحقيقة الأساسية وهي أن الضرب في a يُبدّل xᵢ _: بعبارة أخرى، إذا كان _axⱼ ≡ axⱼ ₍ mod n )، فإن j = k . (تم إثبات قانون الاختزال هذا في مقالة " المجموعة الضربية للأعداد الصحيحة modulo n" [ ^{6 ] )} _{. أي} أن المجموعتين R و aR = { ax1 _, ax2 _, ..., axφ _{( n )} } ، باعتبارهما مجموعتين من فئات التطابق ( mod n )، متطابقتان (كمجموعتين - يمكن ترتيبهما بترتيبات مختلفة)، لذا فإن حاصل ضرب جميع الأعداد في R متطابق ( mod n ) مع حاصل ضرب جميع الأعداد في aR .

${\displaystyle \prod _{i=1}^{\varphi (n)}x_{i}\equiv \prod _{i=1}^{\varphi (n)}ax_{i}=a^{\varphi (n)}\prod _{i=1}^{\varphi (n)}x_{i}{\pmod {n}},}$وباستخدام قانون الإلغاء لإلغاء كل x _i نحصل على نظرية أويلر:

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

• رقم كارمايكل
• معيار أويلر
• نظرية ويلسون

تُرجمت كتاب "Disquisitiones Arithmeticae" من اللاتينية الشيشرونية لغوس إلى الإنجليزية والألمانية. تتضمن النسخة الألمانية جميع أبحاثه في نظرية الأعداد: جميع براهين التبادلية التربيعية، وتحديد إشارة مجموع غاوس، والبحوث المتعلقة بالتبادلية التربيعية الثنائية، وملاحظات غير منشورة.

• غاوس، كارل فريدريش؛ كلارك، آرثر أ. (مترجم إلى الإنجليزية) (1986)، Disquisitiones Arithemeticae (الطبعة الثانية المصححة) ، نيويورك: سبرينغر ، ISBN 0-387-96254-9
• غاوس، كارل فريدريش؛ ماسر، هـ. (مترجم إلى الألمانية) (1965)، دراسات في الحساب العالي (Disquisitiones Arithemeticae وأوراق أخرى في نظرية الأعداد) (الطبعة الثانية) ، نيويورك: تشيلسي، ISBN 0-8284-0191-8
• هاردي، جي إتش ؛ رايت، إي إم (1980)، مقدمة في نظرية الأعداد (  الطبعة الخامسة)، أكسفورد: مطبعة جامعة أكسفورد ، رقم ISBN 978-0-19-853171-5
• أيرلندا، كينيث؛ روزن، مايكل (1990)، مقدمة كلاسيكية لنظرية الأعداد الحديثة (الطبعة الثانية) ، نيويورك: سبرينغر ، ISBN 0-387-97329-X
• لاندو، إدموند (1966)، نظرية الأعداد الأولية ، نيويورك: تشيلسي

• وايسشتاين، إريك دبليو. "نظرية أويلر للدوال" . عالم الرياضيات .
• نظرية أويلر-فيرما في بلانيت ماث