משוואת פל

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

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

אז על מה מדובר? על משוואה שנראית כך:

\( x^{2}-Ny^{2}=1 \)

כאשר \( x,y \) הם משתנים ואילו \( N \) הוא פרמטר, כלומר מספר קבוע כלשהו, שהוא מספר שלם חיובי. עבור פרמטרים שונים נקבל משוואות שונות, למשל:

\( x^{2}-2y^{2}=1 \)

זו דוגמה קונקרטית אחת למשוואת פל, עם \( N=2 \), ואילו

\( x^{2}-7y^{2}=1 \)

היא דוגמה אחרת, עבור \( N=7 \).

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

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

השאלה הבאה, שהיא קצת יותר מעשית, היא “איך פותרים את המשוואה?”. אבל מה זה בעצם אומר, לפתור את המשוואה? למצוא זוג ערכים של \( x,y \) שמקיימים את המשוואה? להכריע אם קיים או לא קיים זוג כזה? למצוא כמה זוגות כאלו יש? למצוא אלגוריתם שמייצר סדרתית את כל הפתרונות? להבין את המבנה האלגברי שלהם, אם קיים כזה? כל אלו הן תשובות אפשריות; מה שיפה במשוואת פל הוא שיש תשובה משביעת רצון לכולן.

נתחיל בדברים הברורים מאליהם. למשוואה תמיד יש פתרון שבו \( x=1 \) ו-\( y=0 \). הפתרון הזה מכונה “הפתרון הטריוויאלי” והוא לא מעניין במיוחד, אז לא נדבר עליו יותר. האתגר הוא למצוא פתרונות שבהם גם \( x \) וגם \( y \) הם חיוביים. עכשיו, אם \( N \) הוא בעצמו ריבוע של מספר כלשהו, אז \( x^{2}-Ny^{2} \) הוא הפרש של שני ריבועים; ההפרש הקטן ביותר של שני ריבועים שונים הוא 3 (\( 2^{2}-1^{2} \)) ובאופן כללי הוא יהיה גדול יותר, כי \( a^{2}-b^{2}=\left(a-b\right)\left(a+b\right) \) ועבור שני מספרים חיוביים שונים, \( a+b \) יהיה לפחות 3. לכן למשוואה אין פתרון לא טריוויאלי אם \( n \) הוא ריבוע, ולכן מראש מדברים על המשוואה רק במקרה שבו \( n \) אינו ריבוע. במקרה זה למשוואה יש אינסוף פתרונות, תמיד. מהם הפתרונות הללו ואיך מוצאים אותם - זה מה שאני רוצה לדבר עליו בפוסט הזה.

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

המתמטיקאים ההודי בראהמגופטה גילה, אי שם במאה ה-7 לספירה, שאם יש לנו שני פתרונות למשוואה \( x^{2}-Ny^{2}=1 \) אז אפשר “לבנות” מהם פתרון חדש, באופן הזה: נסמן את הפתרונות בתור \( \left(x_{1},y_{1}\right),\left(x_{2},y_{2}\right) \), אז מתקיימת המשוואה הבאה:

\( \left(x_{1}^{2}-Ny_{1}^{2}\right)\left(x_{2}^{2}-Ny_{2}^{2}\right)=\left(x_{1}x_{2}+Ny_{1}y_{2}\right)^{2}-N\left(x_{1}y_{2}+x_{2}y_{1}\right)^{2} \)

מה קורה כאן? מכיוון ש-\( \left(x_{1},y_{1}\right) \) ו-\( \left(x_{2},y_{2}\right) \) הם פתרונות למשוואת פל עם הפרמטר \( N \), אגף שמאל הוא פשוט 1 כפול 1; אגף ימין, לעומת זאת, נראה כמו משוואת פל - משהו בריבוע פחות \( N \) כפול משהו אחר בריבוע. מכאן שקיבלנו פתרון חדש של משוואת פל: \( \left(x_{1}x_{2}+Ny_{1}y_{2},x_{1}y_{2}+x_{2}y_{1}\right) \).

