הצגת המקור של הדף "משפט אוילר"

{{פירוש נוסף|נוכחי=משפט אוילר מתחום תורת המספרים}}
'''משפט אוילר''' הוא [[הכללה (מתמטיקה)|הכללה]] של [[המשפט הקטן של פרמה]] מ[[מספר ראשוני|מספרים ראשוניים]] ל[[מספר טבעי|מספרים טבעיים]] כלשהם. ה[[משפט (מתמטיקה)|משפט]] קרוי על שמו של [[לאונרד אוילר]].

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

==המשפט==

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

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

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

==הוכחת המשפט==

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

להלן הוכחה ישירה. על-פי הגדרת הפונקציה, <math>\ \phi \left(n\right)</math> הוא מספר ה'''שאריות''' הזרות ל-<math>\ n</math> היכולות להתקבל מחילוק ב-<math>\ n</math>. נסמן קבוצה זו כך: <math>\ \{r_1,r_2...r_k\}</math> כעת נכפיל את כל איברי הקבוצה ב-<math>\ a</math>. נקבל את הקבוצה
<math>\ \{ar_1,ar_2...ar_k\}</math>. על פי [[חשבון מודולרי|החשבון המודולרי]], בבסיס <math>\ n</math>, קיבלנו אותה קבוצה. נראה זאת:

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

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

==הרחבה==

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

יהיו <math>\ m,n</math> מספרים טבעיים. <math>n=\prod_{i=1}^k p_i^{n_i}</math>, כאשר <math>\ p_1, \ldots, p_k </math> [[מספר ראשוני|מספרים ראשוניים]] שונים ו-<math>\ n_i >0</math> עבור <math>\ i=1,\ldots,k</math>. נסמן <math>\ s_i=\mbox{gcd}(m, p_i^{n_i-1}(p_i-1))</math>, כאשר <math>\ \mbox{gcd}(a,b) </math> הוא ה[[מחלק משותף מקסימלי|מחלק המשותף המקסימלי]] של <math>\ a</math> ושל <math>\ b</math>, ו-<math>s=\prod_{i=1}^k s_i</math>. אזי מספר הפתרונות של המשוואה <math>x^m \equiv 1 \pmod{n}</math> מחושב באופן הבא:
# אם ה-<math>\ p_i</math> כולם אי-זוגיים, אזי למשוואה <math>x^m \equiv 1 \pmod{n}</math> יש בדיוק <math>\ s</math> פתרונות שונים (מודולו <math>\ n</math>).
# אם אחד ה-<math>\ p_i</math> זוגי, נניח <math>\ p_1</math>, ו-<math>\ n_1</math>, החזקה שלו בפירוק של <math>\ n</math>, שווה 1 או 2, מספר הפתרונות גם כן <math>\ s</math>.
#אם אחד ה-<math>\ p_i</math> זוגי, נניח <math>\ p_1</math>, ו-<math>\ n_1</math>, החזקה שלו בפירוק של <math>\ n</math>, היא לפחות 3, מספר הפתרונות של המשוואה <math>x^m \equiv 1 \pmod{n}</math> (מודולו <math>\ n</math>) מחושב באופן הבא:
## אם <math>\ s_1 = 1</math> (כלומר <math>\ m</math> אי זוגי) או ש-<math>\ s_1 = 2^{n_1-1}</math>, מספר הפתרונות הוא <math>\ s</math>.
##אם <math>\ 1<s_1 <2^{n_1-1} </math>, מספר הפתרונות הוא <math>\ 2s</math>.

==קישורים חיצוניים==
* {{MathWorld}}
<div style="direction: ltr;">
* 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 [http://www.jstor.org/pss/2688306 215] and [http://www.jstor.org/pss/2688307 217] are freely available)
</div>
[[קטגוריה:משפטים בתורת המספרים|אוילר]]
[[קטגוריה:הוכחות]]
[[קטגוריה:לאונרד אוילר]]
[[קטגוריה:חשבון מודולרי]]