שארית ריבועית – הבדלי גרסאות

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