قضیه اویلر

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

جستارهای وابسته[ویرایش]

منابع[ویرایش]

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

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