כדי לראות שהנוסחה נכונה אפשר פשוט לפתוח סוגריים ולבדוק, אבל זה מזוויע. תחת זאת, אפשר לתת לה פירוש אלגברי מודרני יותר. אלו מכם שמכירים מספרים מרוכבים אולי מרגישים שהפתרון החדש הוא בעל צורה שמזכירה מאוד כפל של מרוכבים; זה לא מקרי. הרעיון הוא שאת הביטוי \( x^{2}-Ny^{2} \) אפשר לפרק לשני חלקים: \( x^{2}-Ny^{2}=\left(x+\sqrt{N}y\right)\left(x-\sqrt{N}y\right) \). אם \( N \) איננו ריבוע אז \( \sqrt{N} \) כלל לא יהיה מספר שלם (ואפילו לא מספר רציונלי). מנקודת מבט אלגברית, זה הופך ביטוי כמו \( x+\sqrt{N}y \) למעניין יותר. המתמטיקאים מתחילים לדבר בשלב הזה על קבוצת כל המספרים מהצורה \( x+y\sqrt{N} \) כאשר \( x,y \) הם שלמים, ולנסות להבין עד כמה הקבוצה הזו דומה למספרים השלמים ועד כמה היא שונה. זה אחד מהדברים הבסיסיים שבהם עוסקת תורת המספרים האלגברית; לקבוצה \( \mathbb{Z}\left[\sqrt{N}\right]=\left\{ x+y\sqrt{N}\ |\ x,y\in\mathbb{Z}\right\} \) קוראים חוג השלמים של שדה המספרים \( \mathbb{Q}\left(\sqrt{N}\right) \) (אני משקר כאן קצת - אם \( N \) שקול ל-1 מודולו 4 חוג השלמים של \( \mathbb{Q}\left(\sqrt{N}\right) \) הוא מסובך יותר, אבל זה לא יהיה מהותי עבורנו). דיברתי קצת על תורת המספרים האלגברית בעבר בבלוג, אבל לא הגעתי אז אל המשפט ה”כבד” (יחסית; זה אחד מהמשפטים הרציניים הראשונים שמציגים בכל מבוא לתחום) שבו אני רוצה להשתמש עכשיו.

כשאומרים ש-\( \mathbb{Z}\left[\sqrt{N}\right] \) הוא “חוג”, למה הכוונה? לכך שיש פעולות חיבור וכפל על איברי החוג שמתנהגות כפי שאנו מצפים מחיבור וכפל להתנהג - חוקי הקיבוץ, החילוף והפילוג מתקיימים. בואו נניח שיש לנו שני מספרים, \( x_{1}+y_{1}\sqrt{N} \) ו-\( x_{2}+y_{2}\sqrt{N} \). הסכום שלהם הוא

\( \left(x_{1}+y_{1}\sqrt{N}\right)+\left(x_{2}+y_{2}\sqrt{N}\right)=\left(x_{1}+x_{2}\right)+\left(y_{1}+y_{2}\right)\sqrt{N} \)

כאן השתמשנו בחוקי החילוף, הקיבוץ והפילוג של מספרים שלמים “רגילים” וראינו שחיבור פועל “רכיב רכיב” (אפשר לכתוב מספר מהצורה \( x+y\sqrt{N} \) באופן מקוצר כ-\( \left(x,y\right) \); האיבר השמאלי הוא “הרכיב השמאלי” והימני הוא “הרכיב הימני” ואז פעולת החיבור מקיימת \( \left(x_{1},y_{1}\right)+\left(x_{2},y_{2}\right)=\left(x_{1}+x_{2},y_{1}+y_{2}\right) \)). כפל, לעומת זאת, יתנהג באופן קצת יותר מורכב - בואו פשוט נבצע את החישוב:

\( \left(x_{1}+y_{1}\sqrt{N}\right)\left(x_{2}+y_{2}\sqrt{N}\right)=x_{1}x_{2}+\left(y_{1}\sqrt{N}\right)x_{2}+x_{1}\left(y_{2}\sqrt{N}\right)+\left(y_{1}\sqrt{N}\right)\left(y_{2}\sqrt{N}\right) \)

\( =x_{1}x_{2}+x_{2}y_{1}\sqrt{N}+x_{1}y_{2}\sqrt{N}+y_{1}y_{2}N=\left(x_{1}x_{2}+Ny_{1}y_{2}\right)+\left(x_{1}y_{2}+x_{2}y_{1}\right)\sqrt{N} \)

