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

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

p

ולכל מספר שלם

a

הזר ל-

p

, ההפרש

a^{p-1}-1

מתחלק ב-

p

, כלומר

a^{p-1}\equiv 1\!\!\!{\pmod {p}}

.

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

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

הוכחות[עריכת קוד מקור | עריכה]

השוואה של מערכות שאריות[עריכת קוד מקור | עריכה]

יהי $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<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$ על אוסף הצביעות).