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

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש
גאוס פרסם את ההוכחה הראשונה והשנייה של חוק ההדדיות הריבועית במאמרים 125-146 ומאמר 262 של ספרו מחקרים אריתמטיים מ-1801.

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

חוק ההדדיות הריבועית:

יהיו p ו-q שני מספרים ראשוניים אי-זוגיים, אז נגדיר את סימן לז'נדר כך:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{q}{p}\right) =\left\{\begin{array}{rl} 1 & \text{if }\, n^2 \equiv q \!{\pmod p}\, \text{ for some integer } n,\\ -1 & \text{otherwise.} \end{array}\right.}

אז מתקיים:

הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle \left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}{\frac {q-1}{2}}}.}

חוק זה מאפשר חישוב ישיר של סימן לז'נדר, ומאפשר לקבוע האם ישנו פתרון טבעי למשוואה מודולרית מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^2\equiv a \!\!\!\pmod{p}} בעבור p ראשוני אי-זוגי; כלומר, במילים אחרות, לקבוע את "הריבועים המושלמים" מודולו p. בקריפטוגרפיה, המשפט מאפשר גם להכריע בשאלה האם מספר ראשוני נתון p הוא שארית ריבועית מודולו מספר ראשוני גדול בהרבה q במהירות רבה יותר: בעוד שבדיקה נאיבית של כל הריבועים מודולו q עשויה לצרוך זמן חישוב רב, המשפט מאפשר לקצר משמעותית את הבדיקה באמצעות בדיקה של q מודולו p (כך שיש לבדוק רק p ריבועים). אף על פי כן, המשפט הוא תוצאה לא-קונסטרוקטיבית: הוא לא מצביע על שיטה יעילה למציאה של פתרון כזה.

המשפט נחשב לנקודת ציון בתורת המספרים הקלאסית ולתוצאה מפתיעה מאוד; בעוד שבעבור קונגרואנציות ליניאריות משפט השאריות הסיני אומר לנו שההתנהגות של דברים מודולו מספר ראשוני מסוים p היא בלתי תלויה בהתנהגות שלהם מודולו מספר ראשוני אחר q, חוק ההדדיות הריבועית קובע התנהגות שונה עבור קונגרואנציות ריבועיות, ומראה שישנה תלות הדדית מסוימת בין ההתנהגויות -הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\frac{p}{q})} מגביל את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\frac{q}{p})} . בכך הוא מרמז על מבנה אריתמטי נסתר ועמוק יותר, ומבחינה היסטורית גילויו, הוכחתו והניסיונות להכלילו היו בין הזרזים העיקריים להתפתחות תורת המספרים המודרנית[1].

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

היסטוריה

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

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

מאז פורסמו הוכחות רבות נוספות; בשנת 2000 פורסם ספר שהכיל רשימה של לא פחות מ-196 הוכחות שונות.[3] מאז פרסום זה עובד המחבר על חלקים נוספים לספרו ומספר ההוכחות המעודכן עומד בדצמבר 2009 על 233.[4].

מוטיבציה וניסוח בסיסי

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

חוק ההדדיות הריבועית קובע כי מספר ראשוני q הוא שארית ריבועית מודולו מספר ראשוני p בהתניה בתוצאת הקונגרואנציה ההפוכה; בניסוחו הבסיסי, המשפט מקשר בין היכולת לפתור את שתי המשוואות הבאות: אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p,q} הם שני מספרים ראשוניים אי זוגיים, אז המשוואות הן:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^2\equiv p\ ({\rm mod}\ q) \qquad (A)}
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y^2\equiv q\ ({\rm mod}\ p) \qquad (B)}

כלומר, השאלה היא מתי כל אחד מהמספרים הוא ריבוע מודולו המספר השני.

על פי המשפט, התשובה לשאלה זו תלויה בשארית של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p,q} בחלוקה ב-4. אם השארית של שניהם בחלוקה ב-4 היא 3, קיים פתרון לאחת מהמשוואות אם ורק אם לא קיים פתרון לשנייה. לעומת זאת, אם השארית בחלוקה ב-4 של לפחות אחד משני הראשוניים היא 1, הרי שקיים פתרון לאחת מהמשוואת אם ורק אם קיים פתרון לשנייה, ומכאן נובע שם החוק "חוק ההדדיות הריבועית" - כלומר חייבת להיות הדדיות בפתירות הקונגרואנציות הריבועיות (במקרה השני).

דוגמה

אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p=13, q=17} (עבור שניהם, השארית בחלוקה ב-4 היא 1), קיימים פתרונות לשתי המשוואות:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 8^2 \equiv 13 \pmod{17} \,}
הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^2 \equiv 17 \pmod{13} \,}

לעומת זאת, אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p=5, q=13} (גם כאן, השארית בחלוקה ב-4 היא 1 עבור שניהם) לא קיים פתרון לאף אחת מהמשוואת (ניתן להיווכח בכך על ידי בדיקה ישירה).

כעת, אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p=7, q=19} אז השארית בחלוקה ב-4 של שני המספרים היא במקרה זה 3, וניתן לראות כי קיים פתרון למשוואה הראשונה:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 8^2 \equiv 7 \pmod{19} \,}

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

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

