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

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

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

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

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

$\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.$

אז מתקיים:

$\left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}{\frac {q-1}{2}}}.$

חוק זה מאפשר חישוב ישיר של סימן לז'נדר, ומאפשר לקבוע האם ישנו פתרון טבעי למשוואה מודולרית מהצורה $x^{2}\equiv a\!\!\!{\pmod {p}}$ בעבור p ראשוני אי-זוגי; כלומר, במילים אחרות, לקבוע את "הריבועים המושלמים" מודולו p. בקריפטוגרפיה, המשפט מאפשר גם להכריע בשאלה האם מספר ראשוני נתון p הוא שארית ריבועית מודולו מספר ראשוני גדול בהרבה q במהירות רבה יותר: בעוד שבדיקה נאיבית של כל הריבועים מודולו q עשויה לצרוך זמן חישוב רב, המשפט מאפשר לקצר משמעותית את הבדיקה באמצעות בדיקה של q מודולו p (כך שיש לבדוק רק p ריבועים). אף על פי כן, המשפט הוא תוצאה לא-קונסטרוקטיבית: הוא לא מצביע על שיטה יעילה למציאה של פתרון כזה.

המשפט נחשב לנקודת ציון בתורת המספרים הקלאסית ולתוצאה מפתיעה מאוד; בעוד שבעבור קונגרואנציות ליניאריות משפט השאריות הסיני אומר לנו שההתנהגות של דברים מודולו מספר ראשוני מסוים p היא בלתי תלויה בהתנהגות שלהם מודולו מספר ראשוני אחר q, חוק ההדדיות הריבועית קובע התנהגות שונה עבור קונגרואנציות ריבועיות, ומראה שישנה תלות הדדית מסוימת בין ההתנהגויות -$({\frac {p}{q}})$ מגביל את $({\frac {q}{p}})$. בכך הוא מרמז על מבנה אריתמטי נסתר ועמוק יותר, ומבחינה היסטורית גילויו, הוכחתו והניסיונות להכלילו היו בין הזרזים העיקריים להתפתחות תורת המספרים המודרנית.

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

היסטוריה

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

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

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

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

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

חוק ההדדיות הריבועית קובע כי מספר ראשוני q הוא שארית ריבועית מודולו מספר ראשוני p בהתניה בתוצאת הקונגרואנציה ההפוכה; בניסוחו הבסיסי, המשפט מקשר בין היכולת לפתור את שתי המשוואות הבאות: אם $\ p,q$ הם שני מספרים ראשוניים אי זוגיים, אז המשוואות הן:

$x^{2}\equiv p\ ({\rm {mod}}\ q)\qquad (A)$

$y^{2}\equiv q\ ({\rm {mod}}\ p)\qquad (B)$

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

על פי המשפט, התשובה לשאלה זו תלויה בשארית של $\ p,q$ בחלוקה ב-4. אם השארית של שניהם בחלוקה ב-4 היא 3, קיים פתרון לאחת מהמשוואות אם ורק אם לא קיים פתרון לשנייה. לעומת זאת, אם השארית בחלוקה ב-4 של לפחות אחד משני הראשוניים היא 1, הרי שקיים פתרון לאחת מהמשוואת אם ורק אם קיים פתרון לשנייה, ומכאן נובע שם החוק "חוק ההדדיות הריבועית" - כלומר חייבת להיות הדדיות בפתירות הקונגרואנציות הריבועיות (במקרה השני).

דוגמה

אם $\ p=13,q=17$ (עבור שניהם, השארית בחלוקה ב-4 היא 1), קיימים פתרונות לשתי המשוואות:

$8^{2}\equiv 13{\pmod {17}}\,$

$2^{2}\equiv 17{\pmod {13}}\,$

לעומת זאת, אם $\ p=5,q=13$ (גם כאן, השארית בחלוקה ב-4 היא 1 עבור שניהם) לא קיים פתרון לאף אחת מהמשוואת (ניתן להיווכח בכך על ידי בדיקה ישירה).

