قضیه اویلر

قضیه اویلر یا قضیه اولر: فرض کنید 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}}$

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

جستارهای وابسته

• یادواره‌های لئونارد اویلر
• عدد اویلر

منابع

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

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