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

בואו נחזור לדבר על הבעיה העשירית של הילברט שעזבתי בשיא המתח - בדיוק לפני החלק הטכני ביותר, שנתחיל לטפל בו הפעם. תזכורת קטנה למי שאין לו כוח לקרוא את הפוסטים הקודמים: המטרה שלנו היא להוכיח שהפונקציה \( f\left(n,k\right)=n^{k} \) - “הפונקציה האקספוננציאלית” - היא דיופנטית. כלומר, שקיימת מערכת של משוואות פולינומיות בשלמים עם המון משתנים ששלושה מהם הם \( n,k,m \) כך שלכל הצבה של ערכים ב-\( n,k,m \), יש פתרון למערכת המשוואות אם ורק אם \( m=n^{k} \). אפשר, כמובן, להתחיל מלהציג את מערכת המשוואות הזו, אבל היא כוללת שתיים-עשרה משוואות ולא מעט משתנים וממבט ראשון לא יהיה ברור מה הולך שם בכלל, אז נחכה עם זה קצת בסבלנות. לפני כן נטפל בבעיה לכאורה לא קשורה, אבל כזו שתוביל אותנו כמעט ישירות אל הפונקציה האקספוננציאלית: משוואת פל.

כחלק מההכנה לפוסט הזה כתבתי פוסט על משוואת פל שאין צורך לחזור על כל מה שנאמר בו (מרטין דיוויס, במאמר על הבעיה העשירית של הילברט שאני מתבסס עליו, מוכיח מאפס את התכונות שהוא צריך באופן ישיר), אבל בואו נחזור על עיקרי הדברים הרלוונטיים. אם \( d \) הוא מספר טבעי שאינו ריבוע, אז משוואת פל עם הפרמטר \( d \) היא המשוואה \( x^{2}-dy^{2}=1 \) (בפוסט שלי השתמשתי ב-\( N \) אבל עכשיו אני הולך לפי סגנון הכתיבה של דיוויס). מה שמעניין במשוואת פל הוא שלפתרונות שלה יש מבנה יפה במיוחד: קיים פתרון אחד שנקרא הפתרון היסודי ונסמן אותו בתור \( \left(x_{1},y_{1}\right) \), כך שכל פתרון אחד מתקבל כמעין חזקה של הפתרון היסודי.

ליתר דיוק, מה שעושים הוא להסתכל על המספר האלגברי \( x_{1}+\sqrt{d}y_{1} \) ולקחת את החזקות שלו, כלומר מגדירים \( x_{n}+\sqrt{d}y_{n}=\left(x_{1}+\sqrt{d}y_{1}\right)^{n} \). למי שאין לו כוח להתעסק עם שורשים אפשר לעשות את זה גם באופן ישיר בצורה הבאה: אם \( \left(x_{n},y_{n}\right) \) ו-\( \left(x_{k},y_{k}\right) \) הם שני פתרונות של משוואת פל, אז אפשר לבנות מהם על ידי “כפל” פתרון חדש \( \left(x_{t},y_{t}\right) \) שנראה כך:

\( x_{t}=x_{n}x_{k}+dy_{n}y_{k} \)

\( y_{t}=x_{n}y_{k}+x_{k}y_{n} \)

זוכרים משהו מזה? יפה. לא זוכרים? לא נורא, זה מה שצריך לזכור. בואו נעבור למה שדיוויס עושה. ראשית כל, למה הוא בכלל מתעניין במשוואת פל? ובכן, מצד אחד זו משוואה דיופנטית פשוטה - תנאי כמו \( x^{2}-dy^{2}=1 \) אפשר לקודד עם האמצעים שמותר לנו להשתמש בהם. מצד שני, הקטע הזה של “כל פתרון הוא חזקה של הפתרון היסודי” מתנהג כמו, ובכן, חזקה. זהו ה”גשר” שאנו זקוקים לו בין משהו דיופנטי ומשהו אקספוננציאלי. לדעתי זה די מגניב שזה נעשה באמצעות משוואת פל.