כעת, אם $\ p=7,q=19$ אז השארית בחלוקה ב-4 של שני המספרים היא במקרה זה 3, וניתן לראות כי קיים פתרון למשוואה הראשונה:

$8^{2}\equiv 7{\pmod {19}}\,$

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

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

משפטי עזר

בנוסף למשפט המרכזי, ישנם שני משפטי עזר המתלווים אליו, ומאפשרים להשתמש בו בצורה כללית יותר. המשפט הראשון אומר כי אם $\ p$ הוא ראשוני אי זוגי, אז למשוואה:

$x^{2}\equiv -1{\pmod {p}}\,$

קיים פתרון אם ורק אם $\ p$ משאיר שארית 1 בחלוקה ב-4. לדוגמה, עבור $\ p=29$ קיים הפתרון:

${12}^{2}\equiv -1{\pmod {29}}$

אך עבור $\ p=7$ לא קיים פתרון.

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

$x^{2}\equiv 2{\pmod {p}}\,$

ועל פיו יש למשוואה פתרון אם ורק אם $\ p$ משאיר שארית של 1 או 7 בחלוקה ב-8.

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

ניתן לנסח את המשפט בצורה קומפקטית יותר באמצעות סימן לז'נדר, המוגדר בצורה הבאה עבור $\ p$ ראשוני אי זוגי ו-$\ a$ שלם כלשהו:

$\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.$

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

אם $\ p,q$ ראשוניים אי זוגיים, אז:

• $\ \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)}$

וכמו כן:

• $\ \left({\frac {-1}{p}}\right)=\left(-1\right)^{\left({\frac {p-1}{2}}\right)}$
• $\ \left({\frac {2}{p}}\right)=\left(-1\right)^{\left({\frac {p^{2}-1}{8}}\right)}$

הוכחה

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

למה 1: הלמה של גאוס: יהי p מספר ראשוני אי זוגי, ונניח ש- a זר ל- p. אם n הוא מספר המספרים בקבוצה $\ S=\{a,2a,3a,\dots ,((p-1)/2)a\}$ המשאירים שארית גדולה מ- p/2 כשמחלקים אותם ב-p, אז: $\ \left({\frac {a}{p}}\right)=(-1)^{n}$, כאשר ( ) הוא סימן לז'נדר.

הוכחה. מכיוון ש- a זר ל- p, כל $\ (p-1)/2$ המספרים בקבוצה S שונים זה מזה מודולו p. נסמן ב- $\ r_{1},\dots ,r_{m}$ את שאריות החילוק הקטנות מ- p/2, וב- $\ s_{1},\dots ,s_{n}$ את שאריות החילוק הגדולות מ- p/2. המספרים $\ r_{1},\dots ,r_{m},p-s_{1},\dots ,p-s_{n}$ כולם חיוביים וקטנים מ- p/2. יתרה מזו, אלו מספרים שונים, מפני שאם $\ p-s_{i}=r_{j}$, כאשר $\ r_{j}\equiv ua{\pmod {p}}$ ו-$\ s_{i}\equiv va{\pmod {p}}$, $\ u+v\equiv 0{\pmod {p}}$, והרי המכפלות בקבוצה S הן תמיד בגורמים קטנים מ- p/2.

אם כך, המספרים ברשימה הנ"ל שווים למספרים $\ 1,2,\dots ,(p-1)/2$ בסדר כלשהו, ומכפלתם שווה ל- $\ \left({\frac {p-1}{2}}\right)!$; לכן $\ 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}}$. מצד שני, המספרים $\ r_{1},\dots ,r_{m},s_{1},\dots ,s_{n}$ מהווים סידור מחדש של הקבוצה S, ומכאן ש- $\ ((p-1)/2)!\equiv (-1)^{n}\cdot a^{(p-1)/2}\cdot ((p-1)/2)!{\pmod {p}}$. לכן $\ (-1)^{n}\equiv a^{(p-1)/2}{\pmod {p}}$. אבל לפי מבחן אוילר, $\ \left({\frac {a}{p}}\right)=a^{(p-1)/2}$.

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

