המשפט הקטן של פרמה – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
←קומבינטוריקה: צלעות מצולע עדיפות על גזרות מעגל |
|||
שורה 27:
=== קומבינטוריקה ===
ניתן להוכיח את המשפט באמצעות פתרון השאלה הבאה: צובעים את הצלעות של [[מצולע משוכלל]], כל צלע באחד מ-a צבעים נתונים. כמה מצולעים אפשר ליצור, השונים זה מזה גם לאחר סיבוב? אם הצביעה מכילה יותר מצבע אחד, אז כל סיבוב של המצולע מביא אותו לצורה שונה משום ש-p ראשוני. המקרה היחיד שבו הסיבוב אינו משפיע הוא כאשר כל הצלעות צבועות באותו הצבע. מספר האפשרויות לצבוע את המצולע הוא <math>\ a^p</math>, מתוכן a צביעות בצבע אחד, והשאר, <math>\ a^p-a</math>, בשני צבעים שונים לפחות.
את הצביעות שבהן אותו מעגל בסיבוב שונה לא צריך לספור. על כל מעגל, יש בדיוק p סיבובים כאלה. לכן התשובה היא <math>\ {a^p-a \over p} +a</math>. {{ש}}התשובה הזאת חייבת להיות מספר שלם, ו-a הוא מספר שלם, לכן גם <math>\ {a^p-a \over p}</math> הוא מספר שלם, ומכאן <math>\ a^p\equiv a \pmod{p}</math>.
| |||