הצגת המקור של הדף "משפט ההדדיות הריבועית"

[[קובץ:Disqvisitiones-800.jpg|ממוזער|שמאל|גאוס פרסם את ההוכחה הראשונה והשנייה של חוק ההדדיות הריבועית במאמרים 125-146 ומאמר 262 של ספרו [[מחקרים אריתמטיים]] מ-1801.]]
ב[[תורת המספרים]], '''משפט ההדדיות הריבועית''' הוא משפט ב[[חשבון מודולרי]] המספק תנאים לפתירות של [[משוואה ממעלה שנייה|משוואות ריבועיות]] מודולו [[מספר ראשוני|מספרים ראשוניים]]. המשפט למעשה מקשר בין היכולת לפתור שתי משוואות מודולריות ריבועיות. הוא נוסח לראשונה בידי [[לאונהרד אוילר|אוילר]] ו[[אדריאן-מארי לז'נדר|לז'נדר]] (שהוכיח אותו למקרים פרטיים), אך היה זה [[קרל פרידריך גאוס|גאוס]] ש[[הוכחה|הוכיח]] אותו במלואו לראשונה, בשנת [[1796]]. למשפט יש ניסוחים רבים, אך הקביעה הסטנדרטית ביותר שלו היא כדלהלן:

יהיו <math>p,q</math> שני מספרים ראשוניים אי-זוגיים שונים, אז נגדיר את [[סימן לז'נדר]] כך:
:<math>\left(\frac{q}{p}\right)=\begin{cases}1&:\exist n\in\N,\,n^2\equiv q\!\pmod{p}\\-1&:\forall n\in\N,\,n^2\not\equiv q\!\pmod{p}\end{cases}</math>
אז מתקיים
:<math>\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}</math>

חוק זה מאפשר חישוב ישיר של סימן לז'נדר, ומאפשר לקבוע האם ישנו פתרון טבעי למשוואה מודולרית מהצורה <math>x^2\equiv a\!\!\!\pmod{p}</math> בעבור <math>p</math> ראשוני אי-זוגי; כלומר, במילים אחרות, לקבוע את "הריבועים המושלמים" מודולו <math>p</math>. ב[[קריפטוגרפיה]], המשפט מאפשר גם להכריע בשאלה האם מספר ראשוני נתון <math>p</math> הוא [[שארית ריבועית]] מודולו מספר ראשוני גדול בהרבה <math>q</math> במהירות רבה יותר: בעוד שבדיקה נאיבית של כל הריבועים מודולו <math>q</math> עשויה לצרוך זמן חישוב רב, המשפט מאפשר לקצר משמעותית את הבדיקה באמצעות בדיקה של <math>q</math> מודולו <math>p</math> (כך שיש לבדוק רק <math>p</math> ריבועים). אף על פי כן, המשפט הוא תוצאה [[קונסטרוקטיביזם (פילוסופיה של המתמטיקה)|לא-קונסטרוקטיבית]]: הוא לא מצביע על שיטה [[יעילות אלגוריתמית|יעילה]] למציאה של פתרון כזה.

המשפט נחשב לנקודת ציון בתורת המספרים הקלאסית ולתוצאה מפתיעה מאוד; בעוד שבעבור קונגרואנציות ליניאריות [[משפט השאריות הסיני]] אומר לנו שההתנהגות של דברים מודולו [[מספר ראשוני]] מסוים <math>p</math> היא בלתי תלויה בהתנהגות שלהם מודולו מספר ראשוני אחר ''q'', חוק ההדדיות הריבועית קובע התנהגות שונה עבור קונגרואנציות ריבועיות, ומראה שישנה תלות הדדית מסוימת בין ההתנהגויות – <math>\left(\tfrac{p}{q}\right)</math> מגביל את <math>\left(\tfrac{q}{p}\right)</math>. בכך הוא מרמז על מבנה אריתמטי נסתר ועמוק יותר, ומבחינה היסטורית גילויו, הוכחתו והניסיונות להכלילו היו בין הזרזים העיקריים להתפתחות תורת המספרים המודרנית{{הערה|Gauss' Quadratic Reciprocity Law
[https://math.stackexchange.com/questions/3272384/gauss-quadratic-reciprocity-law]
}}.

מאז גאוס, הכללת חוק ההדדיות הייתה לבעיה מובילה במתמטיקה, ששיחקה תפקיד מרכזי בהתפתחות רבים מהכלים הטכניים של האלגברה, תורת המספרים, וה[[גאומטריה אלגברית|גאומטריה האלגברית]] המודרנית, כשתהליך זה הגיע לשיאו בניסוח [[חוק ההדדיות של ארטין]], [[תורת שדות המחלקה]] ו[[תוכנית לנגלנדס]]. בנוסף, מחקר מתמטי של המאה ה-20 העיד על יותר ויותר קשרים מעניינים של המשפט עם תאוריות מתמטיות שונות מתחומי ה[[גאומטריה]] וה[[טופולוגיה]] – למשל, ב[[תורת הקשרים]], שם מושג הקשר הראשוני אנלוגי למספר ראשוני באריתמטיקה, ואת תפקיד ההדדיות הריבועית ממלא המשפט שקובע ש[[אינדקס שזירה|אינדקס השזירה]] סימטרי ביחס להחלפה של שני קשרים ראשוניים{{הערה| Gauss linking integral and quadratic reciprocity [https://mathoverflow.net/questions/142914/gauss-linking-integral-and-quadratic-reciprocity]}}.

==היסטוריה==
בראייה היסטורית, המשפט הוא אחד הסימנים המובהקים להפיכתה של תורת המספרים למדע מגובש, שכן בעוד שתרבויות רבות הגיעו למידה מסוימת של ידע ותובנה על תבניות ריבועיות (עוד בימי הביניים), לא ניתן למצוא עדויות לרמה [[מתמטיקה|מתמטית]] שמתקרבת למשפט עד שלהי המאה ה-18. יוצא אחד מן הכלל הזה הוא  [[פייר דה-פרמה]], אשר ניתן לראות כמה מטענותיו על הצגה של מספר ראשוני על ידי תבניות ריבועיות מסוימות כמרכיבות יחדיו את הטענה המכונה "משפט ההדדיות הריבועית". עם זאת, פרמה עצמו מעולם לא ניסח את המשפט במפורש. משפט ההדדיות הריבועית נוסח לראשונה במפורש בידי [[לאונהרד אוילר|אוילר]] ו[[אדריאן-מארי לז'נדר|לז'נדר]] (שהוכיח אותו למקרים פרטיים), אך היה זה [[קרל פרידריך גאוס|גאוס]] ש[[הוכחה|הוכיח]] אותו במלואו לראשונה, בשנת [[1796]]. גאוס כינה אותו בשם "'''משפט הזהב'''", וניתן לראות עדות ל[[יופי מתמטי|חיבה שרחש לו]] בכך שכתב לו שמונה הוכחות שונות במהלך חייו (שתיים מהן פורסמו לאחר מותו).

ההוכחה הראשונה שלו, ממאמרים 125-146 של ספרו "מחקרים אריתמטיים", הייתה [[אינדוקציה מתמטית|אינדוקטיבית]] באופיה. ההוכחה השנייה שלו, ממאמר 262 של ספרו זה, עשתה שימוש בתאוריית ה[[גנוס (תבניות ריבועיות)|גנוס]] של [[תבנית ריבועית|תבניות ריבועיות]]. ההוכחות הראשונות של גאוס היו טכניות באופן יחסי ולא שפכו אור על התשובה לשאלה: מדוע בעצם חוק ההדדיות הריבועית נכון? המצב הזה השתנה כאשר גאוס עשה שימוש ב[[סכום גאוס ריבועי|סכומי גאוס ריבועיים]] כדי להראות ששדות ריבועיים הם תת-שדות של [[שדה ציקלוטומי|שדות ציקלוטומיים]], והסיק באופן לא מפורש את ההדדיות הריבועית ממשפט הדדיות עבור שדות ציקלוטומיים. הוכחה זאת שימשה כמעין [[מנשר]] (בוסרי ביותר) של [[תורת שדות המחלקה]], תורה שניתן לראות אותה כהכללה מרחיקת לכת של ההדדיות הריבועית.

מאז פורסמו הוכחות רבות נוספות; בשנת [[2000]] פורסם ספר שהכיל רשימה של לא פחות מ-196 הוכחות שונות.{{הערה|1=Reciprocity Laws: From Euler to Eisenstein, Franz Lemmermeyer, Springer, 2000.}} מאז פרסום זה עובד המחבר על חלקים נוספים לספרו ומספר ההוכחות המעודכן עומד בדצמבר 2009 על 233.{{הערה|1=[http://www.rzuser.uni-heidelberg.de/~hb3/rchrono.html Proofs of the Quadratic Reciprocity Law]{{כותרת קישור נוצרה על ידי בוט}}}}.

==מוטיבציה וניסוח בסיסי==
חוק ההדדיות הריבועית נוסח בעקבות הצורך לקבוע את הפתירות של [[משוואה ריבועית|משוואות ריבועיות]] בחשבון מודולרי, כלומר לענות על השאלה האם עבור מספר ראשוני נתון p קיים [[מספר טבעי]] <math>x</math> כך שכאשר מציבים אותו במשוואה ריבועית מסוימת התוצאה תתחלק ב-<math>p</math>. בשונה מקונגרואנציות ממעלה ראשונה, בהן ניתן להיעזר במשפטים אריתמטיים בסיסיים כמו [[משפט השאריות הסיני]], לא קיים תהליך מתמטי פשוט אשר מאפשר לבדוק את הפתירות של [[קונגרואנציה]] ממעלה שנייה.

חוק ההדדיות הריבועית קובע כי מספר ראשוני <math>q</math> הוא שארית ריבועית מודולו מספר ראשוני <math>p</math> בהתניה בתוצאת הקונגרואנציה ההפוכה; בניסוחו הבסיסי, המשפט מקשר בין היכולת לפתור את שתי ה[[משוואה|משוואות]] הבאות: אם <math>p,q</math> הם שני [[מספר ראשוני|מספרים ראשוניים]] [[זוגיות (מתמטיקה)|אי-זוגיים]], אז המשוואות הן:
:<math>\begin{align}&x^2\equiv p\!\!\!\pmod{q}\qquad(1)\\&y^2\equiv q\!\!\!\pmod{p}\qquad(2)\end{align}</math>
כלומר, השאלה היא מתי כל אחד מהמספרים הוא ריבוע מודולו המספר השני.

על פי המשפט, התשובה לשאלה זו תלויה בשארית של <math>p,q</math> ב[[חילוק|חלוקה]] ב-4. אם השארית של שניהם בחלוקה ב-4 היא 3, קיים פתרון לאחת מהמשוואות [[אם ורק אם]] לא קיים פתרון לשנייה. לעומת זאת, אם השארית בחלוקה ב-4 של לפחות אחד משני הראשוניים היא 1, הרי שקיים פתרון לאחת מהמשוואת אם ורק אם קיים פתרון לשנייה, ומכאן נובע שם החוק "חוק ההדדיות הריבועית" – כלומר חייבת להיות הדדיות בפתירות הקונגרואנציות הריבועיות (במקרה השני).

===דוגמה===
אם <math>p=13,q=17</math> (עבור שניהם השארית בחלוקה ב-4 היא 1), קיימים פתרונות לשתי המשוואות:
:<math>\begin{align}&8^2\equiv13\!\!\!\pmod{17}\\&2^2\equiv17\!\!\!\pmod{13}\end{align}</math>
לעומת זאת, אם <math>p=5,q=13</math> (גם כאן, השארית בחלוקה ב-4 היא 1 עבור שניהם) לא קיים פתרון לאף אחת מהמשוואת (ניתן להיווכח בכך על ידי בדיקה ישירה).

כעת, אם <math>p=7,q=19</math> אז השארית בחלוקה ב-4 של שני המספרים היא במקרה זה 3, וניתן לראות כי קיים פתרון למשוואה הראשונה:
:<math>8^2\equiv7\pmod{19}</math>
אך בדיקה ישירה מעלה כי לא קיים פתרון למשוואה השנייה.

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

===משפטי עזר===
בנוסף למשפט המרכזי, ישנם שני משפטי עזר המתלווים אליו, ומאפשרים להשתמש בו בצורה כללית יותר.
המשפט הראשון אומר כי אם <math>p</math> הוא ראשוני אי-זוגי, אז למשוואה
:<math>x^2\equiv-1\!\!\!\pmod{p}</math>
קיים פתרון אם ורק אם <math>p</math> משאיר שארית 1 בחלוקה ב-4. לדוגמה, עבור <math>p=29</math> קיים הפתרון:
:<math>{12}^2\equiv-1\!\!\!\pmod{29}</math>
אך עבור <math>p=7</math> לא קיים פתרון.

המשפט השני עוסק במשוואה
:<math>x^2\equiv2\!\!\!\pmod{p}</math>
ועל פיו יש למשוואה פתרון אם ורק אם <math>p</math> משאיר שארית של 1 או 7 בחלוקה ב-8.

==ניסוח בעזרת [[סימן לז'נדר]]==
ניתן לנסח את המשפט בצורה קומפקטית יותר באמצעות '''סימן לז'נדר''', המוגדר בצורה הבאה עבור <math>p</math> ראשוני אי זוגי ו-<math>a</math> [[מספר שלם|שלם]] כלשהו:
:<math>\left(\frac{a}{p}\right)=\begin{cases}1&:\exist n\in\N,\,n^2\equiv a\!\pmod{p}\\0&:a\equiv0\!\pmod{p}\\-1 &:\forall n\in\N,\,n^2\not\equiv a\!\pmod{p}\end{cases}</math>
בסימונים אלו, משפט ההדדיות הריבועית ומשפטי העזר יכולים להיות מנוסחים בצורה הבאה:
אם <math>p,q</math> ראשוניים אי-זוגיים, אז:
:<math>\begin{align}\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\\\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}\\\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}\end{align}</math>

==הוכחה==
ההוכחה המתוארת כאן, היא ההוכחה השלישית של [[קרל פרידריך גאוס]] למשפט ההדדיות הריבועית.

'''למה 1:''' ([[הלמה של גאוס (תורת המספרים)|הלמה של גאוס]]) יהי <math>p</math> [[מספר ראשוני]] [[זוגיות (מתמטיקה)|אי-זוגי]], ויהי <math>a</math> [[מספרים זרים|מספר זר]] ל-<math>p</math>.{{ש}}
אם <math>n</math> מספר המספרים בקבוצה <math>S=\left\{a,2a,\ldots,\frac{p-1}{2}a\right\}</math> בעלי שארית גדולה מ-<math>\frac{p}{2}</math> בחלוקה ל-<math>p</math>, אזי <math>\left(\frac{a}{p}\right)=(-1)^n</math>, כאשר אגף שמאל הוא [[סימן לז'נדר]].

'''למה 2:''' ([[הלמה של אייזנשטיין]]) יהי <math>p</math> [[מספר ראשוני]] [[זוגיות (מתמטיקה)|אי-זוגי]], ויהי <math>a</math> [[מספר שלם]] אי-זוגי [[מספרים זרים|זר]] ל-<math>p</math>.
אזי:
:<math>\left(\frac{a}{p}\right)=(-1)^S,\,S=\sum_{k\,=\,1}^{(p-1)/2}\!\left\lfloor\frac{ka}{p}\right\rfloor</math>.

===הוכחת משפט ההדדיות הריבועית===
נתבונן בשתי הקבוצות הבאות:
:<math>M=\left\{1,2,\ldots,\tfrac{p-1}{2}\right\},\quad N=\left\{1,2,\ldots,\tfrac{q-1}{2}\right\}</math>
מספר הזוגות <math>(m,n)</math> – כאשר <math>m\in M,n\in N</math> – שווה לפי עקרון כפל האפשרויות ל-<math>\tfrac{p-1}{2}\tfrac{q-1}{2}</math>.{{ש}}
נחלק את קבוצת הזוגות לשלוש קבוצות: האחת אשר הזוגות בה מקיימים <math>\tfrac{m}{n}<\tfrac{p}{q}</math>, השנייה <math>\tfrac{m}{n}=\tfrac{p}{q}</math>, השלישית <math>\tfrac{m}{n}>\tfrac{p}{q}</math>.{{ש}}
אם <math>\tfrac{m}{n}=\tfrac{p}{q}</math> אז נקבל <math>np=mq</math>, אך <math>p,q</math> זרים ולכן נקבל כי <math>q</math> מחלק את <math>n</math>, בסתירה. כלומר אין זוגות כאלה.{{ש}}
לכל <math>m</math>, מספר המספרים הטבעיים <math>n</math> המקיימים את התנאי בקבוצה הראשונה הוא בדיוק <math>\left\lfloor m\tfrac{q}{p}\right\rfloor</math>.{{ש}}
לכל <math>n</math>, מספר המספרים הטבעיים <math>m</math> המקיימים את התנאי בקבוצה השלישית הוא בדיוק <math>\left\lfloor n\tfrac{p}{q}\right\rfloor</math>.{{ש}}
סך כל הזוגות הסדורים <math>(m,n)</math> שווה לסכום הזוגות המשתייכים לקבוצה הראשונה ולקבוצה השלישית, ונקבל:
:<math>\frac{p-1}{2}\cdot\frac{q-1}{2}=\sum_{m\,=\,1}^{(p-1)/2}\!\left\lfloor\frac{mq}{p}\right\rfloor+\sum_{n\,=\,1}^{(q-1)/2}\!\left\lfloor\frac{np}{q}\right\rfloor=S_p+S_q</math>
אך לפי למה 2 מתקיים <math>\left(\frac{p}{q}\right)=(-1)^{S_p},\left(\frac{q}{p}\right)=(-1)^{S_q}</math>, ולכן
:<math>\left(\frac{p}{q}\right)\!\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}</math>
ובכך נשלמה הוכחת משפט ההדדיות הריבועית.

===הכללה ל[[סימן יעקובי]]===
בהינתן מספר שלם אי-זוגי <math>b</math> מגדירים את סימן יעקובי באמצעות סימן לז'נדר בצורה הבאה:

אם <math>b=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}</math> הוא [[פירוק לגורמים של מספר שלם|פירוק לגורמים]] של <math>b</math>, אזי סימן יעקובי מוגדר כך לכל <math>a</math> שלם:
:<math>\left(\frac{a}{b}\right)=\left(\frac{a}{p_1}\right)^{\alpha_1}\left(\frac{a}{p_2}\right)^{\alpha_2}\cdots\left(\frac{a}{p_k}\right)^{\alpha_k}</math>
תחת הכללה זו ניתן לנסח את משפט ההדדיות הריבועית בצורה דומה עבור סימן יעקובי: אם <math>a,b</math> שלמים אי-זוגיים חיוביים וזרים, אזי:
:<math>\begin{align}\left(\frac{a}{b}\right)\left(\frac{b}{a}\right)=(-1)^{\frac{a-1}{2}\frac{b-1}{2}}\\\left(\frac{-1}{b}\right)=(-1)^{\frac{b-1}{2}}\\\left(\frac{2}{b}\right)=(-1)^{\frac{b^2-1}{8}}\end{align}</math>

==דוגמה לשימוש==
3 הוא שארית ריבועית מודולו <math>p</math> אם ורק אם <math>p\equiv\pm1\!\!\!\pmod{12}</math>.

נניח כי רוצים לדעת האם קיים פתרון למשוואה: 
:<math>x^2\equiv17\!\!\!\pmod{31}</math>
נראה כיצד לעשות זאת תוך שימוש במשפט ההדדיות הריבועית ובשתי תכונות בסיסיות של סימן לז'נדר:
*<math>\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)</math>
*אם<math>a\equiv b\!\!\!\pmod{p}</math> אז <math>\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)</math>.
בעזרת המשפט ושתי תכונות אלה נקבל:
:<math>\left(\frac{17}{31}\right)=1\cdot\left(\frac{17}{31}\right)=\left(\frac{31}{17}\right)\left(\frac{31}{17}\right) \left(\frac{17}{31}\right)=\left(\frac{31}{17}\right)\cdot(-1)^{\frac{31-1}{2}\frac{17-1}{2}}=\left(\frac{31}{17}\right)=\left(\frac{14}{17}\right)=\left(\frac{2}{17}\right)\left(\frac{7}{17}\right)=\left(\frac{7}{17}\right)</math>
כאשר המעבר האחרון נובע מכך ש-17 מתחלק ב-8 עם שארית 1 ולכן <math>\left(\frac{2}{17}\right)=1</math>.

כעת, נמשיך בצורה דומה:
:<math>\left(\frac{7}{17}\right)=\left(\frac{17}{7}\right)\cdot(-1)^{\frac{17-1}{2}\frac{7-1}{2}}=\left(\frac{17}{7}\right)=\left(\frac{3}{7}\right)</math>
ושוב נבצע אותו הדבר בדיוק:
:<math>\left(\frac{3}{7}\right)=\left(\frac{7}{3}\right)\cdot(-1)^{\frac{7-1}{2}\frac{3-1}{2}}=-\left(\frac{7}{3}\right)=-\left(\frac{1}{3}\right)=-1</math>
וקיבלנו שאין למשוואה פתרון. המעבר האחרון נובע מכך כי <math>\left(\frac{1}{p}\right)=1</math> לכל <math>p</math> (למעשה, <math>\left(\frac{a^2}{p}\right)=1</math> לכל <math>p</math> ראשוני ולכל <math>a</math>, על פי הגדרה).

==הכללות==
קיימות הכללות של המשפט לסדרים גבוהים יותר - למשל, לחזקה שלישית ורביעית. עם זאת, מכיוון שחלק מ[[שורש יחידה|שורשי היחידה]] של 1 מסדר שהוא גבוה מ-2 אינם [[מספר ממשי|ממשיים]], משפטים אלו מתבססים על אריתמטיקה שמערבת את [[מספר מרוכב|המספרים המרוכבים]] ואינה תלויה אך ורק ב[[מספר רציונלי|מספרים רציונליים]], ולכן שייכים יותר ל[[תורת המספרים האלגברית]].

== ראו גם ==
*[[שארית ריבועית]]
*[[הלמה של גאוס (תורת המספרים)|הלמה של גאוס]]

==קישורים חיצוניים==
*[https://www.youtube.com/watch?v=X63MWZIN3gM הסבר מאיר עיניים על משפט ההדדיות הריבועית בערוץ היוטיוב Mathologer]
*{{MathWorld}}

==הערות שוליים==
<div style="direction: ltr;">
{{הערות שוליים}}
</div>

[[קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה]]
[[קטגוריה:שאריות ריבועיות]]
[[קטגוריה:משפטים בתורת המספרים|הדדיות ריבועית]]
[[קטגוריה:לאונרד אוילר]]
[[קטגוריה:קרל פרידריך גאוס]]