$\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 שווה לפי עקרון כפל האפשרויות ל- $(p-1)/2\cdot (q-1)/2$ . נחלק את קבוצות הזוגות (m,n) לשלוש קבוצות: האחת אשר הזוגות בה מקיימים: $\ n/m<p/q$, השנייה: $\ n/m=p/q$, השלישית: $\ n/m>p/q$. אם $\ n/m=p/q$ אז נקבל: nq = pm, ומאחר ש-p ו-q זרים נקבל ש-q מחלק את m, סתירה, לכן אין זוגות כאלה. לכל m, מספר המספרים הטבעיים n הקיימים את התנאי בקבוצה הראשונה הוא בדיוק [mp/q] ולכל n מספר המספרים הטבעיים m המקיימים את התנאי בקבוצה השלישית הוא בדיוק [nq/p]. מאחר שסה"כ הזוגות הסדורים (m,n) שווה לסכום הזוגות המשתייכים לקבוצה הראשונה ולקבוצה השלישית, נקבל:

$(p-1)/2\cdot (q-1)/2$ = ${\sum _{m=1}^{(q-1)/2}[mp/q]}+{\sum _{n=1}^{(p-1)/2}[nq/p]}$.

אבל לפי למה 2: $\left({\frac {q}{p}}\right)=(-1)^{\sum _{m=1}^{(p-1)/2}[mq/p]}$ ו-: $\left({\frac {p}{q}}\right)=(-1)^{\sum _{n=1}^{(q-1)/2}[np/q]}$, ולכן: $\left({\frac {p}{q}}\right)\cdot \left({\frac {q}{p}}\right)=(-1)^{(p-1)/2\cdot (q-1)/2}$ ובכך נשלמה הוכחת משפט ההדדיות הריבועית.

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

בהינתן מספר שלם אי זוגי $\ b$ מגדירים את סימן יעקובי באמצעות סימן לז'נדר בצורה הבאה: אם $\ b=p_{1}p_{2}\cdots p_{m}$ הוא פירוק לגורמים של $\ b$ (הגורמים אינם בהכרח שונים זה מזה) אז סימן יעקובי מוגדר כך לכל $\ a$ שלם:

• $\ \left({\frac {a}{b}}\right)=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_{2}}}\right)\cdots \left({\frac {a}{p_{m}}}\right)$

תחת הכללה זו ניתן לנסח את משפט ההדדיות הריבועית בצורה דומה עבור סימן יעקובי: אם $\ a,b$ שני מספרים שלמים אי זוגיים חיוביים, אז:

• $\ \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)}$
• $\ \left({\frac {-1}{b}}\right)=\left(-1\right)^{\left({\frac {b-1}{2}}\right)}$
• $\ \left({\frac {2}{b}}\right)=\left(-1\right)^{\left({\frac {b^{2}-1}{8}}\right)}$

דוגמה לשימוש

• 3 הוא שארית ריבועית מודולו p אם ורק אם $\ p\equiv \pm 1{\pmod {12}}$.

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

$x^{2}\equiv 17{\pmod {31}}\,$

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

• $\ \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)$
• אם$\ a\equiv b{\pmod {p}}\,$, אז $\left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)$

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

• $\ \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 ולכן: $\ \left({\frac {2}{17}}\right)=1$

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

• $\ \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)$

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

• $\ \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$

וקיבלנו שאין למשוואה פתרון. המעבר האחרון נובע מכך ש-$\ \left({\frac {1}{p}}\right)=1$ לכל $\ p$ (למעשה, $\ \left({\frac {a^{2}}{p}}\right)=1$ לכל $\ p$ ראשוני ולכל $\ a$, על פי הגדרה).

הכללות

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

ראו גם

• שארית ריבועית
• הלמה של גאוס

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

• הסבר מאיר עיניים על משפט ההדדיות הריבועית בערוץ היוטיוב Mathologer
• משפט ההדדיות הריבועית, באתר MathWorld (באנגלית)

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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