המשפט הקטן של פרמה – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ ←השוואה של מערכות שאריות: קישורים פנימיים |
|||
שורה 10:
<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>, ולכן ניתן לחלק בו את שני צידי המשוואה ולקבל את המשפט: <math>\ a^{p-1}=1 \pmod{p}</math>.
| |||