משפט אוילר

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

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

המשפט

משפט אוילר קובע שאם $\ n$ מספר טבעי, אז לכל $\ a$ זר ל-$\ n$ מתקיים $\ a^{\phi (n)} \equiv 1\pmod{n}$, כלומר, n מחלק את ההפרש $\ a^{\phi(n)}-1$. לדוגמה עבור a=4, מכיוון ש- $\ \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$, קיבלנו אותה קבוצה. נראה זאת:

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

ומאחר ששתי הקבוצות זהות - גם מכפלת איבריהם צריכה להיות שווה: $\ a^k(r_1r_2...r_k)=r_1r_2...r_k\ (\mbox{mod}\ n)$, ומאחר שהמספר $\ r_1r_2...r_k$ הוא מכפלת מספרים זרים ל-$\ n$, וגם הוא זר ל-$\ n$, ניתן לחלק בו את שני צידי המשוואה. כלומר: $\ a^k=1\ (\mbox{mod}\ n)$ ו-$\ k$, על פי הגדרתו, הוא מספר השאריות הזרות ל-$\ n$ בחילוק ל- $\ n$. כלומר - הוא שווה ל-$\ \phi \left(n\right)$.

הרחבה

משפט אוילר הוא מקרה פרטי של המשפט הבא (ג'יימס אלונסו):

יהיו $\ m,n$ מספרים טבעיים. $n=\prod_{i=1}^k p_i^{n_i}$, כאשר $\ p_1, \ldots, p_k$ מספרים ראשוניים שונים ו-$\ n_i >0$ עבור $\ i=1,\ldots,k$. נסמן $\ s_i=\mbox{gcd}(m, p_i^{n_i-1}(p_i-1))$, כאשר $\ \mbox{gcd}(a,b)$ הוא המחלק המשותף המקסימלי של $\ a$ ושל $\ b$, ו-$s=\prod_{i=1}^k s_i$. אזי מספר הפתרונות של המשוואה $x^m \equiv 1 \pmod{n}$ מחושב באופן הבא:

1. אם ה-$\ p_i$ כולם אי-זוגיים, אזי למשוואה $x^m \equiv 1 \pmod{n}$ יש בדיוק $\ s$ פתרונות שונים (מודולו $\ n$).
2. אם אחד ה-$\ p_i$ זוגי, נניח $\ p_1$, ו-$\ n_1$, החזקה שלו בפירוק של $\ n$, שווה 1 או 2, מספר הפתרונות גם כן $\ s$.
3. אם אחד ה-$\ p_i$ זוגי, נניח $\ p_1$, ו-$\ n_1$, החזקה שלו בפירוק של $\ n$, היא לפחות 3, מספר הפתרונות של המשוואה $x^m \equiv 1 \pmod{n}$ (מודולו $\ n$) מחושב באופן הבא:
   1. אם $\ s_1 = 1$ (כלומר $\ m$ איזוגי) או ש-$\ s_1 = 2^{n_1-1}$, מספר הפתרונות הוא $\ s$.
   2. אם $\ 1<s_1 <2^{n_1-1}$, מספר הפתרונות הוא $\ 2s$.

קישורים חיצוניים

• James Alonso, Number of Solutions of the Congruence x^m = r (mod n), Mathematics Magazine, Vol. 46, No. 4 (Sep 1973), pp. 215-217 (pages 215 and 217 are freely available)