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

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

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

בתורת המספרים, מספר 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 הוא שארית ריבועית, ראu הוצאת שורש ריבועי.

את הבעיה של זיהוי שאריות ריבועיות מודולו 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}$ שורשים; מכאן שכל השורשים הם שאריות ריבועיות. כדי לסיים את ההוכחה מספיק להבחין ש- $\ (a^{\frac{p-1}{2}})^2 = a^{p-1} \equiv 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}$