משפטי עזר

בנוסף למשפט המרכזי, ישנם שני משפטי עזר המתלווים אליו, ומאפשרים להשתמש בו בצורה כללית יותר. המשפט הראשון אומר כי אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p} הוא ראשוני אי זוגי, אז למשוואה:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^2 \equiv -1 \pmod p\,}

קיים פתרון אם ורק אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p} משאיר שארית 1 בחלוקה ב-4. לדוגמה, עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p=29} קיים הפתרון:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle {12}^2 \equiv -1 \pmod{29}}

אך עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p=7} לא קיים פתרון.

המשפט השני עוסק במשוואה:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^2 \equiv 2 \pmod p\,}

ועל פיו יש למשוואה פתרון אם ורק אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p} משאיר שארית של 1 או 7 בחלוקה ב-8.

ניסוח בעזרת סימן לז'נדר

ניתן לנסח את המשפט בצורה קומפקטית יותר באמצעות סימן לז'נדר, המוגדר בצורה הבאה עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p} ראשוני אי זוגי ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a} שלם כלשהו:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{a}{p}\right)=\left\{\begin{matrix}1 & \mathrm{if}\ a\ \mathrm{is\ a\ square\ modulo\ }p, \\ 0 & \mathrm{if\ } p\ \mathrm{divides\ }a, \\ -1 & \mathrm{otherwise,}\end{matrix}\right.}

בסימונים אלו, משפט ההדדיות הריבועית ומשפטי העזר יכולים להיות מנוסחים בצורה הבאה:

אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p,q} ראשוניים אי זוגיים, אז:

  • הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=\left(-1\right)^{\left(\frac{p-1}{2}\right)\left(\frac{q-1}{2}\right)}}

וכמו כן:

  • הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left(\frac{-1}{p}\right)=\left(-1\right)^{\left(\frac{p-1}{2}\right)}}
  • הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left(\frac{2}{p}\right)=\left(-1\right)^{\left(\frac{p^2-1}{8}\right)}}

הוכחה

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

למה 1: הלמה של גאוס: יהי p מספר ראשוני אי זוגי, ונניח ש- a זר ל- p. אם n הוא מספר המספרים בקבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ S = \{a,2a,3a,\dots,((p-1)/2)a\}} המשאירים שארית גדולה מ- p/2 כשמחלקים אותם ב-p, אז: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left(\frac{a}{p}\right) = (-1)^n} , כאשר ( ) הוא סימן לז'נדר.

הוכחה. מכיוון ש- a זר ל- p, כל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (p-1)/2} המספרים בקבוצה S שונים זה מזה מודולו p. נסמן ב- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r_1,\dots,r_m} את שאריות החילוק הקטנות מ- p/2, וב- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s_1,\dots,s_n} את שאריות החילוק הגדולות מ- p/2. המספרים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r_1,\dots,r_m,p-s_1,\dots,p-s_n} כולם חיוביים וקטנים מ- p/2. יתרה מזו, אלו מספרים שונים, מפני שאם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p-s_i = r_j} , כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r_j \equiv u a \pmod{p}} ו-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s_i \equiv v a \pmod{p}} , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ u+v \equiv 0 \pmod{p}} , והרי המכפלות בקבוצה S הן תמיד בגורמים קטנים מ- p/2.

אם כך, המספרים ברשימה הנ"ל שווים למספרים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 1,2,\dots,(p-1)/2} בסדר כלשהו, ומכפלתם שווה ל- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left(\frac{p-1}{2}\right)!} ; לכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r_1\dots r_m (p-s_1)\dots (p-s_n) = (-1)^n r_1 \dots r_m \cdot s_1 \dots s_n \equiv ((p-1)/2)! \pmod{p}} . מצד שני, המספרים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ r_1,\dots,r_m, s_1,\dots,s_n} מהווים סידור מחדש של הקבוצה S, ומכאן ש- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ ((p-1)/2)! \equiv (-1)^n \cdot a^{(p-1)/2} \cdot ((p-1)/2)! \pmod{p}} . לכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (-1)^n \equiv a^{(p-1)/2} \pmod{p}} . אבל לפי מבחן אוילר, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left(\frac{a}{p}\right) = a^{(p-1)/2}} .

למה 2: אם p הוא מספר ראשוני אי זוגי ו-a הוא מספר שלם אי זוגי המקיים 1 =(gcd(a,p אז:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{a}{p}\right) = (-1)^{\sum_{k=1}^{(p-1)/2}[ka/p]}}

הוכחה: בדומה ללמה של גאוס.

