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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

משפט ההדדיות הריבועית נוסח לראשונה בידי אוילר ולז'נדר (שהוכיח אותו למקרים פרטיים), אך היה זה גאוס שהוכיח אותו במלואו לראשונה, בשנת 1796. גאוס כינה אותו בשם "משפט הזהב", וניתן לראות עדות לחיבה שרחש לו בכך שפרסם שש הוכחות שונות שלו במהלך חייו (ושתיים נוספות פרי עטו פורסמו לאחר מותו). מאז פורסמו הוכחות רבות נוספות; בשנת 2000 פורסם ספר שהכיל רשימה של לא פחות מ-196 הוכחות שונות‏[1]. מאז פרסום זה עובד המחבר על חלקים נוספים לספרו ומספר ההוכחות המעודכן עומד בדצמבר 2009 על 233‏[2].

ניסוח בסיסי[עריכת קוד מקור | עריכה]

בניסוחו הבסיסי, המשפט מקשר בין היכולת לפתור את שתי המשוואות הבאות: אם \ 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_i \equiv u a \pmod{p} ו-\ s_j \equiv v a \pmod{p}, אז \ u+v \equiv 0 \pmod{p}, והרי המכפלות בקבוצה S הן תמיד בגורמים קטנים מ- p/2.

אם כך, המספרים ברשימה הנ"ל שווים למספרים \ 1,2,\dots,(p-1)/2 בסדר כלשהו, ומכפלתם שווה ל- \ (p-1/2)!; לכן \ 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]}

הוכחה: נתבונן בקבוצת המספרים: {S = {a,2a,....,(p-1)/2a . נחלק את הכפולות הללו של a ב-p ונקבל: \ ka = qp + t כאשר לכל k קיימים q ו-t כלשהם המתאימים לו. \ ka/p = q + t/p ומאחר ש-q שלם ו-t קטן מ-p אזי נקבל: [q = [ka/p כלומר: \ ka = p[ka/p]+t. אם השארית t גדולה מ-p/2 אזי היא אחד מן המספרים

הוכחת משפט ההדדיות הריבועית: נתבונן בשתי הקבוצות הבאות: {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_1p_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 אינם ממשיים, משפטים אלו מתבססים על אריתמטיקה שמערבת את המספרים המרוכבים ואינה תלויה אך ורק במספרים רציונליים, ולכן שייכים יותר לתורת המספרים האלגברית.

ראו גם[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ ראה: Reciprocity Laws: From Euler to Eisenstein, Franz Lemmermeyer, Springer, 2000.
  2. ^ Proofs of the Quadratic Reciprocity Law