על סכומי ריבועים והקשר להדדיות ריבועית

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

אם כן, נתחיל מהתחלה. פרמה נהג, כידוע, לתאר תגליות מתמטית במכתבים לידידים, לרוב בלי הוכחה של ממש. כך היה גם במכתב מ-1640 למרסן (אותו מרסן ממספרי מרסן שגם כן הזכרתי כשדיברתי על פרמה). פרמה טען שהוא יודע מתי מספר ראשוני \( p \) ניתן להצגה כסכום של שני ריבועים שלמים, כלומר \( p=x^{2}+y^{2} \) עם \( x,y \) שלמים; הוא טען שזה מתרחש בדיוק כאשר \( p \) מותיר שארית של 1 כאשר מחלקים אותו ב-4. בכתיבה מודרנית, זה מתואר כך: \( p\equiv1\left(4\right) \). פרמה לא עצר כאן - הוא טען שניתן להציג את \( p \) בתור \( p=x^{2}+2y^{2} \) בדיוק כאשר \( p\equiv1,3\left(8\right) \), ולקינוח טען שניתן להציג את \( p \) בתור \( p=x^{2}+3y^{2} \) אך ורק כאשר \( p\equiv1\left(3\right) \) (או כאשר \( p=3 \) בעצמו, אבל זה מקרה בודד ולכן לא מעניין). תאמרו שלא ברור למה להתעמק דווקא בראשוניים ולא בכל המספרים - הסיבה לכך היא שכל מספר ניתן לכתיבה כמכפלה של ראשוניים, ולכן הבנת הטענה על הראשוניים היא הצעד הראשון והחשוב ביותר בדרך לטענה כללית על כל המספרים.

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

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

מבחינה היסטורית, את שלב הנסיגה אוילר סיים יחסית מהר - הוא תיאר אותו במכתב לגולדבך בשנת 1741. רק בשנת 1749 עלה בידי אוילר לפתור את שלב ההדדיות עבור המקרה של \( p=x^{2}+y^{2} \); המקרים האחרים דרשו לו זמן רב יותר, והעבודה נשלמה רק בשנת 1772 - יותר מ-40 שנים לאחר שאוילר שמע על הבעיה לראשונה.

בין לבין הוא עשה עוד דברים.

ובכן, מהם שני השלבים? אתאר ראשית את שלב הנסיגה עבור המקרה של סכום שני ריבועים, שהוא הפשוט ביותר; בשני המקרים האחרים ההכללה די מיידית אך מעט יותר מסובכת. אני מזהיר מראש שהשלב הזה טכני למדי ואינו המטרה העיקרית שלי בפוסט, כך שמי שמתייאש יכול לדלג. שלב הנסיגה אומר שאם הראשוני \( p \) מחלק סכום של שני ריבועים, \( a^{2}+b^{2} \), אז הוא ניתן לכתיבה כסכום של שני ריבועים בעצמו. ההוכחה של הטענה הולכת כך: מניחים שלא ניתן לכתוב את \( p \) כסכום של שני ריבועים, ומוכיחים כי נובע מכך שקיים ראשוני \( q<p \) שגם הוא מחלק סכום של שני ריבועים אך אינו ניתן לכתיבה כסכום של שני ריבועים. מכאן שאפשר שוב לחזור על הטענה ולקבל עוד ראשוני \( q^{\prime}<q \) שגם כן מקיים את התכונה הזו, וכן הלאה וכן הלאה - וכך נגיע לראשוניים קטנים יותר ויותר, עד שניתקע עם ראשוני קטן מדי, שכן ניתן להציג כסכום של שני ריבועים (למשל, 2).

עד כה לא אמרנו הרבה יותר מאשר פרמה - רק פרטים קצת יותר מדוייקים. עלינו להראות כיצד, בהינתן \( p \) שמחלק סכום של שני ריבועים אך אינו סכום שכזה בעצמו, ניתן למצוא \( q<p \) דומה. לב העניין הוא באבחנה שאם \( N=a^{2}+b^{2} \) הוא סכום של שני ריבועים זרים (“זרים” פירושו שאין ל-\( a,b \) מחלק משותף גדול מ-1) ו-\( q \) הוא ראשוני שהוא בעצמו סכום של שני ריבועים, אז גם \( \frac{N}{q} \) הוא סכום של שני ריבועים זרים. ההוכחה של האבחנה הזו היא טכנית ומכילה כמה משוואות ואני מעדיף לא להיכנס אליה.

