משוואות דיופנטיות, ולמה בגללן אנחנו מתעניינים במספרים p-אדיים?

לפעמים מתקבל הרושם השגוי שמה שהמתמטיקאים עוסקים בו הוא “פתרון משוואות”. לכן מחשבים אנושיים שמסוגלים לומר מהו השורש השביעי של 5434245346 תוך חלקיק שניה נחשבים מייד לעילויי מתמטיקה. כמובן שהמתמטיקה ה”אמיתית” אינה כזו, ועם זאת העיסוק במשוואות הוא עדיין מרכזי מאוד במתמטיקה - אך באיזה מובן? מה שהמתמטיקאי עושה איננו לפתור משוואות ספציפיות על ידי הפעלה של אלגוריתם ידוע כלשהו - הוא עוסק במציאת דרכים לפתור משוואות, בפיתוח אלגוריתמים חדשים למציאת הפתרון, ובחקירת התכונות של הפתרונות.

הדוגמה הקלאסית היא משוואות ממעלה שניה. כל תלמיד תיכון יודע שכדי למצוא את פתרונות המשוואה \( ax^{2}+bx+c=0 \) יש לחשב את \( \frac{-b\pm\sqrt{b^{2}-4ac}}{2a} \), וחלק נכבד מלימודי המתמטיקה בתיכון מוקדש להצבת דברים בנוסחה זו. המתמטיקאי לא מציב בנוסחה זו להנאתו; כשהוא אומר שהוא “פותר משוואות ממעלה שנייה”, כוונתו לכך שהוא מוצא את הנוסחה הזו מלכתחילה. ואכן, על פניו לא ברור למה הנוסחה עובדת בכלל; יש כאן מין “קסם”, שמהנוסחה המפחידה הזו יוצאים הפתרונות של המשוואה. זהו תפקידו של המתמטיקאי לגלות את הקסם ולתרגם אותו לשיטת פעולה פשוטה יחסית - במקרה זה, הצבה בנוסחה.

בפוסט הזה ובהמשכים שלו אני רוצה להתמקד במחלקה מיוחדת וחשובה ביותר של משוואות - משוואות דיופנטיות. משוואה דיופנטית היא משוואה בנעלם אחד או יותר, שכל המקדמים בה הם מספרים שלמים, והפתרונות שאנו מחפשים גם הם מספרים שלמים (לעתים מרשים גם מספרים רציונליים כי ניתן לתרגם משוואה רציונלית שכזו למשוואה בשלמים, אבל ברשותכם לא אכנס לכך). משוואות דיופנטיות הן טבעיות מאוד, כי המספרים שאנו פוגשים בחיי היום-יום הם מספרים שלמים (ורציונליים), ופתרונות שאינם שלמים לרוב אינם מועילים לנו. דוגמה חביבה לכך היא בעיית כדורי התותח: נשאלת השאלה האם ניתן לקחת קבוצת כדורי תותח המסודרת על הקרקע בריבוע מושלם (כלומר, אין בו חורים של כדורים חסרים), ולבנות מהם פירמידה מושלמת (פירמידה במקרה זה מורכבת מריבוע עם אורך צלע \( k \) של כדורים, שעליו מושם ריבוע עם אורך צלע \( k-1 \) וכן הלאה). כלומר, השאלה היא האם קיימים \( k,n \) כך ש-\( \sum_{i=1}^{k}i^{2}=n^{2} \). נוסחה ידועה עבור הסכום שבאגף שמאל נותנת את המשוואה \( \frac{k\left(k+1\right)\left(2k+1\right)}{6}-n^{2}=0 \). זוהי משוואה בשני נעלמים עם מקדמים רציונליים - את המקדמים הרציונליים אפשר לבטל על ידי הוצאת גורם משותף, כך שמתקבלת בסופו של דבר המשוואה הדיופנטית הבאה: \( k\left(k+1\right)\left(2k+1\right)-6n^{2}=0 \). מן הסתם פתרון שאיננו שלם למשוואה הזו הוא חסר טעם - אנחנו לא יכולים להשתעשע עם מחצית כדור תותח, או עם \( \frac{1}{\pi} \) כדור תותח. אם כן, מהם פתרונות המשוואה? אפשר לגלות על ידי ניסוי וטעייה ש-\( \left(1,1\right) \) ו-\( \left(24,70\right) \) הם פתרונות, אבל האם קיימים עוד? מסתבר שלא, אך ההוכחה אינה פשוטה בכלל.

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

