המשפט הקטן של פרמה – 0. הקדמה

פרמה הקטן

פייר דה פרמה. בחוגים מסויימים: פרמה הקטן.

פייר דה פרמה (1601 – 1665) היה עורך-דין צרפתי בהכשרתו ועיסוקו. עם זאת, הוא נודע יותר בתור מתמטיקאי חובב – בין המשפיעים של המאה ה17 – שעסק במגווון תחומים מתמטים כמו תורת המספרים וגיאומטריה אנליטית, ונחשב לחלוצי ההסתברות והחשבון הדיפרנציאלי והאינטגרלי. הוא נהג לפרסם את משפטיו במכתבים לחבריו, פעמים רבות בלי הוכחה – כך משפטים שנושאים את שמו הוכחו רק עשרות עד מאות שנים לאחר מכן ע"י מתמטיקאים אחרים. גם את המשפט שעליו נכתבת סדרת פוסטים זו פרמה רק ציין, ובהצהרה שלא מניחה את הדעת התחמק מהוכחה: "את ההוכחה הייתי שולח לך אילולא הייתי חושש מלהאריך יתר על המידה" (נשבע). לייבניץ ואוילר הם אלו שהוכיחו לראשונה את המשפט – אותה הוכחה, אבל באופן בלתי-תלוי – תופעה תמוהה שקוראת מידי פעם במתמטיקה.
כל העניין הזה קצת מזכיר את הפרובוקציה של אותו פרמה לגבי המשפט המפורסם הנקרא על שמו, "המשפט האחרון של פרמה": "גיליתי הוכחה נפלאה למשפט זה, אך שוליים אלו צרים מלהכילה".
אין זאת בכדי להוריד מכבודו. הבחור גיבש תחומים חדשים ופיתח ישנים, והיה לרוב הראשון להבחין במשפטים שניסח. לשאול את השאלה הנכונה זו יכולת יקרה גם במתמטיקה. טוב, בואו נתלכלך קצת –

חשבון מודולרי

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

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

בהסתכלות גבוהה יותר, אפשר להסתכל על המחלקות האלה כנובעות מיחס השקילות x\sim y\leftrightarrow n|x-y, או (באופן שקול) כקוסטים של תת-החבורה n\mathbb{Z} בתוך \mathbb{Z}, או על איברי חוג המנה \mathbb{Z}/n\mathbb{Z}. ההסתכלות האחרונה אולי הכי מתאימה, כי אנחנו הולכים לכפול, ולא רק לחבר את המחלקות.

דוגמא מפורשת, כי זה תמיד עובד: אם n=3 אז המחלקות (אשר יסומנו עם קו עליון) יהיו:

\overline{0}=\{...,-3,0,3,6,...\},\overline{1}=\{...,-2,1,4,...\},\overline{2}=\{...,-1,2,5,...\}

הכוונה ב\overline{i} למחלקה שמכילה את i. נשים לב ש2 מספרים נמצאים באותה מחלקה אם ורק אם ההפרש ביניהם מתחלק ב3. כשרוצים להגיד ששני מספרים הם באותה מחלקה, מקצרים ואומרים שהם שווים "מודולו" (modulo) 3. כשנחשב ביטויים מודולו 3, למעשה נחשב מהי המחלקה שלהם.

החיבור והכפל בין המחלקות האלה יוגדר בצורה הטבעית:

\overline{i}+\overline{j}=\overline{i+j},\overline{i}\cdot\overline{j}=\overline{ij}

החלק החשוב הוא להראות שהפעולות עקביות. כלומר, שאם

\overline{i}=\overline{i'},\overline{j}=\overline{j'}

אז

\overline{i}\cdot\overline{j}=\overline{i'}\cdot\overline{j'}

(וטענה דומה עם חיבור). נראה זאת:

לפי ההגדרה, זה שקול לכך שij, i'j' באותה מחלקה, כלומר ההפרש ביניהם מתחלק ב3. מכך ש\overline{i}=\overline{i'} ו\overline{j}=\overline{j'}, נובע שההפרש בין i וi' מתחלק ב3, וכך גם ההפרש בין j וj', ולכן:

ij-i'j'=(i-i')j+(j-j')i'

