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

בתורת המספרים, המשפט הקטן של פרמה קובע שלכל ראשוני 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$ . זהו מספר שלם, ולכן $\ a^{p}\equiv a{\pmod {p}}$ . (חישוב זה הוא מקרה פרטי של הלמה של ברנסייד, עבור הפעולה של החבורה הציקלית מסדר p על אוסף הצביעות).