משפט אוילר קובע שאם מספר טבעי, אז לכל זר ל- מתקיים , כלומר, n מחלק את ההפרש . לדוגמה עבור a=4 ו-n=15, מכיוון ש- , המשפט מנבא ש-15 מחלק את .
בנוסחה זו, (קרי: "פִי של n") היא פונקציית אוילר של , השווה למספרם של המספרים הזרים ל- וקטנים ממנו.
משפט אוילר אינו נותן את התוצאה הטובה ביותר האפשרית. לדוגמה, כל מספר זר ל-240 מקיים , בעוד ש-. את החזקה הקטנה ביותר שתבטיח התנהגות כזו מסמנים ב-, והיא שווה לאקספוננט של חבורת אוילר ה--ית. בעוד שפונקציית אוילר של מתקבלת מהכפלת כל המספרים , הפונקציה שווה לכפולה המשותפת המינימלית של כל המספרים האלה (לאחר שהגורם מוחלף ב-, אם ).
המשפט נובע מיד מן העובדה שקבוצת המספרים הזרים ל- מהווה חבורה (חבורת אוילר של ) ביחס לכפל ולקיחת השארית בחלוקה ל-. הגודל של חבורה זו הוא , ולכן כל איבר בחבורה מקיים (משפט לגראנז').
להלן הוכחה ישירה. על-פי הגדרת הפונקציה, הוא מספר השאריות הזרות ל- היכולות להתקבל מחילוק ב-. נסמן קבוצה זו כך: כעת נכפיל את כל איברי הקבוצה ב-. נקבל את הקבוצה
. על פי החשבון המודולרי, בבסיס , קיבלנו אותה קבוצה. נראה זאת:
כל איבר בקבוצה החדשה הוא שארית בחילוק ל-, מאחר שהוא תוצאה של חישוב מודולרי בבסיס .
כל איבר בקבוצה החדשה זר ל-, מאחר שהוא מכפלת שני מספרים זרים ל-.
אין בקבוצה החדשה שני איברים שווים. הוכחה: נניח בשלילה . מאחר ש- זר ל-, ניתן לחלק את שני צידי המשוואה ב-. כלומר: - מה שמוביל אותנו לסתירה.
ומאחר ששתי הקבוצות זהות - גם מכפלת איבריהם צריכה להיות שווה: , ומאחר שהמספר הוא מכפלת מספרים זרים ל-, וגם הוא זר ל-, ניתן לחלק בו את שני צידי המשוואה. כלומר: ו-, על פי הגדרתו, הוא מספר השאריות הזרות ל- בחילוק ל-
. כלומר - הוא שווה ל-.
משפט אוילר הוא מקרה פרטי של המשפט הבא (ג'יימס אלונסו):
יהיו מספרים טבעיים. , כאשר מספרים ראשוניים שונים ו- עבור . נסמן , כאשר הוא המחלק המשותף המקסימלי של ושל , ו-. אזי מספר הפתרונות של המשוואה מחושב באופן הבא:
אם ה- כולם אי-זוגיים, אזי למשוואה יש בדיוק פתרונות שונים (מודולו ).
אם אחד ה- זוגי, נניח , ו-, החזקה שלו בפירוק של , שווה 1 או 2, מספר הפתרונות גם כן .
אם אחד ה- זוגי, נניח , ו-, החזקה שלו בפירוק של , היא לפחות 3, מספר הפתרונות של המשוואה (מודולו ) מחושב באופן הבא:
James Alonso, Number of Solutions of the Congruencexm = r (mod n), Mathematics Magazine, Vol. 46, No. 4 (Sep 1973), pp. 215-217 (pages 215 and 217 are freely available)