משפט ההדדיות הריבועית

היסטוריה

בראייה היסטורית, המשפט הוא אחד הסימנים המובהקים להפיכתה של תורת המספרים למדע מגובש, שכן בעוד שתרבויות רבות הגיעו למידה מסוימת של ידע ותובנה על תבניות ריבועיות (עוד בימי הביניים), לא ניתן למצוא עדויות לרמה מתמטית שמתקרבת למשפט עד שלהי המאה ה-18. יוצא אחד מן הכלל הזה הוא  פייר דה-פרמה, אשר ניתן לראות כמה מטענותיו על הצגה של מספר ראשוני על ידי תבניות ריבועיות מסוימות כמרכיבות יחדיו את הטענה המכונה "משפט ההדדיות הריבועית". עם זאת, פרמה עצמו מעולם לא ניסח את המשפט במפורש. משפט ההדדיות הריבועית נוסח לראשונה במפורש בידי אוילר ולז'נדר (שהוכיח אותו למקרים פרטיים), אך היה זה גאוס שהוכיח אותו במלואו לראשונה, בשנת 1796. גאוס כינה אותו בשם "משפט הזהב", וניתן לראות עדות לחיבה שרחש לו בכך שפרסם שש הוכחות שונות שלו במהלך חייו (ושתיים נוספות פרי עטו פורסמו לאחר מותו).
ההוכחה הראשונה שלו, ממאמרים 125-146 של ספרו "מחקרים אריתמטיים", הייתה אינדוקטיבית באופיה. ההוכחה השנייה שלו, ממאמר 262 של ספרו זה, עשתה שימוש בתאוריית הגנוס של תבניות ריבועיות. ההוכחות הראשונות של גאוס היו טכניות באופן יחסי ולא שפכו אור על התשובה לשאלה: מדוע בעצם חוק ההדדיות הריבועית נכון? המצב הזה השתנה כאשר גאוס עשה שימוש בסכומי גאוס ריבועיים כדי להראות ששדות ריבועיים הם תת-שדות של שדות ציקלוטומיים, והסיק באופן לא מפורש את ההדדיות הריבועית ממשפט הדדיות עבור שדות ציקלוטומיים. הוכחה זאת שימשה כמעין מנשר (בוסרי ביותר) של תורת שדות המחלקה, תורה שניתן לראות אותה כהכללה מרחיקת לכת של ההדדיות הריבועית.
מאז פורסמו הוכחות רבות נוספות; בשנת 2000 פורסם ספר שהכיל רשימה של לא פחות מ-196 הוכחות שונות. מאז פרסום זה עובד המחבר על חלקים נוספים לספרו ומספר ההוכחות המעודכן עומד בדצמבר 2009 על 233.

הוכחה

ההוכחה המתוארת כאן, היא ההוכחה השלישית של קרל פרידריך גאוס למשפט ההדדיות הריבועית.
למה 1: הלמה של גאוס:
יהי p מספר ראשוני אי זוגי, ונניח ש- a זר ל- p. אם n הוא מספר המספרים בקבוצה 
 המשאירים שארית גדולה מ- p/2 כשמחלקים אותם ב-p, אז: , כאשר ( ) הוא סימן לז'נדר. 
הוכחה. מכיוון ש- a זר ל- p, כל  המספרים בקבוצה S שונים זה מזה מודולו p. נסמן ב- 
 את שאריות החילוק הקטנות מ- p/2, וב-  את שאריות החילוק הגדולות מ- p/2. המספרים  כולם חיוביים וקטנים מ- p/2. יתרה מזו, אלו מספרים שונים, מפני שאם 
, כאשר  ו-, 
, והרי המכפלות בקבוצה S הן תמיד בגורמים קטנים מ- p/2. 
אם כך, המספרים ברשימה הנ"ל שווים למספרים  בסדר כלשהו, ומכפלתם שווה ל- ; לכן 
. מצד שני, המספרים  מהווים סידור מחדש של הקבוצה S, ומכאן ש- 
. לכן 
. אבל לפי מבחן אוילר, 
.
למה 2: אם p הוא מספר ראשוני אי זוגי ו-a הוא מספר שלם אי זוגי המקיים 1 =(gcd(a,p אז:
הוכחה: בדומה ללמה של גאוס.
הוכחת משפט ההדדיות הריבועית: 
נתבונן בשתי הקבוצות הבאות: {N = {1,2,...,(p-1)/2  ו- {M = {1,2,...,(q-1)/2 . מספר הזוגות (m,n) כאשר m נבחר מתוך הקבוצה M ו-n נבחר מתוך הקבוצה N שווה לפי עקרון כפל האפשרויות ל-  . נחלק את קבוצות הזוגות (m,n) לשלוש קבוצות: האחת אשר הזוגות בה  מקיימים: , השנייה: , השלישית: 
. אם  אז נקבל: nq = pm, ומאחר ש-p ו-q זרים נקבל 
ש-q מחלק את m, סתירה, לכן אין זוגות כאלה. 
לכל m, מספר המספרים הטבעיים n הקיימים את התנאי בקבוצה הראשונה הוא בדיוק [mp/q] ולכל n מספר המספרים הטבעיים m המקיימים את התנאי בקבוצה השלישית הוא בדיוק [nq/p]. מאחר שסה"כ הזוגות הסדורים 
(m,n) שווה לסכום הזוגות המשתייכים לקבוצה הראשונה ולקבוצה השלישית, נקבל:
   = .
אבל לפי למה 2:  ו-: 
, ולכן:  ובכך נשלמה הוכחת משפט ההדדיות הריבועית.

הכללות

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