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

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

בתורת המספרים, המשפט הקטן של פרמה קובע שלכל ראשוני p ולכל מספר שלם a, ההפרש מתחלק ב-p, כלומר .

משפט אוילר מכליל את המשפט הקטן של פרמה, מאחר ש- לכל ראשוני.

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

הוכחות[עריכת קוד מקור | עריכה]

השוואה של מערכות שאריות[עריכת קוד מקור | עריכה]

נסתכל על קבוצת כל השאריות (מלבד 0) מודולו : . נכפיל את כל האיברים בקבוצה ב-, ונקבל את .

נראה שגם ב-B מופיעות אותן שאריות, כמו ב-A: הקבוצה אינה כוללת את , מכיוון שכל המספרים הם מכפלות של שני מספרים זרים ל-, שהוא ראשוני, ולכן גם המכפלה זרה ל-. מלבד זה, אין בקבוצה שני מספרים זהים (הוכחה: נניח בשלילה ש- . מאחר ש- זר ל-, ניתן לחלק בו את שני צידי המשוואה ומתקבל ש-, מה שמוביל לסתירה).

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

אינדוקציה[עריכת קוד מקור | עריכה]

לכל , במקדם הבינומי המונה מתחלק ב-p והמכנה לא, ולכן המנה מתחלקת ב-p. מכאן שלכל מתקיים . בפרט, באינדוקציה על a, .

פעולת החבורה הראשונית[עריכת קוד מקור | עריכה]

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

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

הוכחה קומבינטורית[עריכת קוד מקור | עריכה]

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

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]

ויקישיתוף מדיה וקבצים בנושא המשפט הקטן של פרמה בוויקישיתוף