בשביל הצרכים שלו, דיוויס נזקק רק למשוואות פל מסוג מסויים: משוואות מהצורה \( x^{2}-dy^{2}=1 \) (עד כאן הכל כרגיל) כך ש-\( d=a^{2}-1 \), עבור \( a>1 \) כלשהו. כלומר, המשוואות \( x^{2}-3y^{2}=1 \), \( x^{2}-8y^{2}=1 \), \( x^{2}-15y^{2}=1 \) וכדומה (כזכור, אם \( d \) הוא ריבוע “ממש”, כלומר אם \( d=a^{2} \), אז למשוואה אין פתרונות) למשוואות שבהן \( d=a^{2}-1 \) קל מאוד לתת פתרון: \( x=a,y=1 \) תמיד פותר את המשוואה, שהרי \( a^{2}-\left(a^{2}-1\right)1^{2}=a^{2}-a^{2}+1=1 \). האם זהו הפתרון היסודי, כלומר הפתרון שבעזרת “חזקות” שלו (ביחס לפעולת ה”כפל” שהצגתי למעלה) אפשר לקבל את כל שאר הפתרונות הלא טריוויאליים של המשוואה?

כדי להוכיח את זה מספיק להוכיח שאם \( \left(x,y\right) \) הוא פתרון כלשהו של המשוואה, אז לא ייתכן שמתקיים \( 1<x+y\sqrt{d}<a+\sqrt{d} \), כלמר אין פתרון למשוואה “בין” שני הפתרונות הבסיסיים \( \left(1,0\right) \) ו-\( \left(a,1\right) \). זה מספיק כי אם \( a+\sqrt{d}<x+y\sqrt{d} \), אז בוודאי שגם \( a+\sqrt{d}<\left(x^{2}+dy^{2}\right)+\left(xy+yx\right) \), כלומר החזקה השניה של הפתרון \( \left(x,y\right) \) לא יכולה לתת את \( \left(a,1\right) \), וגם החזקה השלישית וכן הלאה, מה שמאלץ את \( \left(a,1\right) \) להיות הפתרון היסודי.

אם כן, בואו נניח בכשלילה ש-\( \left(x,y\right) \) הוא פתרון של המשוואה שגם מקיים \( 1<x+y\sqrt{d}<a+\sqrt{d} \). כעת, מכיוון שמתקיים \( x^{2}-dy^{2}=1 \) הרי שאפשר לפרק את הביטוי הזה ולקבל

\( \left(x-y\sqrt{d}\right)\left(x+y\sqrt{d}\right)=x^{2}-dy^{2}=1=a^{2}-d=\left(a-\sqrt{d}\right)\left(a+\sqrt{d}\right) \)

בואו נחלק את שני האגפים ב-\( x+y\sqrt{d} \). נקבל:

\( x-y\sqrt{d}=a-\sqrt{d}\cdot\frac{a+\sqrt{d}}{x+y\sqrt{d}}>a-\sqrt{d} \)

כי הרי הביטוי \( \frac{a+\sqrt{d}}{x+y\sqrt{d}} \) הוא גדול מ-1 אם מניחים ש-\( x+y\sqrt{d}<a+\sqrt{d} \). עכשיו, נכפול את שני האגפים במינוס 1, הסימן של אי השוויון יתהפך ולבסוף נקבל:

\( -x+y\sqrt{d}<-a+\sqrt{d} \)

אם נחבר את זה לאי השוויון \( x+y\sqrt{d}<a+\sqrt{d} \) נקבל בסופו של דבר ש-\( 2y\sqrt{d}<2\sqrt{d} \), כלומר \( y<1 \). זה לכשעצמו עדיין לגיטימי - אולי \( y \) שלילי, או אפס? לכן אנו נזקקים לעוד תעלול. נשים לב לכך שעל פי הנחתנו, \( x+y\sqrt{d}>1 \) ולכן \( \left(x-y\sqrt{d}\right)=\frac{1}{x+y\sqrt{d}}<1 \), ולכן \( -x+y\sqrt{d}>-1 \), ואם נחבר את זה ל-\( 1<x+y\sqrt{d} \) נקבל ש-\( 0<y \), כלומר \( 0<y<1 \), כלומר \( y \) בכלל לא מספר שלם, אבל רק מספרים שלמים הם פתרונות חוקיים של משוואת פל. זה מסיים את הסיפור. אני מודה, ההוכחה הזו היא לא הדבר הכי יפה בעולם.

