![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/e/e3/Disqvisitiones-800.jpg/640px-Disqvisitiones-800.jpg&w=640&q=50)
משפט ההדדיות הריבועית
ויקיפדיה האנציקלופדיה encyclopedia
בתורת המספרים, משפט ההדדיות הריבועית הוא משפט בחשבון מודולרי המספק תנאים לפתירות של משוואות ריבועיות מודולו מספרים ראשוניים. המשפט למעשה מקשר בין היכולת לפתור שתי משוואות מודולריות ריבועיות. הוא נוסח לראשונה בידי אוילר ולז'נדר (שהוכיח אותו למקרים פרטיים), אך היה זה גאוס שהוכיח אותו במלואו לראשונה, בשנת 1796. למשפט יש ניסוחים רבים, אך הקביעה הסטנדרטית ביותר שלו היא כדלהלן:
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e3/Disqvisitiones-800.jpg/320px-Disqvisitiones-800.jpg)
יהיו שני מספרים ראשוניים אי-זוגיים שונים, אז נגדיר את סימן לז'נדר כך:
אז מתקיים
חוק זה מאפשר חישוב ישיר של סימן לז'נדר, ומאפשר לקבוע האם ישנו פתרון טבעי למשוואה מודולרית מהצורה בעבור
ראשוני אי-זוגי; כלומר, במילים אחרות, לקבוע את "הריבועים המושלמים" מודולו
. בקריפטוגרפיה, המשפט מאפשר גם להכריע בשאלה האם מספר ראשוני נתון
הוא שארית ריבועית מודולו מספר ראשוני גדול בהרבה
במהירות רבה יותר: בעוד שבדיקה נאיבית של כל הריבועים מודולו
עשויה לצרוך זמן חישוב רב, המשפט מאפשר לקצר משמעותית את הבדיקה באמצעות בדיקה של
מודולו
(כך שיש לבדוק רק
ריבועים). אף על פי כן, המשפט הוא תוצאה לא-קונסטרוקטיבית: הוא לא מצביע על שיטה יעילה למציאה של פתרון כזה.
המשפט נחשב לנקודת ציון בתורת המספרים הקלאסית ולתוצאה מפתיעה מאוד; בעוד שבעבור קונגרואנציות ליניאריות משפט השאריות הסיני אומר לנו שההתנהגות של דברים מודולו מספר ראשוני מסוים היא בלתי תלויה בהתנהגות שלהם מודולו מספר ראשוני אחר q, חוק ההדדיות הריבועית קובע התנהגות שונה עבור קונגרואנציות ריבועיות, ומראה שישנה תלות הדדית מסוימת בין ההתנהגויות –
מגביל את
. בכך הוא מרמז על מבנה אריתמטי נסתר ועמוק יותר, ומבחינה היסטורית גילויו, הוכחתו והניסיונות להכלילו היו בין הזרזים העיקריים להתפתחות תורת המספרים המודרנית[1].
מאז גאוס, הכללת חוק ההדדיות הייתה לבעיה מובילה במתמטיקה, ששיחקה תפקיד מרכזי בהתפתחות רבים מהכלים הטכניים של האלגברה, תורת המספרים, והגאומטריה האלגברית המודרנית, כשתהליך זה הגיע לשיאו בניסוח חוק ההדדיות של ארטין, תורת שדות המחלקה ותוכנית לנגלנדס. בנוסף, מחקר מתמטי של המאה ה-20 העיד על יותר ויותר קשרים מעניינים של המשפט עם תאוריות מתמטיות שונות מתחומי הגאומטריה והטופולוגיה – למשל, בתורת הקשרים, שם מושג הקשר הראשוני אנלוגי למספר ראשוני באריתמטיקה, ואת תפקיד ההדדיות הריבועית ממלא המשפט שקובע שאינדקס השזירה סימטרי ביחס להחלפה של שני קשרים ראשוניים[2].