שארית ריבועית – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ שוחזר מעריכה של 217.132.54.54 (שיחה) לעריכה האחרונה של 89.0.213.23 |
מ שינוי מבנה של משפט-הוכחה |
||
שורה 1:
ב[[תורת המספרים]], מספר a נקרא '''שארית ריבועית''' [[חשבון מודולרי|מודולו]] מספר n אם קיים פתרון [[מספר שלם|שלם]] למשוואה <math>\ x^2 \equiv a \pmod{n}</math>. זהו מושג קלאסי, שנחקר על-ידי
אם <math>\ n=p>2</math> [[מספר ראשוני|ראשוני]], אז למעט השארית 0, יש בדיוק <math>\ \frac{p-1}{2}</math> שאריות ריבועיות, ו- <math>\ \frac{p-1}{2}</math> שאריות שאינן ריבועיות. לדוגמה, השאריות הריבועיות מודולו 11 הן 1,3,4,5,9, בעוד ש- 2,6,7,8,10 אינן שאריות ריבועיות. בזכות הפיזור האקראי-לכאורה של השאריות, יש למושג זה שימושים רבים בתחומים שונים של ה[[קומבינטוריקה]], וגם מחוץ ל[[מתמטיקה]].
שורה 10:
==תכונות בסיסיות==
:<math>\ a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right)\pmod{p}</math>. אם <math>\ a\equiv x^2\pmod{p}</math>, אז <math>\ a^{\frac{p-1}{2}}\equiv x^{p-1} \equiv 1\pmod{p}</math> לפי [[משפט לגראנז' (תורת החבורות)|משפט לגראנז']], מכיוון ש[[סדר (תורת החבורות)|סדרה]] של חבורת אוילר הוא p-1. בכך הוכחנו שאם אגף ימין שווה ל- 1, אז כך גם אגף שמאל. מצד שני, לכל מספר שונה מאפס בשדה שיש לו שורש ריבועי, יש בדיוק שניים. זה מוכיח שיש <math>\ \frac{p-1}{2}</math> שאריות ריבועיות, אבל למשוואה <math>\ a^{\frac{p-1}{2}}\equiv 1</math> לא יכולים להיות יותר מ- <math>\ \frac{p-1}{2}</math> שורשים, כיוון ש-<math>\ \mathbb{Z}/p\mathbb{Z}</math> הוא [[שדה (מבנה אלגברי)|שדה]]; מכאן שכל השורשים הם שאריות ריבועיות. כדי לסיים את ההוכחה מספיק להבחין ש- <math>\ (a^{\frac{p-1}{2}})^2 = a^{p-1} \equiv 1</math> כמקודם, ולכן אגף שמאל שווה תמיד לפלוס או מינוס 1; מכאן שהוא שווה למינוס 1 עבור השאריות שאינן ריבועיות. ▼
בפרט, מהנוסחה הזו נובעת תוצאה חשובה לגבי הריבועיות של 1-:
▲אם <math>\ a\equiv x^2\pmod{p}</math>, אז <math>\ a^{\frac{p-1}{2}}\equiv x^{p-1} \equiv 1\pmod{p}</math> לפי [[משפט לגראנז' (תורת החבורות)|משפט לגראנז']], מכיוון ש[[סדר (תורת החבורות)|סדרה]] של חבורת אוילר הוא p-1. בכך הוכחנו שאם אגף ימין שווה ל- 1, אז כך גם אגף שמאל. מצד שני, לכל מספר שונה מאפס בשדה שיש לו שורש ריבועי, יש בדיוק שניים. זה מוכיח שיש <math>\ \frac{p-1}{2}</math> שאריות ריבועיות, אבל למשוואה <math>\ a^{\frac{p-1}{2}}\equiv 1</math> לא יכולים להיות יותר מ- <math>\ \frac{p-1}{2}</math> שורשים; מכאן שכל השורשים הם שאריות ריבועיות. כדי לסיים את ההוכחה מספיק להבחין ש- <math>\ (a^{\frac{p-1}{2}})^2 = a^{p-1} \equiv 1</math> כמקודם, ולכן אגף שמאל שווה תמיד לפלוס או מינוס 1; מכאן שהוא שווה למינוס 1 עבור השאריות שאינן ריבועיות.
:<math>\ \left(\frac{-1}{p}\right)\equiv (-1)^{\frac{p-1}{2}} \pmod{p}</math>
מתוצאה זו נובע (בעזרת שיטת ה[[נסיגה אינסופית|נסיגה האינסופית]] שפיתח [[לאונרד אוילר|אוילר]]) שניתן להציג כל מספר ראשוני מן הסוג הראשון, כסכום של שני ריבועים (למשל, <math>\ 73=8^2+3^2</math>). עובדה זו קובעת את הפירוק לראשוניים ב[[חוג השלמים של גאוס]], והיא מדגימה את הקשר בין שאריות ריבועיות, [[תבניות ריבועיות]] בינארית, ופירוק לראשוניים בחוג שלמים של [[שדה מספרים]] [[הרחבה ריבועית|ריבועי]].
תכונה זו מסייעת לחישוב סימן לז'נדר באמצעות משפט ההדדיות הריבועית, שכן היא מאפשרת לפרק את המספר שבודקים את סימן לז'נדר שלו לגורמים ראשוניים.
▲אם a,b אינם שניהם זרים ל-p התוצאה מיידית (שני האגפים שווים ל-0). אחרת:
<math>\ \left(\frac{ab}{p}\right)\equiv (ab)^{\frac{p-1}{2}}=a^{\frac{p-1}{2}}b^{\frac{p-1}{2}}\equiv\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\pmod{p}</math>
קיבלנו שקילות מודולו p של שני האגפים, ומכיוון ששניהם יכולים לקבל רק את הערך 1 או מינוס 1, מתקיים שוויון ממש.
[[קטגוריה: תורת המספרים]]
| |||