مبرهنة أويلر

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

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

إذا كان 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},<br />

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



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


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

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