אם כן, נתון לנו ש-\( N=a^{2}+b^{2} \), כך ש-\( p|a^{2}+b^{2} \) (הקו פירושו “\( p \) מחלק את \( a^{2}+b^{2} \)”). נשים לב שאפשר לחסר או לחבר את \( p \) בחופשיות הן ל-\( a \) והן ל-\( b \) ועדיין ש-\( p \) יחלק את סכום הריבועים שלהם (בדקו זאת!), ולכן אפשר להניח כי שניהם קטנים יחסית ל-\( p \), נניח \( \left|a\right|,\left|b\right|<\frac{p}{2} \) (אחרת אפשר לחסר מהם את \( p \) שוב ושוב עד שהם נהיים קטנים מספיק). אחרי שעשינו זאת צריך לחלק את \( a,b \) שקיבלנו בגורם המשותף הגדול ביותר שלהם כדי להבטיח ששני המספרים שנקבל יהיו זרים זה לזה (למה \( p \) עדיין יחלק את \( a^{2}+b^{2} \) גם אחרי שנחלק אותם בגורם הזה? כי \( p \) לא מחלק את הגורם הזה בעצמו - למה, ולמה זה מספיק?)

אם כן, נסכם את מה שמגיעים אליו: שקיים \( N=a^{2}+b^{2} \) כך ש-\( p|N \) וכמו כן \( a,b \) זרים זה לזה ומקיימים \( \left|a\right|,\left|b\right|<\frac{p}{2} \), כלומר \( N=a^{2}+b^{2}<\frac{p^{2}}{4}+\frac{p^{2}}{4}=\frac{p^{2}}{2} \). מכאן עולה שאם \( q \) הוא גורם ראשוני של \( N \) השונה מ-\( p \), הוא בהכרח קטן מ-\( p \); אחרת היינו מקבלים \( \frac{p^{2}}{2}>N\ge pq\ge p^{2} \) - סתירה. כעת, אם \( q \) הוא סכום של שני ריבועים, אז מהאבחנה שתיארתי לעיל היה נובע שגם \( \frac{N}{q} \) הוא סכום של שני ריבועים; ואם היינו חוזרים על החלוקה הזו לכל גורם של \( N \) שאיננו \( p \), היינו מקבלים בסופו של דבר את \( p \) כסכום של שני ריבועים (וזה מה שרצינו). לכן אם \( p \) איננו סכום של שני ריבועים, אז קיים \( q<p \) שגם הוא איננו סכום של שני ריבועים, ועם זאת \( q|N=a^{2}+b^{2} \), כלומר זה הראשוני הקטן יותר שחיפשנו - וזה מסיים את ההוכחה.

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

השלב השני בהוכחה של אוילר הוא מה שמכונה “שלב ההדדיות”. בשלב הנסיגה, נקודת המוצא הייתה ש-\( p \) מחלק סכום של שני ריבועים, או בלשון מודרנית, ש-\( a^{2}+b^{2}\equiv0\left(p\right) \), עבור \( a,b \) זרים (ולכן בפרט לא שקולים שניהם לאפס מודולו \( p \) - כלומר, אנחנו רוצים פתרון “לא טריוויאלי” למשוואה). האתגר של שלב ההדדיות הוא להראות עבור אילו ערכי \( p \) הדבר הזה מתקיים. אוילר הוכיח בשיטה משלו - חשבון הפרשים, המקבילה הדיסקרטית של החשבון הדיפרנציאלי, נושא מעניין לכשעצמו - כי כדי שלמשוואה הזו יהיה פתרון צריך להתקיים \( p\equiv1\left(4\right) \). עם זאת, אני רוצה לגשת לשאלה הזו מנקודת מבט מעט יותר מודרנית, ותוך התייחסות לשתי הבעיות הנוספות - אוילר גם רצה לדעת באילו תנאים על \( p \) יש פתרון למשוואה \( a^{2}+2b^{2}\equiv0\left(p\right) \), ובאילו תנאים יש פתרון למשוואה \( a^{2}+3b^{2}\equiv0\left(p\right) \).