כלומר ij-i'j' סכום של 2 ביטויים שמתחלקים ב3, לכן הוא מתחלק ב3. נובע ש ij וi'j' באותה מחלקה. הוריי!

דוגמא יום-יומית לחשבון מודולרי היא חישובי שעות: כשהשעה היא 11 בערב ואנחנו מחשבים ומוצאים שעוד 6 שעות יהיה 5 לפנות בוקר, עשינו חשבון מודולרי – התחשבנו רק בשארית החלוקה ב12.

חשוב להבהיר שהחשבון הזה מתנהג בצורה הטבעית ביותר, כלומר אני – ואתם – יכולים לחבר ולכפול מחלקות כאוות נפשנו. בנוסף, תמיד מתקיים, לפי ההגדרה, a \in \overline{a}. החשבון הזה בא לפשט דברים ולא לסבך אותם – אפשר לנסח את המשפט הקטן גם בלעדיו, אבל הוא מקל על ההתעסקות בו.

משפט קטן של פרמה, מה הוא אומר?

ראשוני הראשוניים

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

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

לכל מספר ראשוני p ולכל מספר שלם a, מתקיים: \overline{a^{p}}=\overline{a}, כלומר: a^p וa באותה המחלקה ביחס לp, או (הניסוח הכי פשוט):

a^p-a מתחלק בp, עבור כל a שלם

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

  • נציב a=1. נקבל: a^{p}-a=0, וזה מתחלק בp לכל a. אבל בעצם גם לכל p שלם שונה מ0 ולא השתמשנו כאן בראשוניות. לא מעניין.
  • נציב a=2. נקבל שמתקיים: 2^p-2 מתחלק בp לכל ראשוני p. עבור p=5, לדוגמא: 2^{5}-2=32-2=30=5\cdot6.
  • נציב p=2. נקבל: a^2-a=a(a-1) מתחלק ב2, לכל a. זה הגיוני – יש לנו מכפלה של 2 מספרים עוקבים, לכן אחד מהם בהכרח מתחלק ב2.
  • נציב p=3. נקבל: a^3-a=a(a^2-1)=(a-1)a(a+1) מתחלק ב3. אותו הנימוק של p=2 מוכיח את הטענה כאן: יש לנו מכפלה של שלושה מספרים עוקבים, לכן אחד מהם מתחלק ב3 ועל כן גם מכפלתם.
  • במקרה p=5 המשפט גורס כי a^{5}-a=a(a^{4}-1)=a(a^{2}-1)(a^{2}+1)=a(a-1)(a+1)(a^{2}+1) מתחלק ב5 עבור כל a. הטיעון "הרגיל" שלנו קורס – אין לנו כאן 5 מספרים עוקבים. עם זאת, מתקבל הרושם שאפשר להוכיח את זה באופן דומה: אם אחד מבין a-1, a, a+1 מתחלק ב5, סיימנו. אחרת, a נמצא במחלקה \overline{2} או \overline{3} (כשמסתכלים על שאריות חלוקה ב5). צריך להראות ש5 מחלק את a^2+1 כלומר ש\overline{a^2+1}=\overline{0}. במקרה \overline{a}=\overline{2} נקבל: \overline{a^{2}+1}=(\overline{a})^{2}+\overline{1}=\overline{4}+\overline{1}=\overline{0}, וכנ"ל כאשר \overline{a}=\overline{3}. עוד עניין שכדאי לתת עליו את הדעת הוא שa^5-a מכיל מכפלה של 3 מספרים עוקבים ולכן מתחלק ב3 – אפילו שבבירור 3\neq5. נדון בזה בהמשך.