דוגמה: המשפט האחרון של פרמה. המשוואה הדיופנטית \( x^{2}+y^{2}=z^{2} \) ניתנת לפתרון - למעשה, יש לה אינסוף פתרונות, וזו שאלה מעניינת (אם כי בעלת תשובה פשוטה יחסית) למצוא את כולם. והנה בא פרמה וטען שהוא סגר את כל המשוואות הדומות: שכל משוואה מהצורה \( x^{n}+y^{n}=z^{n} \) אינה ניתנת לפתרון כאשר \( n \) טבעי גדול מ-2. נדרשו כ-300 שנים להוכחת הטענה הזו, כשבאמצע הדרך מומצא התחום של תורת המספרים האלגברית כדי לטפל במקרים פרטיים שלה. הפתרון מגיע בסופו של דבר מתחום שעוסק בפתרונות של משוואות דיופנטיות אחרות - משוואות מהצורה \( y^{2}=x^{3}+ax+b \) - “עקומים אליפטיים”. למעשה, בהקשר של משפט פרמה העניין הוא בפתרונות רציונליים של המשוואה ולא רק שלמים, אך גם לזה לא אוכל להיכנס כרגע.

עוד דוגמה יפה במיוחד היא משוואת פל - משוואה מהצורה \( x^{2}-Dy^{2}=1 \) עבור \( D \) שאינו ריבוע (יש עוד הכללות שלה - ה-1 באגף ימין יכול להיות מוחלף במספרים אחרים, במחיר סיבוך של התורה). המשוואה הזו נראית לא מזיקה ממבט ראשון, אבל יש לה נטייה לצוץ בהקשרים רבים ושונים. אחד מהחביבים עלי הוא בחידה מס’ 100 מפרויקט אוילר: יש קופסה עם כדורים אדומים וכחולים, ואנו שולפים שניים באקראי. מה צריך להיות הרכב הכדורים בתיבה כדי שההסתברות ששני הכדורים שישלפו יהיו כחולים תהיה בדיוק חצי? הרכב אפשרי אחד הוא של 15 כדורים כחולים ו-6 כדורים אדומים, אבל יש מן הסתם הרכבים רבים נוספים. אפשר לתרגם באופן מסויים את מציאתם למציאת פתרונות עבור משוואת פל מסויימת (עם מינוס 1 באגף ימין ולא 1, אך ההבדל כאמור אינו כה גדול).

למשוואת פל (כפי שראיתם, מדובר בעצם על “משפחה” של משוואות, כתלות ב-\( D \) ואולי גם במה שבאגף ימין) יש תורה מפותחת ויפה, שעליה באמת נכתבו ספרים שלמים. בבסיסה, הרעיון הוא כזה: למשוואה יש אינסוף פתרונות, שאחד מהם, שהוא במובן מסויים הקטן ביותר, “מייצר” את כל היתר (ניתן לחשוב עליהם כעל חזקה שלו, כשחושבים על הפתרונות כאיברים בתוך הרחבה מסויימת של המספרים השלמים). כדי למצוא את הפתרון היסודי הזה משתמשים בשיטות שמערבות את התורה של שברים משולבים. בקיצור, כיף חיים. ארחיב על כך בפוסט נפרד מתישהו.

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

ראשית, שימו לב שמשוואה דיופנטית הופכת למעניינת רק מרגע שיש בה שני משתנים או יותר. אם \( p\left(x\right) \) הוא פולינום במשתנה יחיד, אז אין קושי מהותי למצוא את כל השורשים שלו תוך שימוש בשיטות אנליטיות (ניוטון-רפסון, למשל) - ולבדוק פרטנית לכל שורש האם הוא מספר שלם או לא (ניוטון-רפסון נותן רק קירוב וכשאנו עובדים במחשב יש לנו דיוק מוגבל; אבל אם קיבלנו שהשורש הוא בערך 4.0000001, נוכל פשוט להציב 4 בפולינום ולבדוק אם קיבלנו אפס). הסיבה שבגללה זה כל כך קל היא שיש ל-\( p\left(x\right) \) מספר סופי של שורשים (לכל היותר כדרגת \( p \)). לעומת זאת, למשוואה בשני נעלמים ויותר יכולים להיות אינסוף פתרונות (כך המצב במשוואת פל, למשל) ולכן שיטה אנליטית כמו זו שהצעתי עובדת הרבה פחות טוב. אם קיים פתרון, אז המצב לא כל כך גרוע - תמיד אפשר יהיה למצוא אותו, ולו על ידי בדיקה סדרתית של כל ההצבות האפשריות למשתנים; מה שמעניין אותנו הוא לגלות מתי למשוואה אין בכלל פתרון (אני כמובן מגזים - אחד מהדברים החשובים במשוואת פל הוא שכל כך קל לחשב את הפתרונות).

