שארית ריבועית – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
←תכונות בסיסיות: תוספת נוספת |
Felagund-bot (שיחה | תרומות) בוט - מחליף 'דוגמא' ב'דוגמה' |
||
שורה 1:
ב[[תורת המספרים]], מספר a נקרא '''שארית ריבועית''' [[חשבון מודולרי|מודולו]] מספר n אם קיים פתרון [[מספר שלם|שלם]] למשוואה <math>\ x^2 \equiv a \pmod{n}</math>. זהו מושג קלאסי, שנחקר על-ידי מתמטיקאים מן המאה ה-17 ואילך.
אם <math>\ n=p>2</math> [[מספר ראשוני|ראשוני]], אז למעט השארית 0, יש בדיוק <math>\ \frac{p-1}{2}</math> שאריות ריבועיות, ו- <math>\ \frac{p-1}{2}</math> שאריות שאינן ריבועיות.
כדי להכריע האם a הוא שארית ריבועית מודולו מספר נתון n, יש [[פירוק לגורמים|לפרק]] את n לגורמים ראשוניים, <math>\ n=p_1^{\alpha_1}\dots p_t^{\alpha_t}</math>. מ[[משפט השאריות הסיני]] נובע שמספר הוא שארית ריבועית מודולו n אם ורק אם הוא שארית ריבועית מודולו כל אחד מן הגורמים הזרים שלו (החזקות <math>\ p_i^{\alpha_i}</math>).
כאשר p ראשוני אי-זוגי ו- a [[מספרים זרים|זר]] ל-p, אז a הוא שארית ריבועית מודולו חזקות של p אם ורק אם הוא שארית ריבועית מודולו p עצמו. עבור חזקות של [[2 (מספר)|2]], מספר איזוגי הוא שארית ריבועית מודולו חזקות גבוהות של 2 אם ורק אם הוא שארית ריבועית מודולו 8.
את הבעיה של זיהוי שאריות ריבועיות מודולו p ראשוני, מקודדים ב[[סימן לז'נדר]]. הסימן מוגדר לפי <math>\ \left(\frac{a}{p}\right)=+1</math> אם a זר ל- p והוא שארית ריבועית, <math>\ \left(\frac{a}{p}\right)=-1</math> אם a אינו שארית ריבועית, ו- <math>\ \left(\frac{a}{p}\right)=0</math> אם a מתחלק ב- p. [[סימן יעקובי]] מוגדר באופן כללי יותר, גם כאשר p אינו ראשוני, אבל הקשר שלו לשאריות ריבועיות פחות מיידי. מצד שני את סימן יעקובי קל יחסית לחשב, בעזרת [[משפט ההדדיות הריבועית]].
| |||