סכום של שני ריבועים

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

הבעיה של הצגת מספר נתון כסכום של שני ריבועים, כלומר בצורה \ a^2+b^2, היא מן הבעיות הקלאסיות בתורת המספרים. הבעיה נזכרת בכתבי דיופנטוס, שניסח אותה באופן גאומטרי: בהינתן מספר x, למצוא משולש ישר-זווית בעל צלעות שלמות או רציונליות שאורך היתר שלו הוא x. פרמה טען (ללא הוכחה) שאפשר להציג מספר שלם כסכום של שני ריבועים, אם ורק אם אין לו גורם ראשוני מהצורה 4p-1, המופיע בחזקה אי-זוגית. תוצאה זו, שאותה חקר והוכיח לאונרד אוילר, נקראת לפעמים משפט שני הריבועים של פרמה.

היסטוריה[עריכת קוד מקור | עריכה]

ב- 1225 הציג והוכיח פיבונאצ'י את נוסחת המכפלה \ (a^2+b^2)(c^2+d^2) = (ac\pm bd)^2 + (ad\mp bc)^2, שהייתה מוכרת כנראה כבר לדיופנטוס, למרות שהלה לא ניסחה במפורש. מן הנוסחה עולה שכדי להציג מספר נתון כסכום של שני ריבועים שלמים, די להציג באופן הזה את גורמיו הראשוניים; אז אפשר להיעזר בנוסחה כדי לקבל הצגות עבור המכפלה. לדוגמה, מן ההצגות \ 3^2+2^2=13 ו- \ 1^2+2^2=5, אפשר לקבל את \ 8^2+1^2=4^2+7^2=65.

ב- 1638 הציע פרמה לדקארט להוכיח שלא ניתן להציג מספר מן הצורה \ 4k-1 כסכום של שני ריבועים. כעבור ימים ספורים שלח דקארט את הבעיה ופתרונה למרסן: הריבוע של כל מספר שלם הוא מן הצורה \ 4m או \ 8m+1. ב-1659 כתב פרמה לפסקל שהוא מצא הוכחה לכך שניתן להציג כל ראשוני מהצורה 4k+1 כסכום של שני ריבועים, בשיטה של נסיגה אינסופית.

פרמה המשיך לעסוק בבעיה גם אחר-כך, וכאשר פרסם ב-1670 קובץ הערות על הספר "אריתמטיקה" של דיופנטוס, התייחס גם למשוואה \ a^2+b^2=n. פרמה טען שאם n ראשוני מהצורה 4k+1, אז אפשר לפתור את המשוואה באופן יחיד (פרט להחלפת המשתנים, ולשינוי הסימן), וכן, שאם \ n=p^k ו- p ראשוני מהצורה הנזכרת, אז יש למשוואה בדיוק \ \left\lfloor{\frac{k+1}{2}}\right\rfloor פתרונות. בעזרת נוסחת המכפלה, הציג פרמה שיטה למציאת מספרים שיש להם בדיוק m הצגות כסכום של שני ריבועים.