עכשיו, משאנחנו יודעים מהו הפתרון היסודי, אפשר לתת סימון כללי לשאר הפתרונות החיוביים. מכיוון שהמשוואה שלנו תלויה גם ב-\( d \), אבל את \( d \) כתבנו בתור \( a^{2}-1 \), אנחנו משתמשים ב-\( x_{n}\left(a\right) \) ו-\( y_{n}\left(a\right) \) כדי לתאר את הפתרונות. פורמלית הסדרות הללו מוגדרות כך: \( x_{0}\left(a\right)=1,y_{0}\left(a\right)=0 \), ובאופן אינדוקטיבי:

\( x_{n+1}\left(a\right)=ax_{n}\left(a\right)+dy_{n}\left(a\right) \)

\( y_{n+1}\left(a\right)=ay_{n}\left(a\right)+x_{n}\left(a\right) \)

או בצורה טיפה יותר אלגנטית אבל לא מפורשת, \( x_{n}\left(a\right)+y_{n}\left(a\right)\sqrt{d}=\left(a+\sqrt{d}\right)^{n} \). אבחנה חביבה של דיוויס בנקודה הזו היא שהנוסחה הזו דומה באופיה לנוסחת אוילר, \( \cos\theta+i\sin\theta=e^{i\theta} \). כאן \( \cos \) מיוצג על ידי \( x_{n}\left(a\right) \), \( \sin \) מיוצג על ידי \( y_{n}\left(a\right) \), במקום \( i \) יש לנו את \( \sqrt{d} \) ובמקום \( e^{i} \) יש לנו את \( a+\sqrt{d} \). דיוויס מצביע על כך שניתן להשתמש בייצוג המעריכי הזה כדי לקבל בקלות נוסחאות לחיבור וחיסור (למעשה, כבר יש לנו את הנוסחה לחיבור…) שמזכירות את הנוסחאות המקבילות מטריגו - ושוב, לא במקרה! הדרך הכי טובה לפתח את הנוסחאות מטריגו היא לעבור דרך נוסחת אוילר שפשוט נותנת לנו אותן במתנה. אני מציע לכם לשחק קצת עם המשוואות ולהוכיח את הנוסחאות הללו לעצמכם בדרך הזו:

\( x_{m\pm n}=x_{m}x_{n}\pm dy_{m}y_{n} \)

\( y_{m\pm n}=x_{n}y_{m}\pm x_{m}y_{n} \)

שימו לב שכבר התעצלתי מלכתוב את ה-\( \left(a\right) \) אחרי ה-\( x_{n},y_{n} \) וכך גם אמשיך לעשות בהמשך אם זהותו המדויקת של ה-\( a \) לא רלוונטית באותו רגע או ברורה מההקשר.

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

בתור התחלה, \( x_{n},y_{n} \) הם זרים - אין להם מחלק משותף חיובי גדול מ-1. זה מסומן בתור \( \left(x_{n},y_{n}\right)=1 \). למה? פשוט: אם \( d \) חיובי מחלק את \( x_{n} \) ואת \( y_{n} \) אז הוא בוודאי מחלק גם את \( x_{n}^{2} \) ואת \( dy_{n}^{2} \) ולכן גם מחלק את ההפרש ביניהם, שהוא 1. אם \( d \)הוא חיובי ומחלק את 1, הוא בהכרח 1 בעצמו.

קצת יותר מעניינת הטענה ש-\( y_{n} \) מחלק את \( y_{nk} \). זה מן הסתם נכון עבור \( k=1 \) אבל לערכים גדולים יותר יש צורך להוכיח זאת באינדוקציה, בעזרת נוסחת החיבור שלנו:

\( y_{n\left(k+1\right)}=y_{nk+n}=x_{n}y_{nk}+x_{nk}y_{n} \)