נראה מוכר? זה בדיוק מה שהופיע באגף ימין משוואה של בראהמגופטה. במילים אחרות, עכשיו אפשר לנסח את התגלית של בראהמגופטה כך: אם אנחנו חושבים על פתרון \( \left(x,y\right) \) למשוואת פל בתור האיבר \( x+y\sqrt{N} \) בחוג השלמים \( \mathbb{Z}\left[\sqrt{N}\right] \), אז גם מכפלה של פתרונות (עם פעולת הכפל של \( \mathbb{Z}\left[\sqrt{N}\right] \)) היא פתרון.

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

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

בפועל, עבור \( \mathbb{Z}\left[\sqrt{N}\right] \), להגדרה הזו יש משמעות מאוד פשוטה: הנורמה של \( x+y\sqrt{N} \) היא המכפלה שלו באיבר \( x-y\sqrt{N} \) (ה”צמוד” שלו), וחישוב מהיר מראה שזה יוצא \( x^{2}-Ny^{2} \). במילים אחרות, איבר של \( \mathbb{Z}\left[\sqrt{N}\right] \) הוא פתרון של משוואת פל אם ורק אם הוא מנורמה 1. עכשיו, מההגדרה הכללית של נורמה נובע די בקלות שהיא כפלית, כלומר הנורמה של מכפלה של איברים היא מכפלת הנורמות שלהם (\( \mbox{Norm}\left(\alpha\cdot\beta\right)=\mbox{Norm}\left(\alpha\right)\cdot\mbox{Norm}\left(\beta\right) \)). אם כופלים שני איברים מנורמה 1, אז הנורמה של המכפלה גם כן תהיה 1, ולכן גם היא תהיה פתרון למשוואת פל - הופס! הוכחנו את בראהמגופטה בלי להיכנס לחישובים טכניים (כמובן, נפנפתי את העניין הזה שנורמה היא תמיד כפלית, וגם את זה שאנחנו יודעים מה הנורמה של איבר ב-\( \mathbb{Z}\left[\sqrt{N}\right] \), אבל סמכו עלי שאין שם סיבוך טכני). לא רק שהוכחנו, עכשיו אנחנו גם מבינים יותר טוב מה הולך כאן, והצלחנו להמיר את הבעיה של הכרת המבנה של אוסף הפתרונות של משוואת פל לבעיה אחרת - הבנת המבנה של קבוצת האיברים ב-\( \mathbb{Z}\left[\sqrt{N}\right] \) שהם מנורמה 1.

עכשיו, אם איבר הוא מנורמה 1, אז הוא הפיך (אפשר לכפול אותו במשהו ולקבל 1 - זה נובע מכך שהנורמה היא מכפלת איבר בכל הצמודים שלו, אז מכפלת כל הצמודים הזו היא בדיוק ההופכי). לרוע המזל, ההפך לא נכון - איבר הפיך יכול להיות גם מנורמה \( -1 \). עם זאת, היתרון שבלעבור לדבר על הבעיה של הבנת המבנה של קבוצת כל ההפיכים ב-\( \mathbb{Z}\left[\sqrt{N}\right] \) הוא שעכשיו אפשר להכניס לתמונה את המשפט ה”כבד” שדיברתי עליו - משפט ההפיכים של דיריכלה (באנגלית זה Dirichlet Unit Theorem כאשר Unit הוא השם המקובל לאיבר הפיך בחוג; אני מעדיף לתרגם בתור “משפט ההפיכים” מאשר בתור “משפט היחידות” שנשמע יותר מדי כמו “Uniqueness Theorem’’).

מהמשפט הזה נובע שאת כל ההפיכים ב-\( \mathbb{Z}\left[\sqrt{N}\right] \) ניתן לקבל על ידי כך שמתחילים מאיבר הפיך ספציפי (שכבר קראתי לו “הפתרון היסודי” קודם) וכופלים אותו בעצמו, שוב ושוב ושוב. במילים אחרות, כל פתרון הוא חזקה של הפתרון היסודי. פורמלית זה הולך כך: אם \( \left(x_{0},y_{0}\right) \) הוא הפתרון היסודי, אז נגדיר רקורסיבית את הסדרה הבאה:

