המשפט הקטן של פרמה – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ r2.6.4) (בוט מוסיף: pms:Cit teorema ëd Fermat |
מאין תקציר עריכה |
||
שורה 9:
=== השוואה של מערכות שאריות ===
נסתכל על [[קבוצה (מתמטיקה)|קבוצת כל השאריות]] (מלבד 0) מודולו <math>\ p</math>:
<math>\ A=\{1,2,3,...,p-1\}</math>. [[כפל|נכפיל]] את כל האיברים בקבוצה ב-<math>\ a</math>, ונקבל את <math>\ B=\{a,2a,3a,...,a(p-1)\}</math>.
נראה שגם ב-B מופיעות אותן שאריות, כמו ב-A: הקבוצה אינה כוללת את <math>\ 0</math>, מכיוון שכל המספרים הם מכפלות של שני מספרים זרים ל-<math>\ p</math>, שהוא [[מספר ראשוני|ראשוני]], ולכן גם המכפלה זרה ל-<math>\ p</math>. מלבד זה, אין בקבוצה <math>\ B</math> שני מספרים זהים (הוכחה: [[הוכחה בדרך השלילה|נניח בשלילה]] ש- <math>\ an=am\pmod{p}</math>. מאחר ש-<math>\ a</math> זר ל-<math>\ p</math>, ניתן לחלק בו את שני צידי המשוואה ומתקבל ש-<math>\ \ n=m\pmod{p}</math>, מה שמוביל לסתירה).
כעת, מאחר ששתי הקבוצות זהות, גם מכפלת איבריהן שווה: <math>\ a^{p-1}(p-1)!=(p-1)! \pmod{p}</math>; ומאחר ש-<math>\!\, (p-1)!</math> הוא מכפלת מספרים זרים ל-<math>\ p</math>, הרי שגם הוא זר ל-<math>\ p</math> (למעשה הוא שווה ל-1- לפי [[משפט וילסון]]), ולכן ניתן [[חילוק|לחלק]] בו את שני צידי המשוואה ולקבל את המשפט: <math>\ a^{p-1}=1 \pmod{p}</math>.
=== אינדוקציה ===
לכל <math>\ 0<k<p</math>,
<math>\ (a+1)^p \equiv a^p+1 \equiv a + 1 \pmod{p}</math>.
שורה 29:
=== הוכחה קומבינטורית ===
ניתן להוכיח את המשפט באמצעות פתרון השאלה הבאה: צובעים את הצלעות של [[מצולע משוכלל]] עם p צלעות, כל צלע באחד מ-a צבעים נתונים. כמה מצולעים אפשר ליצור, השונים זה מזה גם לאחר סיבוב? תשובה: אם הצביעה מכילה יותר מצבע אחד, אז כל סיבוב של המצולע מביא אותו לצורה שונה משום ש-p ראשוני. המקרה היחיד שבו הסיבוב אינו משפיע הוא כאשר כל הצלעות צבועות באותו הצבע. מספר האפשרויות לצבוע את המצולע הוא <math>\ a^p</math>, מתוכן a צביעות בצבע אחד, והשאר, <math>\ a^p-a</math>, בשני צבעים שונים לפחות.
אין לספור פעמיים את אותו מצולע רק בסיבוב שונה. על כל מצולע, יש בדיוק p סיבובים כאלה. לכן התשובה היא <math>\ {a^p-a \over p} +a</math> (חישוב זה הוא מקרה פרטי של [[הלמה של ברנסייד]], עבור ה[[פעולת חבורה על קבוצה|פעולה]] של [[חבורה ציקלית|החבורה הציקלית מסדר p]] על אוסף הצביעות).
התשובה הזאת חייבת להיות [[מספר שלם]], ו-a הוא מספר שלם, לכן גם <math>\ {a^p-a \over p}</math> הוא מספר שלם, ומכאן <math>\ a^p\equiv a \pmod{p}</math>.
[[קטגוריה:משפטים בתורת המספרים|פרמה]]
| |||