שארית ריבועית – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
מ שוחזר מעריכה של 217.132.54.54 (שיחה) לעריכה האחרונה של 89.0.213.23 |
||
שורה 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> שאריות שאינן ריבועיות. לדוגמה, השאריות הריבועיות מודולו 11 הן 1,3,4,5,9, בעוד ש- 2,6,7,8,10 אינן שאריות ריבועיות. בזכות הפיזור האקראי-לכאורה של השאריות, יש למושג זה שימושים רבים בתחומים שונים של ה[[קומבינטוריקה]], וגם מחוץ ל[[מתמטיקה]].
כדי להכריע האם a הוא שארית ריבועית מודולו מספר נתון n, יש [[פירוק לגורמים|לפרק]] את n לגורמים ראשוניים, <math>\ n=p_1^{\alpha_1}\dots p_t^{\alpha_t}</math>. מ[[משפט השאריות הסיני]] נובע שמספר הוא שארית ריבועית מודולו n אם ורק אם הוא שארית ריבועית מודולו כל אחד מן הגורמים הזרים שלו (החזקות <math>\ p_i^{\alpha_i}</math>).
| |||