\( x_{n+1}=x_{n}x_{0}+Ny_{n}y_{0} \)

\( y_{n+1}=x_{n}y_{0}+y_{n}x_{0} \)

וכך נקבל סדרה \( \left(x_{0},y_{0}\right),\left(x_{1},y_{1}\right),\left(x_{2},y_{2}\right),\dots \) שבה נמצאים כל האיברים ההפיכים ב-\( \mathbb{Z}\left[\sqrt{N}\right] \), ולכן בפרט גם את כל הפתרונות למשוואת פל \( x^{2}-Ny^{2}=1 \) (אבל, אם הפתרון היסודי מקיים \( x_{0}^{2}-Ny_{0}^{2}=-1 \), אז גם איברים שאינם פתרון למשוואת פל אם כי הם פותרים משוואה קרובה שגם היא מעניינת לעתים - \( x^{2}-Ny^{2}=-1 \), או אם תרצו \( Ny^{2}-x^{2}=1 \)).

איך זה נובע מהמשפט של דיריכלה? כאן כבר אין מנוס - אני הולך להיות טכני, ומי שיאבד אותי כאן יכול לקפוץ לפסקה הבאה. קל לראות שקבוצת כל ההפיכים בחוג שלמים היא תמיד חבורה, וחבורה אבלית, כי הכפל בחוג הוא קומוטטיבי. עכשיו, כל חבורה אבלית איזומורפית לחבורה מהצורה \( \mathbb{Z}^{r}\times\mathbb{Z}_{k_{1}}\times\dots\times\mathbb{Z}_{k_{t}} \), כאשר \( \mathbb{Z}^{r} \) נקרא הרכיב החופשי של החבורה ו-\( r \) נקרא המימד שלו, ואילו \( \mathbb{Z}_{k_{1}}\times\dots\times\mathbb{Z}_{k_{t}} \) נקרא הפיתול של החבורה - החלק בה שמכיל את האיברים מסדר סופי (אפשר אפילו להגיד עוד משהו על הקשר בין ה-\( k_{i} \)-ים השונים, אבל זה לפוסט אחר). בחבורה האבלית של ההפיכים של חוג שלמים כלשהו, הפיתול כולל בדיוק את שורשי היחידה בחוג הזה; ב-\( \mathbb{Z}\left[\sqrt{N}\right] \) מדובר רק על \( \left\{ 1,-1\right\} \) כך שהפיתול לא מעניין במיוחד. מה שמעניין הוא \( r \). משפט היחידה של דיריכלה מצביע על ערכו של \( r \): הוא שווה ל-\( r_{1}+r_{2}-1 \), כאשר \( r_{1} \) הוא מספר השיכונים של \( \mathbb{Q}\left(\sqrt{N}\right) \) ב-\( \mathbb{R} \) ו-\( r_{2} \) הוא מספר השיכונים של \( \mathbb{Q}\left(\sqrt{N}\right) \) ב-\( \mathbb{C} \), חלקי 2 (שיכונים כאלו תמיד באים בזוגות צמודים, אז סופרים את הזוגות). בפועל, \( r_{1} \) הוא פשוט מספר הצמודים של \( \sqrt{N} \) שהם ממשיים (יש שניים - \( \sqrt{N} \) ו-\( -\sqrt{N} \)) ו-\( 2r_{2} \) הוא מספר הצמודים של \( \sqrt{N} \) שאינם ממשיים (לפעמים קוראים להם “מרוכבים” למרות שזה קצת שקר כי גם ממשי הוא מרוכב). כאן אין ל-\( \sqrt{N} \) צמודים שאינם ממשיים, כך ש-\( r_{1}=2 \) ו-\( r_{2}=0 \) וקיבלנו ממשפט דיריכלה שמבנה חבורת ההפיכים ב-\( \mathbb{Z}\left[\sqrt{N}\right] \) הוא איזומורפי ל-\( \mathbb{Z}\times\left\{ 1,-1\right\} \), וזה מה שרצינו.

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

