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

משפט ההדדיות הריבועית הוא משפט בתורת המספרים הנוגע לחשבון מודולרי. הוא נותן תנאי כללי לדעת מתי משוואה ריבועית x^2 ≡ a (מודול p) имеет פתרון כש-p ו-q הם מספרים ראשוניים אי-זוגיים. האינטואיציה היא שהפתירות של x^2≡p (מודול q) והפתירות של y^2≡q (מודול p) קשורות זו בזו.

המשפט נוסח במובנים שונים. סימן לז'נדר, (a/p), מוגדר כך: הוא 1 אם a הוא שארית ריבועית מודולו p (כלומר קיים n כך ש-n^2≡a (מודול p)), 0 אם p מחלק את a, ו-1- אם אין כזה n. בניסוח הקלאסי עבור שני ראשוניים אי-זוגיים p,q מתקיים:

(p/q)(q/p)=(-1)^{((p-1)/2)((q-1)/2)}

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

המשפט הוזכר לראשונה על ידי אוילר ולז'נדר בחלק מהמקרים. קרל פרידריך גאוס הוכיח אותו במלואו בשנת 1796. גאוס כינה אותו "משפט הזהב" ופרסם כמה הוכחות שונות במהלך חייו. מאז נמצאו מאות הוכחות נוספות.

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

אם p=13 ו-q=17 (שניהם נותרים 1 בחלוקה ב-4) יש פתרונות לשתי המשוואות: 8^2≡13 (מודול 17) ו-2^2≡17 (מודול 13). אם p=7 ו-q=19 (שתיהן שאריתן 3 בחלוקה ב-4), קיימת פתרון לאחת מהמשוואות בלבד.

קיימים שני משפטי עזר שימושיים:
- המשוואה x^2≡-1 (מודול p) נפתרת אם ורק אם p נותן שארית 1 בחלוקה ב-4.
- המשוואה x^2≡2 (מודול p) נפתרת אם ורק אם p נותיר שארית 1 או 7 בחלוקה ב-8.

המשפט והמשפטים הנוספים ניתנים לכתיבה קומפקטית באמצעות סימן לז'נדר. לדוגמה:
(p/q)(q/p)=(-1)^{((p-1)/2)((q-1)/2)},
(-1/p)=(-1)^{(p-1)/2},
(2/p)=(-1)^{(p^2-1)/8}.

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

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

לבדיקת קיומה של פתרון ל-x^2≡17 (מודול 31) משתמשים בחוק ההדדיות ובתכונות בסיסיות של סימן לז'נדר. לאחר סדרה של החלפות ויישום הכללים מקבלים (17/31)=-1, כלומר אין פתרון.

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

משפט ההדדיות הריבועית עוזר לדעת מתי יש פתרון למשוואה x^2 ≡ a כשחושבים מודול מספר ראשוני. חשבו מודולו כאילו בודקים שארית אחרי חלוקה.

סימן לז'נדר אומר אם מספר a הוא "ריבוע" מודולו p. אם כן הוא 1. אם p מחלק את a הוא 0. אם לא, הוא -1. המשפט אומר שיש קשר בין (p מול q) ו-(q מול p) עבור שני ראשוניים אי-זוגיים.

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

השאלה היא: מתי מספר הוא ריבוע אם בודקים מודולו p? החוק מקשר בין שתי בדיקות כאלה לשני מספרים ראשוניים שונים.

אם p=13 ו-q=17 שניהם נותרים 1 בחלוקה ב-4. אז קיימים פתרונות לשתי המשוואות. אם p=7 ו-q=19 שניהם נותרים 3 בחלוקה ב-4. יש פתרון רק לאחת מהן.

- x^2≡-1 יש פתרון אם רק אם p נותן שארית 1 ב-4.
- x^2≡2 יש פתרון אם רק אם p נותן שארית 1 או 7 ב-8.

במקום לכתוב תיאורים ארוכים, משתמשים בסימן לז'נדר כדי לרשום את הכללים בקיצור. זה מקל על בדיקה של שאריות ריבועיות.

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

אם המספר b אינו ראשוני, אפשר לפרק אותו לגורמים ולהגדיר סימן כללי בשם סימן יעקובי. כך אפשר לבדוק גם מקרים מורכבים יותר.

ניתן להשתמש בחוק כדי לבדוק אם x^2≡17 (מודול 31) נפתרת. לפי החישוב המשתמש בהדדיות, אין פתרון.

יש גרסאות מתקדמות יותר לחזקות גבוהות יותר. הן דורשות כלים מהממתמטיקה המתקדמת.