قضیه اویلر

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

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

که ${\phi(m)}\,$ برابر تعداد اعداد کوچکتر از m است که نسبت به آن اول هستند (همان تعداد اعضاء دستگاه مخفف مانده ها)

برهان

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

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

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

{$ar_1, ar_2, ..., ar_{\phi(m)}\,$}

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

$ar_i\equiv ar_j\pmod{m}$

چون ۱ = (a،m) داریم $r_i\equiv r_j\pmod{m}$ که خلاف فرض است و ضمنا چون ۱=(m ،$r_i$)و ۱ = (a، m) پس ۱=(m ،$ar_i$) بنابراین {$ar_1, ar_2, ..., ar_{\phi(m)}\,$} هم دستگاه مخفف مانده‌ها به پیمانه m است.

بنابرین هر یک از اعداد $r_1,r_2,...,r_{\phi(m)}\,$ دقیقا با یکی از اعداد $ar_1,ar_2,...,ar_{\phi(m)\,}$ همنهشت است پس

${r_1}{r_2}{...}{r_{\phi(m)}\,}\equiv {ar_1}{ar_2}{ar_{\phi(m)}\,}\pmod{m}$

یعنی

${r_1}{r_2}{...}{r_{\phi(m)}\,}\equiv {a^{\phi(m)}\,}{r_1}{r_2}{r_{\phi(m)}\,}\pmod{m}$

اما

۱=($r_i,m$)

بنابرین ۱=(${r_1}{r_2}{...}{r_{\phi(m)}\,},m$) در نتیجه می‌توانیم $r_i$ها را از دو طرف معادله ساده کنیم پس داریم

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

یکی از نتایج قضیه اویلر قضیه فرما است.

منابع

مبانی نظریه اعداد، مریم میرزاخانی، رویا بهشتی زواره، انتشارات فاطمی ۱۳۸۲

ویلیام .ج.لوک مبانی نظریه اعداد، ترجمه مهمد تقی دیبایی انتشارت مبتکران ۱۳۷۲