משפט אוילר

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

משפט אוילר הוא הכללה של המשפט הקטן של פרמה ממספרים ראשוניים למספרים טבעיים כלשהם. המשפט קרוי על שמו של לאונרד אוילר, שהוכיח אותו בשנת 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 xm = r (mod n), Mathematics Magazine, Vol. 46, No. 4 (Sep 1973), pp. 215-217 (pages 215 and 217 are freely available)