مبرهنة أويلر

في نظرية الأعداد، مبرهنة أويلر لصاحبها ليونهارد أويلر هي كما يلي :

إذا كان n عدد طبيعي و a أولي مع n، إذن

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

حيث ${\displaystyle{\displaystyle\varphi(n)}}$ الدالة مؤشر أويلر

هذه المبرهنة هي توسيع لمبرهنة فيرما الصغرى.

 البرهان

1. يمكن برهنة مبرهنة اويلر باستخدام مفاهيم من نظرية المجموعات:

لو كان a هو أي number coprime to n حيث a is in one of these residue classes, and its powers a, a², ..., a^k ≡ 1 (mod n) are a subgroup. Lagrange's theorem says k must divide φ(n), i.e. there is an integer M such that kM = φ(n). ولكن حينئذ،

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

2. كما يوجد أيضاً برهان مباشر: Let R = {x₁, x₂, ..., x_φ(n)} be a reduced residue system (mod n) وافرض أن a هو أي integer coprime to n.

${\displaystyle{\displaystyle\prod_{i=1}^{\varphi(n)}x_{i}\equiv\prod_{i=1}^{\varphi(n)}ax_{i}\equiv a^{\varphi(n)}\prod_{i=1}^{\varphi(n)}x_{i}{\pmod{n}},}}$ وباستخدام قانون الشطب لشطب x_is فيعطي مبرهنة اويلر:

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

 انظر أيضاً

• دالة كارمايكل
• معيار اويلر
• مبرهنة فيرما الصغرى
• مبرهنة ولسون

 وصلات خارجية

• Eric W. Weisstein, Euler's Totient Theorem at MathWorld.
• Euler's Theorem at PlanetMath