ל-Bernard Frénicle de Bessy (אנ') מיוחסת ההבחנה שהצגת מספר כסכום של שני ריבועים בשתי דרכים שונות מאפשרת לפרק אותו לגורמים.

למעשה, אם n = a^{2} + b^{2} = c^{2} + d^{2} הן הצגות שונות של n כסכום של 2 ריבועים, ניתן להגדיר: l = \left( \frac{a - c}{\gcd(a - c, d - b)} \right), m = \left( \frac{d - b}{\gcd(a - c, d - b)} \right) ואז l^{2} + m^{2} הוא גורם לא טריוויאלי של n. הפונקציה \gcd(a,b) מסמלת את המחלק המשותף המקסימלי של a ושל b.

ב- 1747, במכתב לגולדבך, הוכיח לאונרד אוילר שאם a ו- b זרים, אז כל גורם של \ a^2+b^2 ניתן להצגה כסכום של שני ריבועים. ההוכחה, המתאימה לתיאורו של פרמה על נסיגה אינסופית (ראו להלן), היא הראשונה שעל קיומה יש ראיות ברורות. אוילר עסק בבעיה זו פעמים רבות, ובאחת ההזדמנויות (ספרו "אלגברה", 1770) העיר שאת נוסחת המכפלה אפשר להוכיח באמצעות חישוב הנורמה המרוכבת של המכפלה \ (a+b\sqrt{-1})(c+d\sqrt{-1}). היום ידוע שאפשר להוכיח את כל התכונות הרצויות של התבנית \ x^2+y^2 בעזרת האוקלידיות של חוג השלמים של גאוס, \ \mathbb{Z}[\sqrt{-1}].

הוכחה באמצעות נסיגה[עריכת קוד מקור | עריכה]

יהי p מספר ראשוני השקול ל- 1 מודולו 4. ידוע ש- 1- הוא שארית ריבועית מודולו p, כלומר, קיים x כך ש- \ x^2+1\equiv 0 \pmod{p}. אם נבחר פתרון x כך ש-|x| < p/2 , מתקבלת הצגה \ x^2+1=mp כאשר \ m = \frac{x^2+1}{p} < p/4. נתבונן בהצגה \ x^2+y^2=mp שבה x,y אינם מתחלקים ב- p, ונניח ש-\ 1 < m. הפתרון יושג על ידי הוכחה בנסיגה אינסופית. על ידי חילוק עם שארית של x,y ב-m אפשר לכתוב \ x=mc+x_1,\, y=md+y_1, כאשר \ |x_1|,|y_1|\leq m/2. כך יוצא ש- \ x_1^2+y_1^2 \equiv x^2+y^2 \equiv 0 \pmod{m}, ומצד שני \ x_1^2+y_1^2<m^2. מכאן ש- \ x_1^2+y_1^2=mm_1 עבור \ 1\leq m_1<m.

מנוסחת המכפלה יוצא ש- \ m^2m_1p = (mp)(mm_1) = (x^2+y^2)(x_1^2+y_1^2)=(xx_1+yy_1)^2+(xy_1-x_1y)^2, אבל שני הגורמים \ xx_1+yy_1,\, xy_1-x_1y מתחלקים ב- m. לאחר שמחלקים את המשוואה ב- \ m^2 מתקבלת הצגה של \ m_1p כסכום של שני ריבועים.

דוגמה. נציג את p=89 כסכום של שני ריבועים. פתרון המשוואה \ x^2+1 \equiv 0 \pmod{p} הוא \ x=\pm 34, ואכן \ 34^2+1 = 13 \cdot 89, כלומר \ m = 13. ההצגה של כפולת p כסכום שני ריבועים היא \ 34^2+1^2 = 13 \cdot 89. נחלק את x=34 ו-y=1 ב-m=13, ונקבל \ 34 = 3 \cdot 13 + (-5) ו-\ 1 = 0 \cdot 13 + 1, כלומר \ x_1 = -5, y_1 = 1. אכן, \ (-5)^2+1^2 = 2\cdot 13, כלומר \ m_1 = 2. מנוסחת המכפלה יוצא \ (13\cdot 89) \cdot (2 \cdot 13) = (34^1+1^2)((-5)^2+1^2) = (-169)^2+(39)^2, וכשמחלקים ב-\ 13^2 מקבלים את ההצגה \ 13^2 + 3^2 = 2 \cdot 89. נחזור לתחילת התהליך, והפעם עם m=2. ההצגה של כפולת p כסכום שני ריבועים היא \ 13^2+3^2 = 2\cdot 89. נחלק את x=13 ו-y=3 ב-m=2, ונקבל \ 13 = 6 \cdot 2 + 1 ו-\ 3 = 1 \cdot 2 + 1, כלומר \ x_1 = y_1 = 1. אכן, \ 1^2+1^2 = 1\cdot 2, כלומר \ m_1 = 1. מנוסחת המכפלה יוצא \ (2\cdot 89) \cdot (1 \cdot 2) = (13^1+3^2)(1^2+1^2) = (16)^2+(10)^2, וכשמחלקים ב-\ 2^2 מקבלים את ההצגה \ 8^2 + 5^2 = 89.

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]

  • History of the Theory of Numbers, Vol. II, Chapter IV: sum of two squares; L.E.Dickson, 1920.
  • Intoroduction to the Theory of Numbers, G.H. Hardy & E.M. Wright, Chapter XX, The representation of a number by two or four squares, 1979.