משפט אוילר – הבדלי גרסאות

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

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

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

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