הלמה של גאוס (תורת המספרים)

הלמה של גאוס היא למה בתורת המספרים, המספקת תנאי למספר טבעי להיות שארית ריבועית. הלמה נקראת על שם קרל פרידריך גאוס שהוכיח אותה לראשונה בדרכו להוכחת משפט ההדדיות הריבועית.

על אף שהלמה אינה יעילה ככלי חישוב, יש לה חשיבות תאורטית, כטענת עזר בהוכחות רבות של משפט ההדדיות הריבועית.

הלמה של גאוס. יהי p מספר ראשוני אי זוגי, ונניח ש- a זר ל- p. אם n הוא מספר המספרים בקבוצה $\ S=\{a,2a,3a,\dots ,{\frac {p-1}{2}}a\}$ המשאירים שארית גדולה מ- p/2 כשמחלקים אותם ב-p, אז: $\ \left({\frac {a}{p}}\right)=(-1)^{n}$ , כאשר $({\tfrac {\cdot }{\cdot }})$ הוא סימן לז'נדר.

הוכחה. מכיוון ש- a זר ל- p, כל $\ (p-1)/2$ המספרים בקבוצה S שונים זה מזה מודולו p. נסמן ב- $\ r_{1},\dots ,r_{m}$ את שאריות החילוק הקטנות מ- p/2, וב- $\ s_{1},\dots ,s_{n}$ את שאריות החילוק הגדולות מ- p/2. המספרים $\ r_{1},\dots ,r_{m},p-s_{1},\dots ,p-s_{n}$ כולם חיוביים וקטנים מ- p/2. יתרה מזו, אלו מספרים שונים, מפני שאם $\ p-s_{i}=r_{j}$ , כאשר $\ r_{j}\equiv ua{\pmod {p}}$ ו- $\ s_{i}\equiv va{\pmod {p}}$ , אז $\ u+v\equiv 0{\pmod {p}}$ , והרי המכפלות בקבוצה S הן תמיד בגורמים קטנים מ- p/2.

אם כך, המספרים ברשימה הנ"ל שווים למספרים $\ 1,2,\dots ,(p-1)/2$ בסדר מתאים, ומכפלתם שווה ל- $\ ((p-1)/2)!$ ; לכן $\ r_{1}\dots r_{m}(p-s_{1})\dots (p-s_{n})=(-1)^{n}r_{1}\dots r_{m}\cdot s_{1}\dots s_{n}\equiv ((p-1)/2)!{\pmod {p}}$ . מצד שני, המספרים $\ r_{1},\dots ,r_{m},s_{1},\dots ,s_{n}$ מהווים סידור מחדש של הקבוצה S, ומכאן ש- $\ ((p-1)/2)!\equiv (-1)^{n}\cdot a^{(p-1)/2}\cdot ((p-1)/2)!{\pmod {p}}$ . לכן $\ (-1)^{n}\equiv a^{(p-1)/2}{\pmod {p}}$ . אבל לפי מבחן אוילר, $\ \left({\frac {a}{p}}\right)=a^{(p-1)/2}$ .