מהנחת האינדוקציה עולה ש-\( y_{n} \) מחלק את \( y_{nk} \) ולכן את \( x_{n}y_{nk} \), וברור שהוא מחלק את \( x_{nk}y_{n} \), ולכן קיבלנו ש-\( y_{n} \) מחלק את \( y_{n\left(k+1\right)} \). האם יש עוד איברים בסדרת ה-\( y \)-ים אותם \( y_{n} \) יכול לחלק? מסתבר שלא. נניח ש-\( y_{n} \) מחלק את \( y_{t} \) אבל \( n \) לא מחלק את \( t \). אז אפשר לחלק אותם עם שארית, כלומר לכתוב \( t=qn+r \) כאשר \( 0<r<n \) היא השארית. נקבל: \( y_{t}=x_{r}y_{nq}+x_{nq}y_{r} \). אם \( y_{n} \) מחלק את הביטוי הזה, אז מכיוון שאנו יודעים שהוא מחלק את \( y_{nq} \) נקבל שהוא חייב לחלק את \( x_{nq}y_{r} \). כעת, \( \left(y_{nq},x_{nq}\right)=1 \) ולכן לא ייתכן ש-\( y_{n} \) יחלק את \( x_{nq} \), אחרת הוא היה גורם משותף שלו ושל \( y_{nq} \). לכן בהכרח \( y_{n} \) מחלק את \( y_{r} \), אבל זה בלתי אפשרי כי \( y_{n}>y_{r} \)! סוף הסיפור.

אתם בוודאי תוהים לאן אני חותר עם כל התכונות הללו. המטרה היא למצוא משהו שאפשר לקודד דיופנטית איכשהו ויאפשר לנו לאפיין את הסדרות \( x_{n},y_{n} \) במדויק. הכיוון המבטיח ביותר הוא תכונות של הסדרות הללו מודולו משהו. כזכור, \( a\equiv_{n}b \) פירושו ש-\( n \) מחלק את \( a-b \) (ובמילים אחרות, שהשארית של חלוקת \( a \) ו-\( b \) ב-\( n \) היא זהה). הנה דוגמה ראשונה לתכונת מודולו:

\( y_{nk}\equiv_{y_{n}^{3}}kx_{n}^{k-1}y_{n} \)

טוב, במבט ראשון המשוואה הזו נראית מונפצת לגמרי. איך בכלל הגיעו אליה? התשובה היא שמישהו כנראה ניסה, על מנת להבין את הסדרות \( x_{n},y_{n} \), לשחק איתן כמה שיותר. הוא כנראה הסתכל על האיבר \( x_{nk}+y_{nk}\sqrt{d}=\left(x_{n}+y_{n}\sqrt{d}\right)^{k} \) ושאל את עצמו - הממ, מה יקרה אם פשוט נפתח את הסוגריים באמצעות הבינום של ניוטון (הדרך ה”רגילה” לפתוח סוגריים שכאלה)? התשובה היא שנקבל:

\( \left(x_{n}+y_{n}\sqrt{d}\right)^{k}=\sum_{i=0}^{k}{k \choose i}x_{n}^{k-i}\left(y_{n}\sqrt{d}\right)^{i}=\sum_{i=0}^{k}{k \choose i}x_{n}^{k-i}y_{n}^{i}d^{\frac{i}{2}} \)

שימו לב ל-\( d^{\frac{i}{2}} \). עבור הערכים הזוגיים של \( i \) זהו מספר טבעי, ולכן כל הגורם \( {k \choose i}x_{n}^{k-i}y_{n}^{i}d^{\frac{i}{2}} \) יתרום ל-\( x_{nk} \) במקרה הזה. עבור \( i \) אי זוגי נקבל \( \sqrt{d} \) בחזקת משהו אי זוגי, ולכן כל הגורם יתרום ל-\( y_{nk}\sqrt{d} \). אם נחלק ב-\( \sqrt{d} \) את שני האגפים נקבל שהגורם הזה תורם \( {k \choose i}x_{n}^{k-i}y_{n}^{i}d^{\frac{i-1}{2}} \) ל-\( y_{nk} \). לכן קיבלנו:

\( y_{nk}=\sum_{\begin{array}{c}i=1\\i\mbox{ odd}\end{array}}^{k}{k \choose i}x_{n}^{k-i}y_{n}^{i}d^{\frac{i-1}{2}} \)

