מבחן אוילר

מבחן אוילר, הנקרא על שם המתמטיקאי לאונרד אוילר, הוא מבחן לבדיקה אם מספר כלשהו $\ a$ הוא שארית ריבועית של מספר ראשוני $\ p$.

נוסח מבחן אוילר: יהי $\ p$ מספר ראשוני אי זוגי ויהי $\ a$ מספר זר ל- $\ p$ , $\ a$ הוא שארית ריבועית של $\ p$ אם ורק אם $a^{(p-1)/2}\equiv 1{\pmod {p}}$.

הוכחה

כיוון ראשון: נניח כי $\ a$ הוא שארית ריבועית של $\ p$, זאת אומרת, עבור $\ x$ כלשהו $x^{2}\equiv a{\pmod {p}}$. לפי המשפט הקטן של פרמה $x^{p-1}\equiv 1{\pmod {p}}$.
. $\ x^{p-1}=x^{2(p-1)/2}=(x^{2})^{(p-1)/2}=a^{(p-1)/2}$. לכן, $a^{(p-1)/2}\equiv 1{\pmod {p}}$.

כיוון שני: נניח כי $a^{(p-1)/2}\equiv 1{\pmod {p}}$. כיוון ש $\ U_{p}$ היא חבורה ציקלית, אזי קיים לה יוצר, יהי $g\in \mathbb {Z} /p\mathbb {Z}$ היוצר שלה. מכיוון ש $a\in \mathbb {Z} /p\mathbb {Z}$ אז $\ a=g^{\alpha }$ עבור $\ \alpha$ כלשהו.$\ a^{(p-1)/2}=(g^{\alpha })^{(p-1)/2}=g^{\alpha (p-1)/2}=1{\pmod {p}}$. הסדר של $\ g$ הוא $\ p-1$, לכן $\ p-1$ מחלק את $\ \alpha (p-1)/2$ ומכאן ש-$\ \alpha /2$ מספר שלם, יהי $\ \beta =\alpha /2$. עבור $\ x=g^{\beta }$ מתקיים $\ x^{2}=(g^{\beta })^{2}=g^{2\beta }=g^{\alpha }=a$, ולכן $\ a$ הוא שארית ריבועית של $\ p$.

קישורים חיצוניים

• מבחן אוילר, באתר MathWorld (באנגלית)

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.