נתחיל מהמשוואה \( a^{2}+b^{2}\equiv0\left(p\right) \). על ידי העברת אגפים נקבל \( a^{2}\equiv-b^{2}\left(p\right) \). מכיוון שאנו מניחים ש-\( b\not\equiv0\left(p\right) \) (כי \( b\equiv0\left(p\right) \) יתן לנו את הפתרון הטריוויאלי של המשוואה, שכאמור לא מועיל לנו) אפשר לחלק בו ולקבל \( \left(\frac{a}{b}\right)^{2}\equiv-1\left(p\right) \). על ידי החלפת משתנים אפשר לכתוב את המשוואה הזו בתור \( x^{2}\equiv-1\left(p\right) \). כלומר, הצטמצמנו לשאלה הבאה: מתי \( -1 \) הוא ריבוע מודולו \( p \)? ובטרמינולוגיה שבדרך כלל משתמשים בה: מתי \( -1 \) הוא שארית ריבועית מודולו \( p \)?

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

כדי לטפל בבעיה הזו בצורה רצינית, מאוד מועיל לבצע שינוי נוסף של נקודת המבט - במקום להמשיך לדבר על מספרים מודולו \( p \) כל הזמן, אפשר לעבור ולדבר על איברים בחבורה \( \mathbb{Z}_{p}^{*} \) - אוסף כל המספרים \( \left\{ 1,\dots,p-1\right\} \) עם פעולה של כפל מודולו \( p \) (כופלים שני מספרים, מחלקים ב-\( p \) והתוצאה היא השארית). החבורה הזו היא אחד מהאובייקטים הבסיסיים בתורת המספרים, וידוע עליה הרבה מאוד - בפרט, שהיא ציקלית, כלומר לכל \( p \) קיים \( g\in\mathbb{Z}_{p}^{*} \) כך שכל איבר \( a\in\mathbb{Z}_{p}^{*} \) ניתן לכתיבה בתור \( a=g^{k} \) עבור \( k \) מתאים כלשהו. ברור שאם \( a=g^{2k} \), כלומר \( a \) הוא חזקה זוגית של \( g \), אז \( a \) הוא שארית ריבועית, כי הוא ניתן לכתיבה בתור \( \left(g^{k}\right)^{2} \); ניתן להראות גם את ההפך, שאם \( a=g^{2k+1} \), כלומר הוא חזקה אי זוגית, אז הוא אינו שארית ריבועית (זהו תרגיל נחמד לאלו מכם שבקיאים בתורת החבורות). כעת, \( g \) מקיים \( g^{p-1}=1 \) (זהו “המשפט הקטן של פרמה”), ולכן ברור שאם \( a=g^{2k} \) אז \( a^{\frac{p-1}{2}}=\left(g^{p-1}\right)^{k}=1 \); ולעומת זאת, אם \( a=g^{2k+1} \) אז \( a^{\frac{p-1}{2}}=\left(g^{2k}\cdot g\right)^{\frac{p-1}{2}}=\left(g^{p-1}\right)^{k}\cdot g^{\frac{p-1}{2}}=g^{\frac{p-1}{2}}=-1 \) - שוב, הבקיאים בתורת החבורות ודאי ירצו להצדיק לעצמם את המעבר האחרון, דהיינו ש-\( g^{\frac{p-1}{2}}=-1 \) (רמז: מהו אגף שמאל בריבוע? ומדוע ידוע לנו שאגף שמאל שונה מ-1?). האבחנות הללו מובילות אותנו למה שמכונה “קריטריון אוילר” (אם כי לא ברור לי כלל שאוילר הגיע אליו כך): מספר \( a \) הוא שארית ריבועית מודולו \( p \) אם ורק אם \( a^{\frac{p-1}{2}}\equiv1\left(p\right) \).

הקריטריון הזה מחסל לנו מייד את המקרה של \( -1 \): \( \left(-1\right)^{\frac{p-1}{2}}=1 \) אם ורק אם \( \frac{p-1}{2} \) הוא זוגי, כלומר אם ורק אם \( p-1 \) מתחלק ב-4, כלומר אם ורק אם \( p\equiv1\left(4\right) \). כדי להתחיל את הטיפול במקרים האחרים, אני רוצה להכניס לתמונה סימון נוח - סימן לג’נדר. סימן לג’נדר של \( a \) מעל \( p \) מסומן בתור \( \left(\frac{a}{p}\right) \), מה שמזכיר באופן מבלבל שבר, אבל ניתן כמעט תמיד להבין מההקשר שמדובר בסימן לג’נדר ולא בשבר. הוא מוגדר כך: אם \( a \) אינו זר ל-\( p \), אז \( \left(\frac{a}{p}\right)=0 \); אם \( a \) הוא שארית ריבועית מודולו \( p \) אז \( \left(\frac{a}{p}\right)=1 \), ואם הוא אינו שארית ריבועית מודולו \( p \), אז \( \left(\frac{a}{p}\right)=-1 \). אם כן, את קריטריון אוילר ניתן לכתוב בצורה קומפקטית באופן הבא: \( \left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\left(p\right) \).