עכשיו משתמשים בתעלול שמשתמשים בו כל הזמן בתורת המספרים (תצטרכו להאמין לי). שמים לב לכך שפרט לאיבר הראשון בסכום, זה שמתקבל עבור \( i=1 \), עבור כל שאר האיברים מתקיים \( i\ge3 \) ולכן \( y_{n}^{3} \) מחלק את כולם, ולכן מודולו \( y_{n}^{3} \) הם נעלמים (זו הסיבה שבגללה בוחרים \( y_{n}^{3} \) דווקא - כדי שהמודולוס יהיה גדול יחסית ועדיין יישאר לנו ביטוי פשוט יחסית. לכן נישאר רק עם האיבר הראשון:

\( y_{nk}\equiv_{y_{n}^{3}}{k \choose 1}x_{n}^{k-1}y_{n}=kx_{n}^{k-1}y_{n} \)

פתאום הביטוי הזה כבר לא נראה מפחיד כל כך. לפחות לא בשבילי. כמובן, עדיין לא ברור בשביל מה הוא טוב. אז הנה המסקנה המיידית שלו: מה קורה אם במשוואה שקיבלנו נציב \( k=y_{n} \)? נקבל מייד

\( y_{ny_{n}}\equiv_{y_{n}^{3}}y_{n}x_{n}^{y_{n}-1}y_{n}=y_{n}^{2}x_{n}^{y_{n}-1} \)

שזה אומר, בצורה הכי מפורשת שרק אפשר, ש-\( y_{ny_{n}}-y_{n}^{2}x_{n}^{y_{n}-1}=\alpha\cdot y_{n}^{3} \), כאשר \( \alpha \) הוא מספר שלם לא מעניין כלשהו. נעביר אגפים, נוציא גורם משותף, ונקבל:

\( y_{ny_{n}}=y_{n}^{2}\left(x_{n}^{y_{n}-1}+\alpha y_{n}\right) \)

כלומר, המסקנה שלנו היא ש-\( y_{n}^{2} \) מחלק את \( y_{ny_{n}} \). עוד תכונת התחלקות של הסדרה \( y_{n} \)! כמו בתכונת ההתחלקות הקודמת, אנחנו גם רוצים להבין מה קורה בכיוון ההפוך. כלומר, אם \( y_{n}^{2} \) מחלק \( y_{t} \) כלשהו, אז מה אפשר לדעת על \( t \)? במקרה שלנו אפשר להוכיח שבהכרח \( y_{n} \) מחלק את \( t \). למה? טוב, ראשית, אם \( y_{n}^{2} \) מחלק את \( y_{t} \) אז בוודאי שגם \( y_{n} \) מחלק אותו, וכבר ראינו שזה גורר ש-\( n \) מחלק את \( t \), כלומר אפשר לכתוב \( t=nk \). עכשיו, \( y_{t}=y_{nk}\equiv_{y_{n}^{3}}kx_{n}^{k-1}y_{n} \), ולכן בגלל ש-\( y_{n}^{2} \) מחלק את \( y_{t} \) נקבל שהוא מחלק גם את \( kx_{n}^{k-1}y_{n} \), כלומר \( y_{n} \) מחלק את \( kx_{n}^{k-1} \). כמו כן, \( \left(y_{n},x_{n}\right)=1 \) ולכן \( y_{n} \) מחלק את \( k \), אבל \( t=nk \) ולכן \( y_{n} \) מחלק את \( t \) - סיימנו.

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

בואו נעבור לדבר עכשיו על משהו קצת שונה שקשור לסדרות \( x_{n},y_{n} \) - אפשר להציג אותן גם באמצעות נוסחת נסיגה. בפרט:

\( x_{n+1}=2ax_{n}-x_{n-1} \)

\( y_{n+1}=2ay_{n}-y_{n-1} \)

ההוכחה כמעט מיידית באמצעות הנוסחאות שלנו ל-\( x_{n\pm m} \) ו-\( y_{n\pm m} \) ואתם מוזמנים לנסות ולמצוא אותה בעצמכם.

מה שנחמד בנוסחאות הנסיגה הללו הוא שהן מאפשרות להוכיח טענות על הסדרות \( x_{n},y_{n} \) אינדוקטיבית. למשל, בואו נוכיח ש-\( y_{n}\equiv_{a-1}n \): ראשית כל בודקים ישירות שזה מתקיים עבור \( n=0,1 \), ושנית:

\( y_{n+1}=2ay_{n}-y_{n-1}\equiv_{a-1}2n-\left(n-1\right)=n+1 \) (השתמשתי כאן בכך ש-\( a\equiv_{a-1}1 \))

כמו כן, וזה כבר מעניין למדי, אם \( a\equiv_{c}b \) אז לכל \( n \) מתקיים ש-\( x_{n}\left(a\right)\equiv_{c}x_{n}\left(b\right) \) ו-\( y_{n}\left(a\right)\equiv_{c}y_{n}\left(b\right) \). גם ההוכחה פה היא מיידית מתוך נוסחת הנסיגה, כאשר המקרים \( n=0,1 \)טריוויאליים (מבחן - היכן אנו משתמשים שם בכך ש-\( a\equiv_{c}b \)?). בכל הנוגע לצעד:

\( y_{n+1}\left(a\right)=2ay_{n}\left(a\right)-y_{n-1}\left(a\right)\equiv_{c}2by_{n}\left(b\right)-y_{n-1}\left(b\right)=y_{n+1}\left(b\right) \)

ואותו דבר בדיוק עבור \( x_{n} \).

עוד שעשוע הוא להיווכח בכך ש-\( y_{n} \) הוא זוגי עבור \( n \) זוגי, ואי זוגי עבור \( n \) אי זוגי. את זה אפשר להסיק מהסתכלות על נוסחת הנסיגה מודולו 2:

\( y_{n+1}=2ay_{n}-y_{n-1}\equiv_{2}y_{n-1} \)

ובגלל ש-\( y_{0} \) זוגי ו-\( y_{1} \) אי זוגי התוצאה נובעת.

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

\( x_{n}\left(a\right)-y_{n}\left(a\right)\left(a-y\right)\equiv_{2ay-y^{2}-1}y^{n} \)

מי זה \( y \)? מספר כלשהו. אז למה דווקא לסמן אותו ב-\( y \)? כדי לדבוק בסימונים של דיוויס.

ההוכחה, כרגיל, דורשת קודם כל לבדוק את המקרה של \( n=0,1 \). בואו נעשה את זה במפורש הפעם:

\( x_{0}\left(a\right)-y_{0}\left(a\right)\left(a-y\right)=1-0\left(a-y\right)=1\equiv_{2ay-y^{2}-1}y^{0} \)

\( x_{1}\left(a\right)-y_{1}\left(a\right)\left(a-y\right)=a-1\left(a-y\right)=y\equiv_{2ay-y^{2}-1}y^{1} \)

ועכשיו נמשיך אינדוקטיבית:

\( x_{n+1}\left(a\right)-y_{n+1}\left(a\right)\left(a-y\right)=2a\left[x_{n}\left(a\right)-y_{n}\left(a-y\right)\right]-\left[x_{n-1}\left(a\right)-y_{n-1}\left(a-y\right)\right]\equiv_{2ay-y^{2}-1}2ay^{n}-y^{n-1} \)

עוד לא סיימנו:

\( 2ay^{n}-y^{n-1}=y^{n-1}\left(2ay-1\right)\equiv_{2ay-y^{2}-1}y^{n-1}y^{2}=y^{n+1} \)

לב העניין כאן הוא המעבר \( \left(2ay-1\right)\equiv_{2ay-y^{2}-1}y^{2} \) - ודאו שאתם מבינים למה הוא נכון.

עכשיו בואו נבין משהו על קצב הגידול של \( x_{n},y_{n} \). נתחיל מ-\( y_{n} \). כזכור, \( y_{n+1}=y_{n}x_{1}+y_{1}x_{n}=ay_{n}+x_{n} \), ולכן \( y_{n+1}>ay_{n} \) - בפרט אפשר להסיק ש-\( y_{n} \) חיובי לכל \( n \) (לא נצטרך יותר מזה).

בכל הנוגע ל-\( x_{n} \), יש לנו את הנוסחה \( x_{n+1}=x_{n}x_{1}+dy_{n}y_{1}=ax_{n}+dy_{n} \). אז \( x_{n+1}>ax_{n} \) לכל \( n \), ולכן אפשר להראות באינדוקציה ש-\( x_{n}\ge a^{n} \), כלומר הסדרה גדלה בקצב שהוא לפחות אקספוננציאלי. זה חסם מלמטה, אבל האם אפשר לחסום גם מלמעלה? ובכן, בקלות, עם נוסחת הנסיגה של \( x_{n} \): \( x_{n+1}=2ax_{n}-x_{n-1}\le2ax_{n} \) ולכן \( x_{n}\le\left(2a\right)^{n} \).

עוד טיפה וסיימנו. התכונה הבאה נראית מוזר למדי במבט ראשון:

\( x_{2n\pm i}\equiv_{x_{n}}-x_{i} \)

אין כאן יותר מאשר שימוש בהגדרה:

\( x_{2n\pm i}=x_{n}x_{n\pm i}+dy_{n}y_{n\pm i}\equiv_{x_{n}}dy_{n}\left(y_{n}x_{i}\pm x_{n}y_{i}\right)\equiv_{x_{n}}dy_{n}^{2}x_{i}=\left(x_{n}^{2}-1\right)x_{i}\equiv_{x_{n}}-1 \)

כאן השתמשנו בכך ש-\( x_{n}^{2}-dy_{n}^{2}=1 \), ולכן \( dy_{n}^{2}=x_{n}^{2}-1 \).

מסקנה מיידית היא ש-\( x_{4n\pm i}\equiv_{x_{n}}x_{i} \), כי \( x_{4n\pm i}=x_{2n+\left(2n\pm i\right)}\equiv_{x_{n}}-x_{2n\pm i}\equiv_{x_{n}}x_{i} \).

עכשיו לתוצאה שההוכחה שלה תהיה טיפה יותר ארוכה, אבל כבר נראית די מעניינת: אם \( x_{i}\equiv_{x_{n}}x_{j} \) כך ש-\( i\le j\le2n \) ו-\( n>0 \) אז \( i=j \) למעט המקרה \( a=2,n=1,i=0,j=2 \). זה מעניין כי זה מראה שאפשר לזהות בצורה ייחודית, בערך, איברים ב-\( x_{n}\left(a\right) \) על פי תכונות התחלקות שלהם, וזה משהו שאפשר לקודד דיופנטית, בערך.

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

אז בואו נניח ש-\( x_{n} \) הוא אי זוגי וניקח את אוסף השאריות מ-\( -q \) עד \( q \) כאשר \( q=\frac{x_{n}-1}{2} \). עכשיו, בואו נסתכל לרגע במספרים \( x_{0},x_{1},x_{2},\dots,x_{n-1} \). ראשית, יש בדיוק \( n \) כאלו. שנית, זו סדרה עולה: \( 1=x_{0}<x_{1}<x_{2}<\dots<x_{n-1}<x_{n} \) וזאת בגלל נוסחת הנסיגה שמגדירה את ה-\( x_{n} \)-ים. זה בפרט אומר שכל ה-\( x_{i} \)-ים הללו שונים זה מזה מודולו \( x_{n} \) (למה?). כעת, אפשר לחסום את הגודל של האיבר המקסימלי בסדרה: אנחנו יודעים ש-\( x_{n}=ax_{n-1}+dy_{n-1}\ge ax_{n-1} \) ולכן \( x_{n-1}\le\frac{x_{n}}{a}\le\frac{x_{n}}{2} \). נובע מזה ש-\( x_{n-1}\le q \) (כי \( x_{n-1} \) הוא שלם ואילו \( q \) הוא הערך השלם התחתון של \( \frac{x_{n}}{2} \)). במילים אחרות, ה-\( x_{i} \)-ים מתאימים לשאריות חיוביות בתוך הקבוצה \( \left\{ -q,-q+1,\dots,-1,0,1,\dots,q\right\} \).

בואו נסתכל עכשיו על המספרים שמעבר ל-\( x_{n} \): \( x_{n+1},x_{n+2},\dots,x_{2n} \). לפני רגע ראינו את התכונה \( x_{2n\pm i}\equiv_{x_{n}}-x_{i} \) ועכשיו היא תועיל לנו: היא אומרת שהסדרה \( x_{n+1},x_{n+2},\dots,x_{2n} \) שקולה מודולו \( x_{n} \) לסדרה \( -x_{n-1},-x_{n-2},\dots,-x_{0} \). מכיוון שה-\( x_{i} \)-ים התאימו לשאריות חיוביות, זה אומר שה-\( x_{n+i} \)-ים מתאימים לשאריות שליליות בתוך הקבוצה \( \left\{ -q,-q+1,\dots,-1,0,1,\dots,q\right\} \). השאריות החיוביות והשליליות בקבוצה לא שקולות זו לזו, ולכן קיבלנו שכל ה-\( x_{i} \)-ים עד \( i\le2n \) לא שקולים האחד לשני (אם אתם עדיין לא משוכנעים נסו להשלים את ההוכחה).

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

\( x_{n}=ax_{n-1}+dy_{n-1}=a\frac{x_{n}}{2}+dy_{n-1} \)

מתי זה יכול לקרות? מכיוון ש-\( a\ge2 \), הדרך היחידה שבה נוכל לקבל שוויון היא אם \( a=2 \) (אחרת \( a\frac{x_{n}}{2}+dy_{n-1}>x_{n} \)), ובמקרה זה בהכרח \( y_{n-1}=0 \), אבל זה קורה רק עבור \( n=1 \). הנה הוכחנו שאנחנו במקרה הפרטי היחיד שסייגנו החוצה מראש בניסוח המשפט.

יפה, הוכחנו את המשפט, בואו נרחיב אותו טיפה ונראה שאם \( x_{i}\equiv_{x_{n}}x_{j} \) תוך שאנו מאלצים את \( i \) להיות קטן יותר - \( 0<i\le n \) אבל מרשים ל-\( j \) להיות גדול יותר - \( 0\le j<4n \), אז או ש-\( j=i \) כמקודם או ש-\( j=4n-i \). ההוכחה פשוטה: אם \( j\le2n \) פשוט נשתמש במשפט שזה עתה הוכחנו. יש את ה”סכנה” שאנחנו במקרה היוצא מן הכלל, אבל אז \( j=0 \) (כי אסרנו על \( i \) להיות 0) וזה מוביל לסתירה כי אז \( i=2>1=n \). בקיצור, החריג ההוא לא ממש רלוונטי במקרה הזה.

במקרה השני \( j>2n \). נסמן \( t=4n-j \), אז \( 0<t<2n \). כעת, זוכרים שהוכחנו מתישהו ש-\( x_{4n\pm j}\equiv_{x_{n}}x_{j} \)? זה נותן לנו עכשיו ש-\( x_{t}\equiv_{x_{n}}x_{j}\equiv x_{i} \) ולכן שוב, מהמשפט שזה עתה הוכחנו, \( t=i \) (ולמה החריג למשפט לא יכול להתקיים כעת?)

רק עוד דבר אחד וסיימנו: נניח ש-\( 0<i\le n \) ומתקיים \( x_{i}\equiv_{x_{n}}x_{j} \), בלי שום הנחות על \( j \). מה נוכל לומר עליו? ובכן, בואו ננסה לחלק אותו ב-\( 4n \), כלומר נרשום אותו בצורה \( j=4nt+r \) כאשר \( 0\le r<4n \). עכשיו, זכרו שוב ש-\( x_{4n\pm k}\equiv_{x_{n}}x_{k} \) ושאפשר לכתוב \( 4nt+r=4n+\left(4n\left(t-1\right)+r\right) \), ולכן \( x_{j}=x_{4nt+r}\equiv_{x_{n}}x_{4n\left(t-1\right)+r} \). אפשר להמשיך עם זה ולקבל בסופו של דבר \( x_{j}\equiv_{x_{n}}x_{r} \), ולכן \( x_{r}\equiv_{x_{n}}x_{i} \). עכשיו \( 0\le r<4n \) ולכן אפשר להשתמש במשפט הקודם עליו ולקבל \( i=r \) או \( i=4n-r \). משני המקרים הללו נקבל ש-\( j\equiv_{4n}r\equiv_{4n}\pm i \) (אחד משניהם, לא שניהם גם יחד!).

זהו. זה היה מייגע ביותר, אבל עכשיו קיבלנו די והותר כלי נשק להתמודדות עם שאלת הדיופנטיות של \( \left(x_{n},y_{n}\right) \) בפרט, ושל הפונקציה האקספוננציאלית בכלל. בפוסט הבא זה גם יקרה בפועל.