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

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

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

==הוכחות==
===השוואה של מערכות שאריות===
יהי <math>p</math> ראשוני ויהי <math>a</math> זר ל-<math>p</math>.

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

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

לכן איברי <math>B</math> שקולים מודולו <math>p</math> לאיברי <math>A</math> בסדר כלשהו. כלומר
:<math>\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}</math>
בהכללה, לכל <math>p</math> ראשוני ולכל <math>a</math> שלם מתקיים <math>a^p\equiv a\!\!\!\pmod{p}</math>.

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

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

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

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

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

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

*
*

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