שבר משולב הוא ביטוי שנראה כך: \( a_{0}+\frac{1}{a_{1}+\frac{1}{a_{2}+\frac{1}{a_{3}+\dots}}} \). במילים אחרות, אפשר לאפיין שבר משולב על ידי סדרה של מספרים \( a_{0},a_{1},a_{2},\dots \) ולא לכתוב את השבר המפחיד בכל פעם מחדש. שבר משולב יכול להיות סופי, כלומר שסדרת המספרים המתאימה לו היא סופית, ואז אפשר לחשב אותו “עד הסוף” ולקבל מספר רציונלי; הוא גם יכול להיות סדרה אינסופית, ואז הוא מגדיר סדרה אינסופית של מספרים רציונליים, שמתכנסת למספר ממשי כלשהו. אפשר להראות שלכל מספר ממשי יש פיתוח כזה כשבר משולב, ואפשר להראות משהו מעניין עוד יותר - שכל מספר ממשי אי רציונלי שהוא פתרון של משוואה ממעלה שניה מתואר על ידי שבר משולב אינסופי שהוא מחזוריהחל ממקום מסוים. למעשה, אפשר להוכיח אפילו יותר מזה! שהשבר המשולב תמיד יהיה מהצורה הבאה - \( a_{0},a_{1},a_{2},\dots,a_{n}\dots,a_{2}a_{1},2a_{0},a_{1},a_{2},\dots \), כלומר הוא יהיה מורכב באופן הבא:

1. איבר התחלתי \( a_{0} \).
2. קטע סימטרי \( a_{1},a_{2},\dots,a_{n},\dots,a_{2},a_{1} \).
3. האיבר ההתחלתי כפול 2: \( 2a_{0} \).

כאשר 2 ו-3 חוזרים על עצמם לאין קץ.

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

מתחילים מהערך השלם התחתון של \( \sqrt{19} \), כלומר \( \left\lfloor \sqrt{19}\right\rfloor =4 \). כן, צריך לחשב אותו - אף אחד לא אמר שאפשר למצוא את השבר המשולב של \( \sqrt{19} \) בלי לעשות חישובים! (איך מוציאים שורש? גם על זה כבר יש לי פוסט). נגדיר \( a_{0}=4 \). עכשיו כותבים:

\( \sqrt{19}=4+\frac{1}{x} \)

איך נמצא את \( x \)? ובכן, נעביר את \( 4 \) אגף, ניקח את ההופכיים של שני האגפים, ונקבל:

\( x=\frac{1}{\sqrt{19}-4} \)

עכשיו נשתמש בתעלול מימי בית הספר - נכפיל מונה ומכנה בצמוד של הביטוי שלמטה (האם עכשיו המילה “צמוד” מצלצלת לכם?), כלומר ב-\( \sqrt{19}+4 \). נקבל:

\( x=\frac{\sqrt{19}+4}{3} \)

לכאורה רק סיבכנו את עצמנו - רצינו למצוא את השורש של 19, ועכשיו קיבלנו מספר שנראה עוד יותר מסובך. עם זאת, אל דאגה! פשוט ממשיכים באותה השיטה לטפל גם בו. ראשית, מחשבים את הערך התחתון שלו: \( \left\lfloor \frac{\sqrt{19}+4}{3}\right\rfloor =2 \). מגדירים \( a_{1}=2 \) וכותבים:

\( \frac{\sqrt{19}+4}{3}=2+\frac{1}{x} \)

איך נמצא את \( x \)? ובכן, באותה שיטת חילוץ! נעביר את 2 אגף ונקבל

\( \frac{1}{x}=\frac{\sqrt{19}+4-6}{3} \)

ניקח הופכי לשני האגפים ונקבל

\( x=\frac{3}{\sqrt{19}-2} \)

נכפול בצמוד \( \sqrt{19}+2 \) ונקבל

\( x=\frac{3\left(\sqrt{19}+2\right)}{15}=\frac{\sqrt{19}+2}{5} \)

ואתם כבר מבינים איך זה נמשך מכאן.

פורמלית, האלגוריתם פועל כך:

מאתחלים משתנים

\( a_{0}=\left\lfloor \sqrt{N}\right\rfloor \)

\( m_{0}=0 \)

\( d_{0}=1 \)

ועכשיו בכל שלב מבצעים את החישובים הבאים:

\( m_{n+1}=a_{n}d_{n}-m_{n} \)

\( d_{n+1}=\frac{N-m_{n+1}^{2}}{d_{n}} \)