כמה מסקנות מיידיות:

  1. המשפט לא טריוויאלי.
  2. יתרה מכך (וחלקית כתוצאה מכך), המשפט מגניב.
  3. הביטוי a(a-1)\cdots(a-(p-1)) (מכפלה של p מספרים עוקבים) מתחלק בp,  וזה מוכיח חלק מהמקרים של המשפט.
  4. נראה שיותר טבעי להוכיח את המשפט כאשר p קבוע וa משתנה, ולא להיפך.
  5. אם נקבע p ראשוני, אז כדי להוכיח את המשפט, מספיק לעבור על p המספרים a=0,1,\cdots,p-1 ולבדוק שהמשפט נכון עבורם. הסיבה לכך היא שהמספרים האלה הם נציגים שונים מכל אחת מהמחלקות (לפי שארית חלוקה בp), ושבעזרת חשבון מודולרי פשוט אפשר לראות ש\overline{a^p-a}=\overline{b^p-b} כאשר \overline{a}=\overline{b}. כלומר אם הראנו שa^p-a מתחלק בp עבור נציגים מכל אחת מp המחלקות, אז למעשה הוכחנו את המשפט לכל המספרים השלמים. זאת כבר מסקנה יפה, שנוח להראות עם חשבון מודולרי ומעצבן אחרת.

נעיר כי יש ניסוח שקול של המשפט, שאומר שa^{p-1}-1 מתחלק בp עבור a שלא מתחלק בp. זה שקול, כי אפשר לפרק את הביטוי בניסוח המקורי כך: a^{p}-a=a(a^{p-1}-1), ואם זה מתחלק בp (כמו שנובע מהניסוח המקורי של המשפט) וa לא מתחלק בp אז בהכרח a^{p-1}-1 מתחלק בp. הכיוון השני של השקילות מיידי.

שימושים

בטרם נפנה להוכחות של המשפט, חובתנו היא להראות שימושים למשפט.

  • פישוט חישובים: אם אנחנו רוצים לחשב שארית חלוקה של ביטוי סבוך במספר ראשוני p, והביטוי מערב חזקות גבוהות, אז החישוב ניתן לפישוט רב: ניתן איטרטיבית להחליף את  a^{k} בa^{k-p+1} כאשר k\ge p-1 כי: \overline{a^{k}}=\overline{a^{k-p}a^{p}}=\overline{a^{k-p}}\cdot\overline{a^{p}}=\overline{a^{k-p}}\cdot\overline{a^{1}}=\overline{a^{k-(p-1)}}. אפשר לעשות זאת בבת-אחת: אם נכתוב את k בתור q(p-1)+r לאחר שנחלק (עם שארית) את k בp-1 ולקבל \overline{a^{k}}=\overline{a^{r}}, כאשר r<p. כמובן שיש גם את היעולים הרגילים האחרים, כמו לחשב את a בחזקת חזקות של 2 (מודולו p כמובן) ואז לחשב את a^r בעזרת הייצוג של r בבסיס 2.
  • פישוט פולינומים: אם יש לי פולינום מעל \mathbb{Z}/p\mathbb{Z}, אז קיים פולינום שקול (שמקבל את אותם הערכים בכל נקודה) ממעלה קטנה מp. הסיבה לכך היא שהפולינום P(x)=x^{p}-x מתאפס בכל נקודה, ובגלל ש(\mathbb{Z}/p\mathbb{Z})[x] הוא חוג אוקלידי – כלומר חוג חילוק עם שארית (נובע מכך ש\mathbb{Z}/p\mathbb{Z} הוא שדה), אז אני יכול לחלק פולינום נתון בפולינום P ולקחת את השארית, והיא תהיה פולינום שקול.
  • טריקים קומבינטורים: העובדה ש1-a^{p-1} שווה ל1 מודולו p אמ"מ a=0 מודולו p, כלומר, שהביטוי הזה הוא אינדיקטור לכך שa=0 מודולו p, היא בסיס להוכחות אלגנטיות המערבות ספירת פתרונות של משוואות מעל \mathbb{Z}/p\mathbb{Z}. לדוגמא, אם יש לי את מערכת המשוואות הפולינומיאלית F_{1}(\vec{x})=F_{2}(\vec{x})=\cdots=F_{n}(\vec{x})=0 כאשר \vec{x}\in(\mathbb{Z}/p\mathbb{Z})^{m}, אז הביטוי \sum_{\vec{x}\in(\mathbb{Z}/p\mathbb{Z})^{m}}\prod_{i=1}^{n}(1-F_{i}^{p-1}(\vec{x})) סופר לי את מספר הפתרונות מודולו p. זה הרעיון המרכזי באחת ההוכחות של משפט שוואליה-וורנינג. גם הזהות \sum_{a\in \mathbb{Z}/p\mathbb{Z}} a^i=-1_{p-1|i} מודולו p שמוכחת חלקית בעזרת המשפט הקטן מוצאת לה שימושים בקומבינטוריקה ותורת המספרים.
  • בדיקת ראשוניות – הסתברותית: בעיה עתיקה במתמטיקה היא בעיית ההכרעה בדבר ראשוניותו של מספר נתון, בצורה יעילה ככל הניתן (כלומר, לא סתם לעבור סדרתית על מספרים ולבדוק האם הם מחלקים את המספר). לפי המשפט הקטן, אם נתון לי n ומצאתי a כך שa^{n}-a לא מתחלק בn, הוכחתי שn פריק. מבחן הראשוניות של פרמה הוא בדיוק זה: בהינתן מספר n, מגרילים a-ים ומחשבים את a^n-a מודולו n. אם מתישהו לא קיבלתי \overline{0}, זו הוכחה לכך שn פריק ואינו ראשוני. אחרת, בהסתברות גבוהה (אך לא בוודאות), המספר הוא ראשוני. יש פגם עקרוני במבחן: יש מספרים המכונים "מספרי קרמייקל" – שאינסופיותם הוכחה רק ב1994 – אשר מקיימים את המשפט הקטן בלי להיות ראשוניים. לדוגמא, 561: a^{561}-a מתחלק ב561 לכל a שלם. הם לא רבים במובן היחסי – כלומר, ההסתברות להיתקל במספר כזה בין 1 לn שואפת ל0 כאשר n שואף לאינסוף, והם מקיימים תכונות מגבילות – כמו שכולם מכפלה של מספרים ראשוניים שונים (דרך אחרת לנסח זאת היא כך: הם לא מתחלקים בריבוע מלבד 1), אבל בכל זאת, הם לא נפסקים החל מנקודה מסויימת.
  • בדיקת ראשוניות – הודו על המפה: ב2002 פותח לראשונה אלגוריתם דטרמיניסטי שבודק ראשוניות בזמן ריצה פולינומיאלי ב\log המספר (כלומר, במספר פעולות שהוא בערך מספר הספרות של המספר בחזקת מספר C, במקרה שלנו – C \le 8. מספר הספרות הוא בעצם גודל הקלט), ע"י שלושה מתמטיקאים הודים. ההוכחה מתבססת על וריאציה על המשפט הקטן, שבה התכונה כן מתקיימת אם ורק אם n ראשוני: המקדמים של הפולינום (x+a)^{n} זהים מודולו n למקדמים של הפולינום x^{n}+a עבור a טבעי שזר לn (מספר a  שלא מתחלק באף גורם של n). אם נשווה את המקדם החופשי בין שני האגפים נקבל את המשפט הקטן.

