משפט אוילר

מתוך ויקיפדיה, האנציקלופדיה החופשית

משפט אוילר הוא הכללה של המשפט הקטן של פרמה ממספרים ראשוניים למספרים טבעיים כלשהם. המשפט קרוי על שמו של לאונרד אוילר, שהוכיח אותו בשנת 1736.

משפט אוילר הוא משפט בסיסי בתורת המספרים, ונעשה בו שימוש רב. אחד היישומים הנודעים של המשפט הוא בשיטת ההצפנה הנפוצה הקרויה RSA.

[עריכה] המשפט

משפט אוילר קובע שאם n מספר טבעי, אז לכל a זר ל-n מתקיים $\ a^{\phi (n)} \equiv 1\pmod{n}$ , כלומר, n מחלק את ההפרש $\ a^{\phi(n)}-1$ . לדוגמה, מכיוון ש- $\ \phi(15)=8$ , המשפט מנבא ש-15 מחלק את $\ 4^{8}-1=65535$ .

בנוסחה זו, $\phi \left(n\right)$ (קרי: "פִי של n") היא פונקציית אוילר של n, השווה למספרם של המספרים הזרים ל-n וקטנים ממנו.

משפט אוילר אינו נותן את התוצאה הטובה ביותר האפשרית. לדוגמה, כל מספר זר ל- 240 מקיים $\ x^4\equiv 1 \pmod{240}$ , בעוד ש- $\ \phi(240)=64$ . את החזקה הקטנה ביותר שתבטיח התנהגות כזו מסמנים ב- $\ \lambda(n)$ , והיא שווה לאקספוננט של חבורת אוילר ה-n-ית. בעוד שפונקציית אוילר של $\ n = p_1^{s_1}\dots p_k^{s_k}$ מתקבלת מהכפלת כל המספרים $\ p_i^{s_i-1}(p_i-1)$ , הפונקציה $\ \lambda$ שווה לכפולה המשותפת המינימלית של כל המספרים האלה (לאחר שהגורם $\ 2^{s-1}$ מוחלף ב- $\ 2^{s-2}$ , אם $\ 2 \leq s$ ).

[עריכה] הוכחת המשפט

המשפט נובע מיד מן העובדה שקבוצת המספרים הזרים ל-n מהווה חבורה (חבורת אוילר של n) ביחס לכפל ולקיחת השארית בחלוקה ל-n. הגודל של חבורה זו הוא $\ \phi(n)$ , ולכן כל איבר בחבורה מקיים $\ a^{\phi(n)}=1$ (משפט לגראנז').

להלן הוכחה ישירה. על-פי הגדרת הפונקציה, $\ \phi \left(n\right)$ הוא מספר השאריות הזרות ל-n היכולות להתקבל מחילוק ב-n. נסמן קבוצה זו כך:

$\ \{r_1,r_2...r_k\}$

כעת נכפיל את כל איברי הקבוצה ב-a:

$\ \{ar_1,ar_2...ar_k\}$

על פי החשבון המודולרי, בבסיס n, קיבלנו אותה קבוצה. נראה זאת:

כל איבר בקבוצה החדשה הוא שארית בחילוק ל-n, מאחר שהוא תוצאה של חישוב מודולרי בבסיס n.
כל איבר בקבוצה החדשה זר ל-n, מאחר שהוא מכפלת שני מספרים זרים ל-n.
אין בקבוצה החדשה שני איברים שווים. הוכחה: נניח בשלילה $\ ar_x=ar_y\ (mod\ n)$ . מאחר ש- $\ a$ זר ל- $\ n$ , ניתן לחלק את שני צידי המשוואה ב- $\ a$ . כלומר: $\ r_x=r_y\ (mod\ n)$ - מה שמוביל אותנו לסתירה.