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

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

הצהרת המשפט

1. ראשוני

If p הוא מספר ראשוני a הוא מספר שלם שאינו ניתן לחלוקה ב pאז a^p-1 - 1 מחולק לפי p.

זה כתוב באופן רשמי כך: a^p-1 ≡ 1 (נגד p).

הערה: מספר ראשוני הוא מספר טבעי שמתחלק רק ב-XNUMX ובעצמו ללא שארית.

לדוגמה:

• a = 2
• p = 5
• a^p-1 - 1 = 2^{5 - 1} - 1 = 2⁴ – 1 = 16 – 1 = 15
• מספר 15 מחולק לפי 5 ללא שארית.

2. אלטרנטיבה

If p הוא מספר ראשוני, a כל מספר שלם, אם כן a^p דומה ל a מודולו p.

a^p ≡ א (נגד p)

היסטוריה של מציאת ראיות

פייר דה פרמה ניסח את המשפט ב-1640, אך לא הוכיח זאת בעצמו. מאוחר יותר, זה נעשה על ידי גוטפריד וילהלם לייבניץ, פילוסוף, לוגיקן, מתמטיקאי גרמני וכו'. מאמינים שההוכחה הייתה לו כבר ב-1683, למרות שמעולם לא פורסמה. ראוי לציין כי לייבניץ גילה את המשפט בעצמו, מבלי לדעת שהוא כבר נוסח קודם לכן.

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

דוגמה לבעיה

מצא את השארית של מספר 2¹² on 12.

פתרון

בואו נדמיין מספר 2¹² as 2⋅2¹¹.

11 הוא מספר ראשוני, לפיכך, לפי המשפט הקטן של פרמה אנו מקבלים:

2¹¹ ≡ 2 (נגד 11).

לָכֵן, 2⋅2¹¹ ≡ 4 (נגד 11).

אז המספר 2¹² מחולק לפי 12 עם שארית שווה ל 4.