قضیه اویلر

قضیه اویلر یا قضیه اولر: فرض کنید m عددی طبیعی و a عددی صحیح باشد و داشته باشیم ۱=(a،m). در این صورت:

${displaystyle a^{phi (m)}equiv 1{pmod {m}}}$

ابتدا باید دستگاه مخفف مانده ها را معرفی کنیم. فرض کنید m عددی طبیعی و A مجموعهای از اعداد صحیح باشد. A را یک دستگاه مخفف ماندهها به پیمانه m می نامند به شرطی که تمام اعضای A نسبت به m اول باشند و هر عدد صحیح که نسبت به m اول است دقیقاً با یکی از اعضای A به پیمانه m همنهشت باشد.

حال فرض کنید ${displaystyle r_{1},r_{2},...,r_{phi (m)},}$ دستگاه مخففی از ماندهها به پیمانه m باشد

چون ۱ = (a،m) پس مجموعهٔ

${displaystyle ar_{1},ar_{2},...,ar_{phi (m)},}$

هم دستگاه مخفف ماندهها به پیمانه m است زیرا اگر i و j وجود داشته باشند که

${displaystyle ar_{i}equiv ar_{j}{pmod {m}}}$

چون ۱ = (a،m) داریم ${displaystyle r_{i}equiv r_{j}{pmod {m}}}$ که خلاف فرض است و ضمناً چون ${displaystyle ar_{1},ar_{2},...,ar_{phi (m)},}$ هم دستگاه مخفف ماندهها به پیمانه m است.بنابرین هر یک از اعداد ${displaystyle r_{1},r_{2},...,r_{phi (m)},}$ دقیقاً با یکی از اعداد ${displaystyle ar_{1},ar_{2},...,ar_{phi (m),}}$ همنهشت است پس

${displaystyle {r_{1}}{r_{2}}{...}{r_{phi (m)},}equiv {ar_{1}}{ar_{2}}{ar_{phi (m)},}{pmod {m}}}$ پس ${displaystyle {r_{1}}{r_{2}}{...}{r_{phi (m)},}equiv {a^{phi (m)},}{r_{1}}{r_{2}}{r_{phi (m)},}{pmod {m}}}$ چون

1=( ${displaystyle {r_{1}}{r_{2}}{...}{r_{phi (m)},},m}$ ) پس

${displaystyle a^{phi (m)}equiv 1{pmod {m}}}$

برچسب: نویسنده: هستی حیدریان تاريخ: چهارشنبه 12 دی 1397 ساعت: 17:17

درباره سایت

آخرین مطالب

امکانات وب

قضیه اویلر

صفحه بندی

آرشیو مطالب

پيوندهای روزانه

لینک دوستان

خبرنامه