הוכחת משפט ההדדיות הריבועית: נתבונן בשתי הקבוצות הבאות: {N = {1,2,...,(p-1)/2 ו- {M = {1,2,...,(q-1)/2 . מספר הזוגות (m,n) כאשר m נבחר מתוך הקבוצה M ו-n נבחר מתוך הקבוצה N שווה לפי עקרון כפל האפשרויות ל- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (p-1)/2\cdot(q-1)/2 } . נחלק את קבוצות הזוגות (m,n) לשלוש קבוצות: האחת אשר הזוגות בה מקיימים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n/m < p/q} , השנייה: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n/m = p/q} , השלישית: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n/m > p/q} . אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ n/m = p/q} אז נקבל: nq = pm, ומאחר ש-p ו-q זרים נקבל ש-q מחלק את m, סתירה, לכן אין זוגות כאלה. לכל m, מספר המספרים הטבעיים n הקיימים את התנאי בקבוצה הראשונה הוא בדיוק [mp/q] ולכל n מספר המספרים הטבעיים m המקיימים את התנאי בקבוצה השלישית הוא בדיוק [nq/p]. מאחר שסה"כ הזוגות הסדורים (m,n) שווה לסכום הזוגות המשתייכים לקבוצה הראשונה ולקבוצה השלישית, נקבל:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (p-1)/2\cdot(q-1)/2 } = הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\sum_{m=1}^{(q-1)/2}[mp/q]} + {\sum_{n=1}^{(p-1)/2}[nq/p]}} .

אבל לפי למה 2: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{q}{p}\right) = (-1)^{\sum_{m=1}^{(p-1)/2}[mq/p]}} ו-: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{p}{q}\right) = (-1)^{\sum_{n=1}^{(q-1)/2}[np/q]}} , ולכן: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{p}{q}\right)\cdot\left(\frac{q}{p}\right)= (-1)^{(p-1)/2\cdot(q-1)/2} } ובכך נשלמה הוכחת משפט ההדדיות הריבועית.

הכללה לסימן יעקובי

בהינתן מספר שלם אי זוגי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b} מגדירים את סימן יעקובי באמצעות סימן לז'נדר בצורה הבאה: אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b=p_1p_2\cdots p_m} הוא פירוק לגורמים של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ b} (הגורמים אינם בהכרח שונים זה מזה) אז סימן יעקובי מוגדר כך לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a} שלם:

  • הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left(\frac{a}{b}\right)=\left(\frac{a}{p_1}\right)\left(\frac{a}{p_2}\right)\cdots\left(\frac{a}{p_m}\right)}

תחת הכללה זו ניתן לנסח את משפט ההדדיות הריבועית בצורה דומה עבור סימן יעקובי: אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a,b} שני מספרים שלמים אי זוגיים חיוביים, אז:

  • הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left(\frac{a}{b}\right)\left(\frac{b}{a}\right)=\left(-1\right)^{\left(\frac{a-1}{2}\right)\left(\frac{b-1}{2}\right)}}
  • הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left(\frac{-1}{b}\right)=\left(-1\right)^{\left(\frac{b-1}{2}\right)}}
  • הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left(\frac{2}{b}\right)=\left(-1\right)^{\left(\frac{b^2-1}{8}\right)}}

דוגמה לשימוש

  • 3 הוא שארית ריבועית מודולו p אם ורק אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p \equiv \pm 1 \pmod{12}} .

נניח כי רוצים לדעת האם קיים פתרון למשוואה:

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^2 \equiv 17 \pmod {31}\,}

נראה כיצד לעשות זאת תוך שימוש במשפט ההדדיות הריבועית ובשתי תכונות בסיסיות של סימן לז'נדר:

  • הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)}
  • אםהפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a \equiv b\pmod p\,} , אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)}

בעזרת המשפט ושתי תכונות אלו נקבל:

  • הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \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\left(-1\right)^{\left(\frac{31-1}{2}\right)\left(\frac{17-1}{2}\right)}=\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)}

כאשר המעבר האחרון נובע מכך ש-17 מתחלק ב-8 עם שארית 1 ולכן: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left(\frac{2}{17}\right)=1}

כעת, נמשיך בצורה דומה:

  • הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left(\frac{7}{17}\right)=\left(\frac{17}{7}\right)\cdot\left(-1\right)^{\left(\frac{17-1}{2}\right)\left(\frac{7-1}{2}\right)}=\left(\frac{17}{7}\right)=\left(\frac{3}{7}\right)}

ושוב נעשה את אותו הדבר בדיוק:

  • הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left(\frac{3}{7}\right)=\left(\frac{7}{3}\right)\cdot\left(-1\right)^{\left(\frac{7-1}{2}\right)\left(\frac{3-1}{2}\right)}=-\left(\frac{7}{3}\right)=-\left(\frac{1}{3}\right)=-1}

וקיבלנו שאין למשוואה פתרון. המעבר האחרון נובע מכך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left(\frac{1}{p}\right)=1} לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p} (למעשה, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \left(\frac{a^2}{p}\right)=1} לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ p} ראשוני ולכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ a} , על פי הגדרה).

הכללות

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

ראו גם

קישורים חיצוניים

הערות שוליים

  1. ↑ Gauss' Quadratic Reciprocity Law [1]
  2. ↑ Gauss linking integral and quadratic reciprocity [2]
  3. ↑ Reciprocity Laws: From Euler to Eisenstein, Franz Lemmermeyer, Springer, 2000.
  4. ↑ Proofs of the Quadratic Reciprocity Law
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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

אוחזר מתוך "https://www.hamichlol.org.il/w/index.php?title=משפט_ההדדיות_הריבועית&oldid=3059203"