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

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

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

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

הוכחות

השוואה של מערכות שאריות

נסתכל על קבוצת כל השאריות (מלבד 0) מודולו $\ p$: $\ A=\{1,2,3,...,p-1\}$. נכפיל את כל האיברים בקבוצה ב-$\ a$, ונקבל את $\ B=\{a,2a,3a,...,a(p-1)\}$.

נראה שגם ב-B מופיעות אותן שאריות, כמו ב-A: הקבוצה אינה כוללת את $\ 0$, מכיוון שכל המספרים הם מכפלות של שני מספרים זרים ל-$\ p$, שהוא ראשוני, ולכן גם המכפלה זרה ל-$\ p$. מלבד זה, אין בקבוצה $\ B$ שני מספרים זהים (הוכחה: נניח בשלילה ש- $\ an=am{\pmod {p}}$. מאחר ש-$\ a$ זר ל-$\ p$, ניתן לחלק בו את שני צידי המשוואה ומתקבל ש-$\ \ n=m{\pmod {p}}$, מה שמוביל לסתירה).

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

אינדוקציה

לכל $\ 0<k<p$, במקדם הבינומי $\ {\frac {p!}{k!(p-k)!}}$ המונה מתחלק ב-p והמכנה לא, ולכן המנה מתחלקת ב-p. מכאן שלכל $\ a,b$ מתקיים $\left(a+b\right)^{p}=\sum \limits _{k=0}^{p}{{\frac {p!}{k!\left(p-k\right)!}}a^{k}b^{p-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,\dots ,a\}$, שגודלה כמובן $\ a^{p}$. וקטור מהווה נקודת שבת ביחס לפעולה רק אם כל הרכיבים שלו שווים, וכאלה וקטורים יש בדיוק a. גודלו של כל מסלול חייב לחלק את סדר החבורה p, ולכן $\ a^{p}-a$ הווקטורים שאינם נקודות שבת שייכים למסלולים בגודל p; מכאן ש- p מחלק את $\ a^{p}-a$.

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

הוכחה קומבינטורית

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

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

ראו גם

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