משפט ההדדיות הריבועית – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ תמונות - הסבה לעברית, תיקון פרמטרים (תג) |
מ ←פתיח: תיקון קישור |
||
שורה 13:
:<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> בעבור ''p'' ראשוני אי-זוגי; כלומר, במילים אחרות, לקבוע את "הריבועים המושלמים" מודולו ''p''. ב[[קריפטוגרפיה]], המשפט מאפשר גם להכריע בשאלה האם מספר ראשוני נתון ''p'' הוא [[שארית ריבועית]] מודולו מספר ראשוני גדול בהרבה ''q'' במהירות רבה יותר: בעוד שבדיקה נאיבית של כל הריבועים מודולו ''q'' עשויה לצרוך זמן חישוב רב, המשפט מאפשר לקצר משמעותית את הבדיקה באמצעות בדיקה של ''q'' מודולו ''p'' (כך שיש לבדוק רק ''p'' ריבועים). אף על פי כן, המשפט הוא תוצאה [[הוכחה לא קונסטרוקטיבית|לא-קונסטרוקטיבית]]: הוא לא מצביע על שיטה [[יעילות אלגוריתמית|יעילה]] למציאה של פתרון כזה.
המשפט נחשב לנקודת ציון בתורת המספרים הקלאסית ולתוצאה מפתיעה מאוד; בעוד שבעבור קונגרואנציות ליניאריות [[משפט השאריות הסיני]] אומר לנו שההתנהגות של דברים מודולו [[מספר ראשוני]] מסוים ''p'' היא בלתי תלויה בהתנהגות שלהם מודולו מספר ראשוני אחר ''q'', חוק ההדדיות הריבועית קובע התנהגות שונה עבור קונגרואנציות ריבועיות, ומראה שישנה תלות הדדית מסוימת בין ההתנהגויות -<math>(\frac{p}{q})</math> מגביל את <math>(\frac{q}{p})</math>. בכך הוא מרמז על מבנה אריתמטי נסתר ועמוק יותר, ומבחינה היסטורית גילויו, הוכחתו והניסיונות להכלילו היו בין הזרזים העיקריים להתפתחות תורת המספרים המודרנית{{הערה|Gauss' Quadratic Reciprocity Law
| |||