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

בתורת המספרים, המשפט הקטן של פרמה (על שם המתמטיקאי הצרפתי פייר דה פרמה) קובע כי:

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

עבור $a$ זר ל-$p$, אפשר לחלק שוויון זה ב-$a$, ולקבל $a^{p-1}\equiv 1\!\!\!{\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{aligned}n_{1}a&\equiv n_{2}a\!\!\!{\pmod {p}},\qquad :1\leq n_{1}<n_{2}\leq p-1\\n_{1}&\equiv n_{2}\!\!\!{\pmod {p}},\qquad \quad :\gcd\{a,p\}=1\end{aligned}}$

כלומר $p\mid (n_{2}-n_{1})$. אבל $1\leq n_{2}-n_{1}<p$, בסתירה.

לכן איברי $B$ שקולים מודולו $p$ לאיברי $A$ בסדר כלשהו. כלומר

${\begin{aligned}a\cdot 2a\cdots (p-1)a&\equiv 1\cdot 2\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}&\equiv 1\!\!{\pmod {p}}\end{aligned}}$

בהכללה, לכל $p$ ראשוני ולכל $a$ שלם מתקיים $a^{p}\equiv a\!\!\!{\pmod {p}}$.

אינדוקציה

לכל $0<k<p$, במקדם הבינומי ${\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}}$.

פעולת החבורה הראשונית

החבורה הציקלית $\mathbb {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$ על אוסף הצביעות).

ראו גם

• מספר פסאודו-ראשוני
• מספר קרמייקל

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

מדיה וקבצים בנושא המשפט הקטן של פרמה בוויקישיתוף

• המשפט הקטן של פרמה, באתר MathWorld (באנגלית)
• המשפט הקטן של פרמה, באתר אנציקלופדיה בריטניקה (באנגלית)