בואו נביט לרגע במשוואה \( 2x+4y=3 \). האם קיים למשוואה פתרון? מייד אפשר לראות שהתשובה שלילית. למה? כי המספר שבאגף ימין אי זוגי, ואילו לא משנה מה נציב בתור \( x,y \) באגף שמאל, נקבל שם מספר זוגי.

באופן דומה גם למשוואה \( 3x^{2}+9y^{17}=5 \) אין פתרון, הפעם בגלל תכונת התחלקות ב-3. הדרך לטפל באופן מסודר בכללי האצבע הללו היא להסתכל על המשוואות מודולו מספר כלשהו \( n \).

חשבון מודולו \( n \) דומה לחשבון רגיל, תחת המגבלה שאחרי שאנו מבצעים פעולה כלשהי אנו מחלקים את התוצאה ב-\( n \) ולוקחים רק את השארית. כך למשל אם \( n=7 \), אז תוצאת החיבור \( 5+3 \) היא 1, כי \( 5+3=8 \) וכאשר מחלקים \( 8 \) ב-\( 7 \) מקבלים 1. שני מספרים הם שווים מודולו \( n \) אם הם מחזירים את אותה שארית בחלוקה ב-\( n \); כך למשל \( 3\equiv_{7}10 \). הרעיון בחשבון מודולו \( n \) הוא להצטמצם לדיון על אוסף השאריות האפשריות בחלוקה ב-\( n \) - בדיוק המספרים \( 0,1,2,\dots,n-1 \). משוואה דיופנטית שמסתכלים עליה מודולו \( n \) היא קלה הרבה יותר לפתרון ממשוואה דיופנטית רגילה, מהטעם הפשוט שיש רק מספר סופי של הצבות ערכים אפשריות לבדוק (אם אנחנו עובדים מודולו \( n=7 \) וכבר הצבנו \( x=3 \), אין טעם להציב גם \( x=10 \) למשל, כי נקבל את אותה תוצאה). למשל, הבה ונביט במשוואה \( 3x\equiv_{7}5 \) - אפשר פשוט להציב בה את כל המספרים מ-0 ועד \( 6 \) ולראות מתי נקבל 5 (למשל, עבור \( x=4 \) נקבל ש-\( 3x=12\equiv_{7}5 \)).

האבחנה המרכזית כאן היא שאם משוואה דיופנטית כלשהי היא פתירה בשלמים, אז היא בוודאי פתירה מודולו \( n \) לכל \( n \) (למה?). לכן אם נצליח למצוא ולו \( n \) אחד ויחיד כך שהמשוואה אינה פתירה מודולו \( n \), ינבע מכך שאין לה פתרון כלל. לרוע המזל, ההפך אינו נכון - קיימות משוואות שהן פתירות מודולו כל \( n \) אך למרות זאת אין להן פתרון בשלמים. עם זאת, זו עדיין התקדמות כלשהי, שגם מציגה את דרך העבודה הכללית בתורת המספרים: כדי להגיד משהו מעניין על המספרים השלמים, אנחנו עוברים לבחון את הבעיה בתוך אוסף מספרים אחר (במקרה הזה, אוסף השאריות מודולו \( n \), שמסומן בדרך כלל ב-\( \mathbb{Z}_{n} \)).

האם באמת צריך לנסות ולפתור את המשוואה מודולו כל \( n \)? ובכן, לא. כאן נכנס לעזרתנו משפט מתורת המספרים - “משפט השאריות הסיני”. בבסיסו, המשפט אומר שאם \( n=ab \) כאשר \( a,b \) זרים זה לזה - אין להם מחלק משותף גדול מ-1, אז משוואה היא פתירה מודולו \( n \) אם ורק אם היא פתירה מודולו \( a \) ופתירה מודולו \( b \). למעשה, כיוון אחד כאן הוא טריוויאלי - אם המשוואה פתירה מודולו \( n \) אותו פתרון טוב הן מודולו \( a \) והן מודולו \( b \) - הכוח של המשפט נעוץ בכך שהוא מראה כיצד ניתן לבנות מפתרון אחד למשוואה מודולו \( a \) ומפתרון אחר למשוואה מודולו \( b \) פתרון “משולב” עבור המשוואה מודולו \( n \) (ליתר דיוק, זה לא בדיוק מה שהמשפט אומר אלא תוצאה כמעט מיידית שלו).

