مبرهنة أويلر

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

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

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

حيث $\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). ولكن حينئذ،

$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.

$\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 فيعطي مبرهنة اويلر:

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

 انظر أيضاً

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

 وصلات خارجية

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