מבחן אוילר

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

יהי $p$ מספר ראשוני אי-זוגי ויהי $a$ מספר זר ל-$p$ . $a$ הוא שארית ריבועית של $p$ אם ורק אם ${\sqrt {a^{p-1}}}\equiv 1{\pmod {p}}$ .

הוכחה

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

$x^{p-1}={\sqrt {x^{2(p-1)}}}={\sqrt {(x^{2})^{p-1}}}={\sqrt {a^{p-1}}}$ . לכן ${\sqrt {a^{p-1}}}\equiv 1{\pmod {p}}$ .

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0