משפט אוילר

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

משפט אוילר פורסם לראשונה במאמרו של אוילר "Methodus Inveniendi Lineas Curvas Maximi Minive Proprietate Gaudentes", שפורסם בשנת 1744. במאמר זה הציג אוילר את המושג פונקציונלי, שהוא פונקציה שלוקחת פונקציות אחרות כקלט, והוא השתמש במושג זה כדי לגזור את משוואת אוילר-לגראנג'. המשפט היווה תרומה משמעותית לפיתוח החשבון והייתה לו השפעה מתמשכת על תחום המתמטיקה. למשפט אוילר היו גם יישומים רבים בתחומים שונים, כולל פיזיקה, הנדסה וכלכלה, והוא ממשיך להיות בשימוש נרחב עד היום. אחד היישומים הנודעים של המשפט הוא בשיטת ההצפנה הנפוצה הקרויה RSA.

## המשפט

משפט אוילר קובע שאם \ n מספר טבעי, אז לכל \ a זר ל-\ n מתקיים \ a^{\phi (n)} \equiv 1\pmod{n}, כלומר, n מחלק את ההפרש \ a^{\phi(n)}-1. לדוגמה עבור a=4 ו-n=15, מכיוון ש- \ \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\ (\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} מחושב באופן הבא:
# אם ה-\ p_i כולם אי-זוגיים, אזי למשוואה x^m \equiv 1 \pmod{n} יש בדיוק \ s פתרונות שונים (מודולו \ n).
# אם אחד ה-\ p_i זוגי, נניח \ p_1, ו-\ n_1, החזקה שלו בפירוק של \ n, שווה 1 או 2, מספר הפתרונות גם כן \ s.
#אם אחד ה-\ p_i זוגי, נניח \ p_1, ו-\ n_1, החזקה שלו בפירוק של \ n, היא לפחות 3, מספר הפתרונות של המשוואה x^m \equiv 1 \pmod{n} (מודולו \ n) מחושב באופן הבא:
## אם \ s_1 = 1 (כלומר \ m אי זוגי) או ש-\ s_1 = 2^{n_1-1}, מספר הפתרונות הוא \ s.
##אם \ 1, מספר הפתרונות הוא \ 2s.

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

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

אוילר
קטגוריה:הוכחות
קטגוריה:לאונרד אוילר
קטגוריה:חשבון מודולרי