דיי מרשים. אז למה הדבר הנפלא הזה מכונה "המשפט הקטן"? ביזיון. האמת היא שזה לא השם המקורי, אלא (כמו הרבה דברים בחיים) שם שתפס במאמר מ1913.

אינטואיציה

אפשר לנסות להבין מאיפה המשפט הגיע בדרך הבאה: נקבע ראשוני p. לכל a שלם שלא מתחלק בp נסתכל בסדרה המוגדרת ע"י החזקות של a, כלומר a_n = \overline{a^n}, כאשר הסדרה מתחילה בn=0, כלומר האיבר הראשון הוא 1.

  • הבחנה חשובה ראשונה היא שיש 2 ערכים זהים בסדרה. אפשר לראות בזה אפליקציה של עיקרון שובך היונים האינסופי: אם יש לי אינסוף איברים שערכיהם מרכיבים קבוצה סופית, אז שניים מהאיברים שווים. במקרה שלנו, יש סדרה אינסופית והערכים הם p המחלקות/שאריות האפשריות. לכן \overline{a^n} = \overline{a^m} כאשר 0\le n<m.
  • מכאן אפשר להסיק שהסדרה נהיית מחזורית החל מנקודה מסויימת, עם מחזור m-n (או מספר שמחלק אותו), הרי לכל k \ge 0 נקבל: a_{k+m}=\overline{a^{k+m}}=\overline{a^k}\cdot\overline{a^m}=\overline{a^k}\cdot\overline{a^n}=a_{k+n}, כלומר במרחק m-n=(k+m)-(k-n) האיברים שווים.
  • כעת נשתמש בעובדה שלא הוכחתי עד כה, והיא שניתן לצמצם בחשבון מודולרי כאשר המודולוס (modulus – המספר שביחס אליו מחשבים את השארית) ראשוני. כלומר, אם \overline{ab} = \overline{ac} אז \overline{b}=\overline{c} בהינתן ש\overline{c}\neq\overline{0}. ההוכחה קצרה ונובעת מההגדרה אלטרנטיבית (ובמובנים מסויימים – נכונה וכללית יותר) של ראשוניות שהיא כדלהלן: n ראשוני כאשר n|ab גורר n|a או n|b, לכל a,b שלמים (x|y משמעו: x מחלק את y).
  • עובדה זה נותנת לנו ש\overline{1}=a_0=a_{m-n}=\overline{a^{m-n}} כאשר \overline{a} \neq \overline{0}, או: a לא מתחלק בp. כלומר, ביחד עם הנקודה הקודמת, נקבל שהסדרה מחזורית ושכל m-n איברים חוזרים ל\overline{1}. כלומר, לכל מספר a שלא מתחלק בp קיים מספר, שנסמנו ord_p(a) המקיים: a^{ord_p(a)}-1 מתחלק בp. זה ניסוח שכבר מזכיר המשפט הקטן. המשפט הקטן טוען בנוסף שord_p(a) | p-1, כלומר שכל המספרים האלה מחלקים את p-1. זה שקול לכך שיש מחזור גדול – p-1 – שכל שאר המחזורים מחלקים אותו. זה משהו שאפשר לגלות בחישובים עבור pים קטנים. שאלה מעניינת אפשרית היא: האם קיים a שעבורו המחזור הוא בדיוק p-1? מתברר שכן, אבל זו בעיה שונה באופיה. זה שקול לכך שיש מספר שהחזקות שלו מניבות את כל המחלקות – מעניין. בטרמינולוגיה אלגברית זה אומר שהחבורה (\mathbb{Z}/p\mathbb{Z})^{\times} ציקלית.

