שארית ריבועית
ויקיפדיה האנציקלופדיה encyclopedia
בתורת המספרים, מספר a נקרא שארית ריבועית מודולו מספר אם קיים פתרון שלם למשוואה המודולרית
. זהו מושג קלאסי, שנחקר על ידי מתמטיקאים מן המאה ה-17 ואילך.
אם ראשוני, אז למעט השארית 0, יש בדיוק
שאריות ריבועיות ו-
שאריות שאינן ריבועיות. לדוגמה, השאריות הריבועיות מודולו 11 הן 1,3,4,5,9, בעוד כי 2,6,7,8,10 אינן שאריות ריבועיות. בזכות הפיזור האקראי-לכאורה של השאריות, יש למושג זה שימושים רבים בתחומים שונים של הקומבינטוריקה, וגם מחוץ למתמטיקה.
כדי להכריע האם הוא שארית ריבועית מודולו
, יש לפרק את
לגורמים ראשוניים,
. ממשפט השאריות הסיני נובע שמספר הוא שארית ריבועית מודולו
אם ורק אם הוא שארית ריבועית מודולו כל אחד מן הגורמים הזרים שלו (החזקות
).
כאשר ראשוני אי-זוגי ו-
זר ל-
, אזי
הוא שארית ריבועית מודולו חזקות של
אם ורק אם הוא שארית ריבועית מודולו
עצמו. עבור חזקות של 2, מספר אי זוגי הוא שארית ריבועית מודולו חזקות גבוהות של 2 אם ורק אם הוא שארית ריבועית מודולו 8. לדוגמה, 5 הוא שארית ריבועית מודולו 2 או 4, אבל לא מודולו 8. לגבי הבעיה החישובית של מציאת השורש כאשר
הוא שארית ריבועית, ראו הוצאת שורש ריבועי.
את הבעיה של זיהוי שאריות ריבועיות מודולו ראשוני, מקודדים בסימן לז'נדר. הסימן מוגדר לפי
אם
זר ל-
והוא שארית ריבועית,
אם
אינו שארית ריבועית, ו-
אם
מתחלק ב-
. סימן יעקובי מוגדר באופן כללי יותר, גם כאשר p אינו ראשוני, אבל הקשר שלו לשאריות ריבועיות פחות מיידי. מצד שני את סימן יעקובי קל יחסית לחשב, בעזרת משפט ההדדיות הריבועית.