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

בתורת המספרים, **המשפט הקטן של פרמה** (על שם המתמטיקאי הצרפתי פייר דה פרמה) קובע כי:
:לכל מספר ראשוני p ולכל מספר שלם a, שארית החלוקה של a ב-p  שווה לשארית החלוקה של a^p ב-p, דהיינו מתקיים a^{p}\equiv a\!\!\!\pmod{p}.
עבור a זר ל-p, אפשר לחלק שוויון זה ב-a, ולקבל a^{p-1}\equiv1\!\!\!\pmod{p}

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

למשפט מגוון שימושים בתורת המספרים. הוא עומד בבסיסם של מבחני ראשוניות רבים (למשל אלגוריתם מילר-רבין) ומכאן חשיבותו הגדולה בקריפטוגרפיה.

## הוכחות
### השוואה של מערכות שאריות
יהי p ראשוני ויהי a מספר שלם.

אם a אינו זר ל-p, אז משום ש-p מספר ראשוני, בהכרח p מחלק a. מכאן ש-p מחלק גם את a^{p}, ואז נקבל a^{p}\equiv 0\equiv a\!\!\!\pmod{p}. בפרט a^{p}\equiv a\!\!\!\pmod{p}.

נניח ש-a זר ל-p. תהי A=\{1,2,\ldots,p-1\} קבוצת כל השאריות (מלבד 0) מודולו p. נכפיל את כל איברי הקבוצה ב-a ונקבל B=\bigl\{a,2a,\ldots,(p-1)a\bigr\}.

ראשית, B אינה כוללת את 0, מפני שכל המספרים הם מכפלות של שני מספרים זרים ל-p, ולכן גם מכפלתם זרה ל-p.
שנית, כל איברי B שונים מודולו p – נניח בשלילה כי שנים מהם שקולים זה לזה. נקבל כי
:\begin{align}n_1a&\equiv n_2a\!\!\!\pmod{p},\qquad:1\le n_1
כלומר p\mid(n_2-n_1). אבל 1\leq n_2-n_1, בסתירה.

לכן איברי B שקולים מודולו p לאיברי A בסדר כלשהו. כלומר
:\begin{align}a\cdot2a\cdots(p-1)a&\equiv1\cdot2\cdots(p-1)\!\!\pmod{p}\\a^{p-1}(p-1)!&\equiv(p-1)!\!\!\pmod{p}\qquad:\gcd\bigl\{(p-1)!,p\bigr\}=1\\a^{p-1}&\equiv1\!\!\pmod{p}\end{align}
בהכללה, לכל p ראשוני ולכל a שלם מתקיים a^p\equiv a\!\!\!\pmod{p}.

### אינדוקציה
לכל 0, במקדם הבינומי \binom{p}{k}=\frac{p!}{k!(p-k)!} המונה מתחלק ב-p והמכנה לא, ולכן המנה מתחלקת ב-p. מכאן שלכל a,b מתקיים
:(a+b)^p=\sum_{k\,=\,0}^p\binom{p}{k}a^{p-k}b^k\equiv a^p+b^p\!\!\!\pmod{p}
בפרט, באינדוקציה על a מתקיים (a+1)^p\equiv a^p+1\equiv a+1\!\!\!\pmod{p}.

### פעולת החבורה הראשונית
החבורה הציקלית \Z_p פועלת, על ידי סיבוב, על קבוצת הווקטורים באורך p מעל קבוצת הערכים \{1,\ldots,a\}, שגודלה כמובן a^p. וקטור מהווה נקודת שבת ביחס לפעולה רק אם כל הרכיבים שלו שווים, וכאלה וקטורים יש בדיוק a. גודלו של כל מסלול חייב לחלק את סדר החבורה p, ולכן a^p-a הווקטורים שאינם נקודות שבת שייכים למסלולים בגודל p; מכאן ש-p מחלק את a^p-a.

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

### הוכחה קומבינטורית
ניתן להוכיח את המשפט באמצעות פתרון השאלה הבאה (זהו ניסוח אלמנטרי של ההוכחה הקודמת):
צובעים את הצלעות של מצולע משוכלל עם p צלעות, כל צלע באחד מ-a צבעים נתונים. כמה מצולעים ניתן ליצור, השונים זה מזה גם לאחר סיבוב?
אם הצביעה מכילה יותר מצבע אחד, אז כל סיבוב של המצולע מביא אותו לצורה שונה מפני ש-p ראשוני. המקרה היחיד שבו הסיבוב אינו משפיע הוא כאשר כל הצלעות צבועות באותו הצבע. מספר האפשרויות לצבוע את המצולע הוא a^p, מתוכן a צביעות בצבע אחד, והשאר, a^p-a, בשני צבעים שונים לפחות. כל צביעה כזו מופיעה בדיוק p פעמים, ולכן מספר המצולעים השונים הוא \frac{a^p-a}{p}+a. זהו מספר שלם, ולכן a^p\equiv a\!\!\!\pmod{p}. (חישוב זה הוא מקרה פרטי של הלמה של ברנסייד, עבור הפעולה של החבורה הציקלית מסדר p על אוסף הצביעות).

## ראו גם
*מספר פסאודו-ראשוני
*מספר קרמייקל

## קישורים חיצוניים

*
*

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