قضیه اویلر

لئونارد اویلر

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

$a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$

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

برهان

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

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

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

{$a{r}_1,a{r}_2,...,a{r}_{\varphi (m)}$}

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

$a{r}_i\equiv a{r}_j(\mathrm{mod}m)$

چون ۱ = (a،m) داریم $r_i\equiv r_j(\mathrm{mod}m)$ که خلاف فرض است و ضمناً چون ۱=(m ،$r_i$)و ۱ = (a، m) پس ۱=(m ،$a{r}_i$) بنابراین {$a{r}_1,a{r}_2,...,a{r}_{\varphi (m)}$} هم دستگاه مخفف مانده‌ها به پیمانه m است.

بنابرین هر یک از اعداد $r_1,r_2,...,r_{\varphi (m)}$ دقیقاً با یکی از اعداد $a{r}_1,a{r}_2,...,a{r}_{\varphi (m)}$ همنهشت است پس

$r_1{r}_2...r_{\varphi (m)}\equiv a{r}_{1}a{r}_{2}a{r}_{\varphi (m)}(\mathrm{mod}m)$

یعنی

$r_1{r}_2...r_{\varphi (m)}\equiv a^{\varphi (m)}{r}_1{r}_2{r}_{\varphi (m)}(\mathrm{mod}m)$

اما

۱=($r_i,m$)

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

$a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$

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

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

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

منابع

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

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