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

המשפט הקטן של פרמה הוא המשפט הבא: לכל $\ 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$ , מתקבלת קבוצה זהה. נוכיח זאת:

כל מספר שקיבלנו קטן מ- $\ p$ , שכן החישוב נעשה בבסיס $\ p$ .
לא קיבלנו את התוצאה $\ 0$ , מכיוון שכל המספרים הם מכפלות של שני מספרים זרים ל- $\ p$ . $\ p$ ראשוני ולפיכך גם מכפלתם זרה ל- $\ p$ .
לא קיבלנו בקבוצה זו שני מספרים זהים. הוכחה: נניח שמתקיים $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)$

מ.ש.ל

דף זה שונה לאחרונה בתאריך 15:48, 23 ביולי 2006 על־ידי משתמש ויקיפדיה אבינעם. מבוסס על העבודה של משתמש(י) ויקיפדיה עוזי ו., דוד שי, Gadial, יובל מדר וגם חגי הלמן וגם משתמש(ים) אנונימי(ים) של ויקיפדיה.
הטקסט מוגש בכפוף ל־GNU Free Documentation License.
יוצרי הערך מפורטים בדף "גרסאות קודמות". בעלי זכויות היוצרים בתמונה מופיעים בדף התמונה.
אודות ויקיפדיה
הבהרה משפטית