הנה דוגמה: נניח ש-\( n=119 \), כלומר \( a=7,b=17 \) במקרה זה, ואנו מתבוננים במשוואה \( x^{2}=2 \). לא קשה לראות שמודולו 7 המשוואה הזו פתירה עם \( x=3 \), ואילו מודולו 17 המשוואה הזו פתירה עם \( x=6 \). מהו הפתרון מודולו 119? על ידי חיפוש ממצה אפשר לגלות ש-11 הוא פתרון שכזה, אולם משפט השאריות הסיני (שכבר תיארתי בעבר ולכן לא אפרט עליו כעת) נותן לדרך “לבנות” את 11 באופן אלגוריתמי ויעיל מתוך שני הפתרונות הידועים.

המשפט ניתן להכללה ללא קושי עבור כל פירוק של \( n \) לגורמים זרים זה לזה; ולכן הדבר המתבקש ביותר הוא להסתכל על הפירוק ה”מקסימלי” של \( n \), לכמה שיותר גורמים - דהיינו, פירוק לראשוניים. \( n=p_{1}^{k_{1}}\dots p_{t}^{k_{t}} \). מהפירוק הזה עולה שמספיק לבדוק האם המשוואה פתירה מודולו \( p_{i}^{k_{i}} \) לכל \( 1\le i\le t \) כדי לגלות אם היא פתירה מודולו \( n \). אי אפשר לפרק גם את \( p_{i}^{k_{i}} \) למכפלות קטנות יותר של \( p_{i} \), שכן אז נקבל מספרים שאינם זרים זה לזה (\( p \) ו-\( p^{2} \) הם בעלי מחלק משותף גדול מ-1: \( p \)).

אם כן, הדיון שלנו הצטצמם כעת לבחינת משוואות מודלו \( p^{n} \) כאשר \( p \) ראשוני ו-\( n \) טבעי כלשהו. האינטואיציה הראשונה היא לעסוק במשוואה מודולו \( p \), ולראות האם בהינתן פתרון מודולו \( p \) ניתן לבנות ממנו פתרון גם עבור מודולו \( p^{2} \), וממנו פתרון עבור \( p^{3} \) וכן הלאה. הסיבה לכך שעבודה מודולו \( p \) היא קורצת כל כך היא שלאוסף המספרים מודולו \( p \), \( \mathbb{Z}_{p} \), יש מבנה מוצלח במיוחד: הם מהווים שדה - סגורים לכל ארבע פעולות החשבון. עבור חזקות של ראשוניים זה כבר לא עובד כך (אלו מכם שלמדו על שדות סופיים ודאי זוכרים שכל שדה סופי מכיל \( p^{n} \) איברים, עבור \( p \) ראשוני ו-\( n \) טבעי, אבל חשוב להבין ש-\( \mathbb{F}_{p^{n}} \) שונה במבנהו מהקבוצה \( \mathbb{Z}_{p^{n}} \); בתור התחלה, ב-\( \mathbb{Z}_{p^{n}} \) ישנם איברים שונים מאפס שמכפלתם נותנת 0, למשל \( p \) ו-\( p^{n-1} \); ב-\( \mathbb{F}_{p^{n}} \) אין דבר כזה).

ובכן, זו התחלה טובה, והיא תיתן לנו אינטואיציה לגבי המשך הדרך - ובסופה של הדרך נגיע לשדה אחר של מספרים, שמכיל בתוכו את המספרים הרציונליים, והאיברים ה”שלמים” בו הם מעין הכללה של המספרים השלמים הרגילים, ואשר מקיים את התכונה שאם משוואה היא פתירה בו בשלמים (ה”שלמים” של אותו שדה, לא השלמים הרגילים) אז אותה משוואה פתירה בשלמים “רגילים” מודולו \( p^{n} \), לכל \( n \). כלומר, אברי השדה הזו מקודדים איכשהו מידע על כל מה שקורה ב-\( \mathbb{Z}_{p^{n}} \), לכל \( n \). לשדה בעל התכונה המעניינת הזו קוראים שדה המספרים ה-p-אדיים (כפי שהשם מרמז, קיים כזה לכל \( p \) ראשוני), ואותו אציג בפוסט הבא.