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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

בתורת המספרים, המשפט הקטן של פרמה קובע שלכל ראשוני 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}.

ראו גם[עריכת קוד מקור | עריכה]