בחלקים הבאים: הוכחות, הכללות ומשפטים הפוכים.

לקריאה נוספת:

מספרי קרמייקל – קצת רקע, דוגמאות ומסקנות.

מבחן מילר-רבין – פוסט ישראלי על אלגוריתם חצי-ישראלי.

מבחן הראשוניות AKS – כך נראה מאמר אמיתי.


פינת החידה ה(פונקציה-של-תדירות-הכתיבה)יומית:

חידה יפה מתוך תחרות המתמטיקה הבינלאומית, שנת 2005. השאלה הראשונה של היום השני – כלומר שאלה קלה, אבל לא קלה מידי. החידה הולכת כך:

מוגדרת הסדרה a_n=2^n+3^n+6^n-1, עבור n\ge1. מצאו את כל המספרים הטבעיים שזרים לכל איברי הסדרה בו-זמנית (תזכורת: מספרים הם זרים אם אין להם גורמים משותפים מלבד 1).


נתראה בשמחות ובמדורי הרכילות,

פרנקו

נ.ב.: דיון בתגובות הוא דבר מומלץ ומבורך. אל תנסו רק בבית, תנסו גם בבלוג.

מודעות פרסומת

אודות Ofir Gorodetsky

Graduate student at TAU. Can be contacted at bambaman1 at gmail dot com.
פוסט זה פורסם בקטגוריה המשפט הקטן של פרמה, חפירה, תורת המספרים, עם התגים , , , , , . אפשר להגיע ישירות לפוסט זה עם קישור ישיר.

3 תגובות על המשפט הקטן של פרמה – 0. הקדמה

  1. Mila הגיב:

    Why don't you write it in English so that the rest of the world can understand?

  2. אופי הגיב:

    כתבה מעולה . כמה חוכמה

  3. מיכל הגיב:

    תודה רבה- אתה כותב יפה מאוד- נקודת מבט שונה ממה שהכרתי עד עכשיו על המשפט הקטן של פרמה…

כתיבת תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s