המשפט הקטן של פרמה

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

המשפט הקטן של פרמה הוא המשפט הבא: לכל \ p ראשוני ו-\ a זר לו, מתקיים:

a^{p-1}=1\ (mod\ p).

משפט זה הוא מקרה פרטי של משפט אוילר, מאחר ש-\!\, \phi (p)=p-1 לכל \ p ראשוני.

[עריכה] הוכחה

נוכיח את המשפט.

נסתכל על קבוצת כל השאריות (מלבד 0) שעשויות להתקבל מחילוק ב-\ p:

\!\, \{1,2,3,...,p-1\}

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

\!\, \{a,2a,3a,...,a(p-1)\}

טענת עזר: בחשבון מודולרי בבסיס \ p, מתקבלת קבוצה זהה. נוכיח זאת:

  1. כל מספר שקיבלנו קטן מ-\ p, שכן החישוב נעשה בבסיס \ p.
  2. לא קיבלנו את התוצאה \ 0, מכיוון שכל המספרים הם מכפלות של שני מספרים זרים ל-\ p. \ p ראשוני ולפיכך גם מכפלתם זרה ל-\ p.
  3. לא קיבלנו בקבוצה זו שני מספרים זהים. הוכחה: נניח שמתקיים na=ma\ (mod\ p). מאחר ש-\ a זר ל-\ p, ניתן לחלק בו את שני צידי המשוואה ומתקבל ש-\!\, n=m.

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

a^{p-1}(p-1)!=(p-1)!\ (mod\ p)

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

a^{p-1}=1\ (mod\ p)

מ.ש.ל