שארית ריבועית

בתורת המספרים, מספר a נקרא שארית ריבועית מודולו מספר n אם קיים פתרון שלם למשוואה המודולרית $\ x^{2}\equiv a{\pmod {n}}$. זהו מושג קלאסי, שנחקר על ידי מתמטיקאים מן המאה ה-17 ואילך.

אם $\ n=p>2$ ראשוני, אז למעט השארית 0, יש בדיוק $\ {\frac {p-1}{2}}$ שאריות ריבועיות, ו- $\ {\frac {p-1}{2}}$ שאריות שאינן ריבועיות. לדוגמה, השאריות הריבועיות מודולו 11 הן 1,3,4,5,9, בעוד ש- 2,6,7,8,10 אינן שאריות ריבועיות. בזכות הפיזור האקראי-לכאורה של השאריות, יש למושג זה שימושים רבים בתחומים שונים של הקומבינטוריקה, וגם מחוץ למתמטיקה.

כדי להכריע האם a הוא שארית ריבועית מודולו מספר נתון n, יש לפרק את n לגורמים ראשוניים, $\ n=p_{1}^{\alpha _{1}}\dots p_{t}^{\alpha _{t}}$. ממשפט השאריות הסיני נובע שמספר הוא שארית ריבועית מודולו n אם ורק אם הוא שארית ריבועית מודולו כל אחד מן הגורמים הזרים שלו (החזקות $\ p_{i}^{\alpha _{i}}$).

כאשר p ראשוני אי-זוגי ו- a זר ל-p, אז a הוא שארית ריבועית מודולו חזקות של p אם ורק אם הוא שארית ריבועית מודולו p עצמו. עבור חזקות של 2, מספר איזוגי הוא שארית ריבועית מודולו חזקות גבוהות של 2 אם ורק אם הוא שארית ריבועית מודולו 8. לדוגמה, 5 הוא שארית ריבועית מודולו 2 או 4, אבל לא מודולו 8. לגבי הבעיה החישובית של מציאת השורש כאשר a הוא שארית ריבועית, ראו הוצאת שורש ריבועי.

את הבעיה של זיהוי שאריות ריבועיות מודולו p ראשוני, מקודדים בסימן לז'נדר. הסימן מוגדר לפי $\ \left({\frac {a}{p}}\right)=+1$ אם a זר ל- p והוא שארית ריבועית, $\ \left({\frac {a}{p}}\right)=-1$ אם a אינו שארית ריבועית, ו- $\ \left({\frac {a}{p}}\right)=0$ אם a מתחלק ב- p. סימן יעקובי מוגדר באופן כללי יותר, גם כאשר p אינו ראשוני, אבל הקשר שלו לשאריות ריבועיות פחות מיידי. מצד שני את סימן יעקובי קל יחסית לחשב, בעזרת משפט ההדדיות הריבועית.

תכונות בסיסיות

• אם p ראשוני איזוגי ו- a זר ל- p, אז:

$\ a^{\frac {p-1}{2}}\equiv \left({\frac {a}{p}}\right){\pmod {p}}$.

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

בפרט, מהנוסחה הזו נובעת תוצאה חשובה לגבי הריבועיות של 1-:

$\ \left({\frac {-1}{p}}\right)\equiv (-1)^{\frac {p-1}{2}}{\pmod {p}}$

כלומר, 1- הוא שארית ריבועית מודולו p אם $\ p\equiv 1{\pmod {4}}$, ואינו שארית ריבועית כאשר $\ p\equiv -1{\pmod {4}}$.

מתוצאה זו נובע (בעזרת שיטת הנסיגה האינסופית שפיתח אוילר) שניתן להציג כל מספר ראשוני מן הסוג הראשון, כסכום של שני ריבועים (למשל, $\ 73=8^{2}+3^{2}$). עובדה זו קובעת את הפירוק לראשוניים בחוג השלמים של גאוס, והיא מדגימה את הקשר בין שאריות ריבועיות, תבניות ריבועיות בינארית, ופירוק לראשוניים בחוג שלמים של שדה מספרים ריבועי.

• אם p ראשוני איזוגי ו- a,b שלמים כלשהם, אז $\ \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)$.

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

למעשה, זוהי תוצאה ישירה של הנוסחה הראשונה, כיוון שאם a,b אינם שניהם זרים ל-p התוצאה מיידית (שני האגפים שווים ל-0), ואחרת:

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

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