مبرهنة أويلر

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

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

إذا كان n عددا طبيعيا وa أوليا مع n، إذن
a^{\varphi(n)} \equiv 1 \mod n
حيث \varphi(n) الدالة مؤشر أويلر

في ١٧٣٦، قدم أويلر إثباته لمبرهنة فيرما الصغرى، والتي قدمها فيرما دون إثبات.

النظرية تعد تعميماً لنظرية فيرما الصغرى، و يمكن تعميمها إلى مبرهنة كارمايكل.

يمكن استخدام المبرهنة لإيجاد البواقي لإعداد ذات قوى كبيرة ل"n" بسهولة. على سبيل المثال: لإيجاد وحدة الآحاد للعدد 7222 والذي يكافئ 7222 (mod 10)

≡ 74 × 55 + 2 ≡ (74)55 × 72 ≡ 155 × 72 ≡ 49 ≡ 9 (mod 10).

البرهان[عدل]

لتكن {(R = {x1, x2, ..., xφ(n نظام بواقي مصغر (mod n) ولتكن a عدداً صحيحاً أولي نسبياً مع n.

البرهان مبني على أن الضرب بـa يدوّر الباقي xi: بكلمات أخرى إذا كان (axjaxk (mod n فإن j = k.

ما يعني أن المجموعات R و {(aR = {ax1, ax2, ..., axφ(n

بأخذهم (mod n) فإن لهم نفس الباقي ، مايعني أن حاصل ضرب عناصر المجموعة R مساوٍ لـ aR :


\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},

وبالتالي نستطيع التخلص من xi ونحصل على مبرهنة أويلر:



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


راجع أيضاً[عدل]

= المصادر[عدل]