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

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

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

תוכן עניינים

1 ניסוח בסיסי
- 1.1 דוגמה
- 1.2 משפטי עזר
2 ניסוח בעזרת סימן לז'נדר
- 2.1 הכללה לסימן יעקובי
3 דוגמה לשימוש
4 הכללות

[עריכה] ניסוח בסיסי

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

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

$x^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)}$

[עריכה] הכללה לסימן יעקובי

בהינתן מספר שלם אי זוגי $\ 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)}$

[עריכה] דוגמה לשימוש

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

$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)=\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)$ לכל $\ p$ (למעשה, $\ \left(\frac{a^2}{p}\right)=1$ לכל $\ p$ ראשוני ולכל $\ a$ , על פי הגדרה).

[עריכה] הכללות

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

מקור: http://he.wikipedia.org../../../%D7%9E/%D7%A9/%D7%A4/%D7%9E%D7%A9%D7%A4%D7%98_%D7%94%D7%94%D7%93%D7%93%D7%99%D7%95%D7%AA_%D7%94%D7%A8%D7%99%D7%91%D7%95%D7%A2%D7%99%D7%AA.html

קטגוריות: תורת המספרים | משפטים מתמטיים

We provide Linux to the World

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

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

תוכן עניינים

[עריכה] ניסוח בסיסי

[עריכה] דוגמה

[עריכה] משפטי עזר

[עריכה] ניסוח בעזרת סימן לז'נדר

[עריכה] הכללה לסימן יעקובי

[עריכה] דוגמה לשימוש

[עריכה] הכללות

Views

ניווט

קהילה

חיפוש

שפות אחרות