סימן לג’נדר מאפשר לנו לתת תיאור קומפקטי של עוד עובדות בסיסיות, למשל \( \left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right) \) - נסו להבהיר לעצמכם שאתם מבינים מה זה אומר (ולבקיאים בתורת החבורות - איך להוכיח את זה?). כמו כן, אם \( a\equiv b\left(p\right) \) אז \( \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right) \). לבסוף, הוא מאפשר לנו לתאר בצורה פשוטה גם את התכונה המשמעותית ביותר של שאריות ריבועיות - משפט ההדדיות הריבועית. הוא מנוסח בפשטות כך: אם \( p,q \) שניהם ראשוניים אי זוגיים שונים זה מזה, אז מתקיים הקשר הבא: \( \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=\left(-1\right)^{\left(\frac{p-1}{2}\right)\left(\frac{q-1}{2}\right)} \). בניסוח מילולי, אפשר לומר שמשפט ההדדיות אומר שסימן לג’נדר של \( p \) מעל \( q \) וסימן לג’נדר של \( q \) מעל \( p \) הם זהים תמיד, פרט למקרה שבו \( p\equiv q\equiv3\left(4\right) \), ואז הם הפוכים זה לזה.

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

לא אכנס כאן לניתוח של השאלה מתי \( -2 \) הוא שארית ריבועית מודולו \( p \) (מן הסתם המסקנה הסופית היא ש-\( p\equiv1,3\left(8\right) \)) כי הוא טכני ולא מחכים עד כדי כך. לעומת זאת, הניתוח של המקרה של \( -3 \) נותן לנו הזדמנות יפה לראות את משפט ההדדיות הריבועית בשיא כוחו (והעובדה שאני נזקק להדדיות ריבועית רומזת משהו על הקושי שהיה לאוילר, שלא הכיר את משפט ההדדיות הריבועית, כשניסה לטפל במקרה הזה בעצמו). זאת מכיוון ש-3 הוא ראשוני, ולכן אפשר להשתמש בו בתור ה-\( q \) שמופיע במשפט ההדדיות הריבועית. היתרון של משפט ההדדיות הריבועית יהיה בכך שהוא יהפוך את השאלה “מתי \( 3 \) הוא שארית ריבועית מודולו \( p \)?” לשאלה “מתי \( p \) הוא שארית ריבועית מודולו 3?”, ומהתכונה שהצגתי קודם, לפיה אם \( a\equiv b\left(q\right) \) אז \( \left(\frac{a}{q}\right)=\left(\frac{b}{q}\right) \) אפשר לראות שזו שאלה יחסית קלה כי מספיק לבדוק באופן ישיר מספר קטן של מקרים: לא קשה לראות כי \( \left(\frac{1}{3}\right)=1 \) ואילו \( \left(\frac{2}{3}\right)=-1 \).

אם כן, נשתמש בהדדיות ריבועית ובמה שכבר גילינו על \( \left(\frac{-1}{p}\right)=\left(-1\right)^{\frac{p-1}{2}} \) ונקבל את החישוב הישיר הבא:

\( \left(\frac{-3}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)=\left(-1\right)^{\frac{p-1}{2}}\left(\frac{p}{3}\right)\left(-1\right)^{\frac{p-1}{2}}=\left(\frac{p}{3}\right) \)

כלומר, משפט ההדדיות הריבועית לימד אותנו ש-\( \left(\frac{-3}{p}\right) \) הוא בדיוק \( \left(\frac{p}{3}\right) \), ולכן הוא 1 אם ורק אם \( p\equiv1\left(3\right) \), בדיוק כפי שציפינו שנקבל. כמובן שהשתמשתי כאן בתותח כבד; אבל מכיוון שמטרת הפוסט העיקרית הייתה להציג את התותח הזה, אין לי חרטות.