\( a_{n+1}=\left\lfloor \frac{\sqrt{N}+m_{n+1}}{d_{n+1}}\right\rfloor \)

מה קורה כאן? ובכן, בשלב \( n \) המספר שאנחנו מנסים לחשב את השבר המשולב שלו הוא \( \frac{\sqrt{N}+m_{n}}{d_{n}} \). אנחנו יודעים שהשבר המשולב הזה הוא מהצורה \( a_{n}+\frac{1}{x} \) ורוצים למצוא את \( x \). כפי שכבר ראינו, יתברר בסוף ש-\( x \) הוא מהצורה \( x=\frac{\sqrt{N}+y}{z} \) כך ש-\( y,z \) הם שלמים, וצריך רק לחשב אותם.

אז \( a_{n} \) יהיה \( \left\lfloor \frac{\sqrt{N}+m_{n}}{d_{n}}\right\rfloor \). עכשיו, אם \( \frac{\sqrt{N}+m_{n}}{d_{n}}=a_{n}+\frac{1}{x} \) אז \( \frac{1}{x}=\frac{\sqrt{N}+m_{n}-a_{n}d_{n}}{d_{n}} \), ולכן \( x=\frac{d_{n}}{\sqrt{N}-\left(a_{n}d_{n}-m_{n}\right)} \). שימו לב שהפכתי את האיבר \( m_{n}-a_{n}d_{n} \) שבמכנה על ידי הוצאת סימן מינוס החוצה, וקיבלתי בדיוק את האיבר שהגדרתי כ-\( m_{n+1} \). כלומר, קיבלנו \( x=\frac{d_{n}}{\sqrt{N}-m_{n+1}} \). עכשיו מגיע שלב הכפל בצמוד, שהוא במקרה שלנו \( \sqrt{N}+m_{n+1} \), ומקבלים \( x=\frac{d_{n}\left(\sqrt{N}+m_{n+1}\right)}{N-m_{n+1}^{2}}=\frac{d_{n}}{N-m_{n+1}^{2}}\left(\sqrt{N}+m_{n+1}\right) \).

עכשיו, מה הוא הגורם \( \frac{d_{n}}{N-m_{n+1}^{2}} \)? שוב, שימו לב להגדרות שלי - זה בדיוק \( \frac{1}{d_{n+1}} \). לכן קיבלנו \( x=\frac{\sqrt{N}+m_{n+1}}{d_{n+1}} \). כלומר, \( y=m_{n+1} \) ו-\( z=d_{n+1} \), כפי שהיה ניתן לצפות, ולכן המשך החישוב הוא בדיוק ביצוע החישוב \( \left\lfloor \frac{\sqrt{N}+m_{n+1}}{d_{n+1}}\right\rfloor \) וכן הלאה.

כזכור, הובטח לנו שהחישוב הופך למחזורי מתישהו. לא ניכנס לפרטי ההוכחה הזו עכשיו; רק נציין שאפשר לזהות מתי זה מתרחש בתוך האלגוריתם עצמו. כפי שראינו, בשלב \( n \) המצב של האלגוריתם מאופיין על ידי שלושה ערכים: \( a_{n},m_{n},d_{n} \). שלושת אלו קובעים את השלב הבא של האלגוריתם (\( a_{n+1},m_{n+1},d_{n+1} \)). האלגוריתם מתחיל לחזור על עצמו בדיוק כשאנחנו חוזרים לשלשה שכבר היינו בה.

חזרה לשורש 19. הפעלת האלגוריתם עליו “עד הסוף” מניבה את השבר המשולב המחזורי הבא: \( \left[4,2,1,3,1,2,8,2,1,3,1,2,8,\dots\right] \), כאשר המספרים הללו הם סדרת ה-\( a_{n} \)-ים. אתם רואים שבאופן לא מפתיע זה מציית לתבנית שתיארתי - \( q_{0}=4 \) הוא החלק ההתחלתי, החלק המחזורי הסימטרי הוא \( 2,1,3,1,2 \), וה-\( 8 \) הוא \( 2q_{0} \).

מה עושים עכשיו?

