המשפט הקטן של פרמה
מתוך ויקיפדיה, האנציקלופדיה החופשית
המשפט הקטן של פרמה הוא המשפט הבא: לכל
ראשוני ו-
זר לו, מתקיים:
.
משפט זה הוא מקרה פרטי של משפט אוילר, מאחר ש-
לכל
ראשוני.
[עריכה] הוכחה
נוכיח את המשפט.
נסתכל על קבוצת כל השאריות (מלבד 0) שעשויות להתקבל מחילוק ב-
:

נכפל את כל איברי קבוצה זו ב-
(מודולו
). נקבל את הקבוצה:

טענת עזר: בחשבון מודולרי בבסיס
, מתקבלת קבוצה זהה. נוכיח זאת:
- כל מספר שקיבלנו קטן מ-
, שכן החישוב נעשה בבסיס
. - לא קיבלנו את התוצאה
, מכיוון שכל המספרים הם מכפלות של שני מספרים זרים ל-
.
ראשוני ולפיכך גם מכפלתם זרה ל-
. - לא קיבלנו בקבוצה זו שני מספרים זהים. הוכחה: נניח שמתקיים
. מאחר ש-
זר ל-
, ניתן לחלק בו את שני צידי המשוואה ומתקבל ש-
.
מאחר ששתי הקבוצות זהות, גם מכפלת איבריהן שווה:

ומאחר ש-
הוא מכפלת מספרים זרים ל-
, הרי שגם הוא זר ל-
, ולכן ניתן לחלק בו את שני צידי המשוואה:

מ.ש.ל

