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

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

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

למה

יהי $p$ מספר ראשוני אי-זוגי, ויהי $a$ מספר זר ל-$p$.

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

הוכחה

$a$ זר ל-$p$, ולכן כל $\frac{p-1}{2}$ המספרים בקבוצה $S$ שונים זה מזה מודולו $p$.תבנית:ש תהיינה $r_1,\dots ,r_m$ שאריות החילוק הקטנות מ-$\frac{p}{2}$, ותהיינה $s_1,\dots ,s_n$ שאריות החילוק הגדולות מ-$\frac{p}{2}$.תבנית:ש המספרים $r_1,\dots ,r_m,p-s_1,\dots ,p-s_n$ כולם חיוביים וקטנים מ-$\frac{p}{2}$. יתרה מזו, אלה מספרים שונים מודולו $p$:תבנית:ש נניח בשלילה כי $r_i=p-s_j$. אזי קיימים $1\le k_1\ne k_2\le \frac{p-1}{2}$ עבורם

$\begin{array}{cc}& k_{1}a\equiv r_i(\mathrm{mod}p)\\ & k_{2}a\equiv s_j(\mathrm{mod}p)\\ & k_{1}a+k_{2}a\equiv r_i+s_j=p\equiv 0(\mathrm{mod}p)\\ & (k_1+k_2)a\equiv 0(\mathrm{mod}p)\\ & k_1+k_2\equiv 0(\mathrm{mod}p)\end{array}$

אך $1<k_1+k_2<p-1$. סתירה.

המספרים $r_1,\dots ,r_m,s_1,\dots ,s_n$ שקולים כמובן לאיברים $a,2a,\dots ,\frac{p-1}{2}a$ בסדר כלשהו.תבנית:ש המספרים $r_1,\dots ,r_m,p-s_1,\dots ,p-s_n$ שווים לאיברים $1,2,\dots ,\frac{p-1}{2}$ בסדר כלשהו. מתקייםתבנית:ש

$\begin{array}{c}{r}_1\cdots r_m\cdot (p-s_1)\cdots (p-s_n)=\left(\frac{p-1}{2}\right)!\equiv r_1\cdots r_m\cdot (-s_1)\cdots (-s_n)(\mathrm{mod}p)\\ \left(\frac{p-1}{2}\right)!\equiv (-1{)}^n{a}^{(p-1)/2}\left(\frac{p-1}{2}\right)!(\mathrm{mod}p)\\ a^{(p-1)/2}\equiv (-1{)}^n(\mathrm{mod}p)\end{array}$

אך לפי מבחן אוילר $\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}(\mathrm{mod}p)$.

ראו גם

• משפט ההדדיות הריבועית