מבחן אוילר
מבחן אוילר (על שם המתמטיקאי לאונרד אוילר) הוא מבחן לבדיקה אם מספר כלשהו $ 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 $ .
