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

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

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

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

הוכחות

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

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

נראה שגם ב־$B$ מופיעות אותן שאריות, כמו ב־$A$ : הקבוצה אינה כוללת את 0, מכיוון שכל המספרים הם מכפלות של שני מספרים זרים ל־$p$ , שהוא ראשוני, ולכן גם המכפלה זרה ל־$p$ .

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

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

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

אינדוקציה

לכל $0<k<p$ , במקדם הבינומי ${\frac {p!}{k!(p-k)!}}$ המונה מתחלק ב־$p$ והמכנה לא, ולכן המנה מתחלקת ב־$p$ .

מכאן שלכל $a,b$ מתקיים $(a+b)^{p}=\sum _{k=0}^{p}{\frac {p!}{k!(p-k)!}}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,\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 על אוסף הצביעות).

ראו גם

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