לוקחים את החלק מהשבר המשולב עד ולא כולל \( 2q_{0} \), כלומר את \( \left[4,2,1,3,1,2\right] \). זה שבר משולב סופי, ולכן הוא מייצג מספר רציונלי שאפשר לחשב עד הסוף. אם נעשה זאת, נקבל \( \frac{170}{39} \). כעת מגדירים \( x=170,y=39 \), מחשבים את \( x^{2}-19y^{2} \) ומגלים, למרבה התדהמה, שקיבלנו 1! מצאנו פתרון למשוואת פל עם הפרמטר \( N=19 \), ולא סתם פתרון - את הפתרון היסודי!

אם המתמטיקה לא נראית לכם כמו קסם אפילו עכשיו, אין לי מושג איך עוד אפשר לשכנע אתכם. כמובן שיש הסבר הגיוני מאחורי כל זה ונראה אותו, אבל בינתיים בואו נעצור לשניה ונעריך את הקסם שיש כאן. אין לי מושג איך הגיעו לתגלית הזו לראשונה (דומני שהיה זה לגראנז’ שהוכיח את הזהות בין שברים משולבים מחזוריים אינסופיים ופתרונות של משוואות ריבועיות, ואילו ברוקנר היה זה שמצא את הקשר בינם לבין משוואת פל, אבל אולי אני טועה), אבל אני מנחש שזה היה בראש ובראשונה על ידי התקלות בתגלית לפיה התופעה המתרחשת הזו מתקיימת - שיש קשר הדוק בין המספרים הרציונליים שמתקבלים בפיתוח לשבר משולב של \( \sqrt{N} \) והפתרונות של משוואת פל עבור הפרמטר \( N \) (המספרים הרציונליים שמתקבלים בפיתוח של \( \sqrt{N} \) הם לא מקריים; בפוסטים על שברים משולבים ניסיתי להסביר למה אלו במובן מסויים “הקירובים הטובים ביותר” של \( \sqrt{N} \) על ידי מספרים רציונליים).

מה שעשיתי עבור \( N=19 \) תקף תמיד, כמובן. בהינתן \( N \), מפתחים את \( \sqrt{N} \) לשבר משולב מחזורי אינסופי, לוקחים את המספר הרציונלי שמתאים לשבר המשולב שמתקבל מעצירת הסדרה המחזורית בדיוק בתום המחזור הראשון שלה, לפני \( q_{0} \); המונה יהיה \( x \) והמכנה יהיה \( y \). הבעיה היחידה היא שלא תמיד יתקיים \( x^{2}-Ny^{2}=1 \), כי עלול להתקיים גם \( x^{2}-Ny^{2}=-1 \), אבל בכל מקרה נקבל את היוצר של כל ההפיכים ב-\( \mathbb{Z}\left[\sqrt{N}\right] \) ולכן נוכל לקבל ממנו את כל הפתרונות.

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

בואו נעבור להסבר של הקסם הזה - הסבר שיהיה כרוך, כמובן, בפרטים טכניים.

טוב, אז בואו נסמן את השבר שמתקבל מהשבר המשולב עד ולא כולל \( 2q_{0} \) בתור \( \frac{A_{n}}{B_{n}} \), ונסמן את השבר שבא לפניו (כלומר, לא כולל האיבר שממש לפני \( 2q_{0} \)) בתור \( \frac{A_{n-1}}{B_{n-1}} \). אנחנו רוצים להוכיח ש-\( A_{n}^{2}-NB_{n}^{2}=\pm1 \). זה מוכיח שאנחנו מקבלים פתרון; זה עדיין לא מוכיח שהוא הפתרון היסודי, אבל זה כבר באמת יהיה קצת יותר מדי עבורנו.

בואו ניזכר בתוצאה שהוכחנו בדי עמל בפוסט הראשון שלי על שברים משולבים: באופן כללי, אפשר לפתח את המספר \( \alpha \) לשבר משולב תוך שאנו מרשים למספר האחרון להיות לא שלם, ומסמנים אותו בסימון \( \alpha_{n+1} \), כלומר \( \alpha=a_{0}+\frac{1}{a_{1}+}\frac{1}{a_{2}+}\cdots\frac{1}{a_{n}+}\frac{1}{\alpha_{n+1}} \). עבור \( \alpha_{n+1} \) הזה הוכחנו שמתקיימת המשוואה

\( \alpha=\frac{\alpha_{n+1}A_{n}+A_{n-1}}{\alpha_{n+1}B_{n}+B_{n-1}} \)

אז בואו נחיל את זה על המקרה שלנו. אצלנו \( \alpha \) הוא \( \sqrt{N} \) שמיוצג על ידי השבר המשולב \( \left[q_{0},q_{1},\dots,q_{n},2q_{0},q_{1},\dots,q_{n},2q_{0},q_{1},\dots\right] \), ואילו \( \frac{A_{n}}{B_{n}}=\left[q_{0},q_{1},\dots,q_{n}\right] \) ו-\( \frac{A_{n-1}}{B_{n-1}}=\left[q_{0},q_{1},\dots,q_{n-1}\right] \), והכי חשוב - \( \alpha_{n+1}=\left[2q_{0},q_{1},\dots,q_{n},2q_{0},q_{1},\dots\right] \). שימו לב כמה הוא דומה ל-\( \sqrt{N} \) - ההבדל היחיד הוא האיבר הראשון, שהוא \( 2q_{0} \) במקום \( q_{0} \). כלומר מתקיים ש-\( \alpha_{n+1}=q_{0}+\sqrt{N} \).

הבה ונציב את כל זה במשוואה שלעיל, ונקבל:

\( \sqrt{N}=\frac{\left(q_{0}+\sqrt{N}\right)A_{n}+A_{n-1}}{\left(q_{0}+\sqrt{N}\right)B_{n}+B_{n-1}} \)

נכפול את שני האגפים במכנה של אגף ימין ונקבל:

\( \sqrt{N}\left(q_{0}+\sqrt{N}\right)B_{n}+\sqrt{N}B_{n-1}=\left(q_{0}+\sqrt{N}\right)A_{n}+A_{n-1} \)

למשוואה הזו תכונה מעניינת - היא למעשה כוללת שתי משוואות שונות. זאת מכיוון שפרט ל-\( \sqrt{N} \), כל שאר המספרים במשוואה הם שלמים, ולכן כפל שלהם ב-\( \sqrt{N} \) מותיר אותו אי רציונלי. אז אפשר לחשוב על המשוואה הזו כאילו היא מהצורה \( a_{1}+b_{1}\sqrt{N}=a_{2}+b_{2}\sqrt{N} \) ולהסיק את זוג המשוואות

\( a_{1}=a_{2} \)

\( b_{1}=b_{2} \)

(נסו להוכיח פורמלית שאכן אפשר להסיק את שתי המשוואות הללו).

במקרה שלנו, אחרי פישוט, נקבל שהמשוואה לעיל יכולה להיכתב כך:

\( NB_{n}+\left(q_{0}B_{n}+B_{n-1}\right)\sqrt{N}=q_{0}A_{n}+A_{n-1}+A_{n}\sqrt{N} \)

ומכאן שתי המשוואות:

\( NB_{n}=q_{0}A_{n}+A_{n-1} \)

\( q_{0}B_{n}+B_{n-1}=A_{n} \)

אפשר מהמשוואות הללו לחלץ את \( A_{n-1} \) ואת \( B_{n-1} \):

\( A_{n-1}=NB_{n}-q_{0}A_{n} \)

\( B_{n-1}=A_{n}-q_{0}B_{n} \)

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

\( A_{n}B_{n-1}-A_{n-1}B_{n}=\left(-1\right)^{n-1} \)

נציב את \( A_{n-1},B_{n-1} \) בנוסחה הזו ונקבל:

\( A_{n}\left(A_{n}-q_{0}B_{n}\right)-B_{n}\left(NB_{n}-q_{0}A_{n}\right)=\left(-1\right)^{n-1} \)

נפתח סוגריים ונקבל:

\( A_{n}^{2}-q_{0}A_{n}B_{n}-NB_{n}^{2}+q_{0}A_{n}B_{n}=\left(-1\right)^{n-1} \)

ולסיום, קיבלנו:

\( A_{n}^{2}-NB_{n}^{2}=\left(-1\right)^{n-1} \)

שזה בדיוק מה שרצינו.

בשבילי כל העסק הזה הוא כל כך Mind Blowing שאני חושב שאעצור כאן לפני שהמקלדת תתפוצץ.