מבחן אוילר

מבחן אוילר (על שם המתמטיקאי הגרמני לאונהרד אוילר) הוא מבחן לבדיקה אם מספר $a\in \mathbb {Z}$ הוא שארית ריבועית מודולו מספר ראשוני $p$ .

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

הוכחה

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

כיוון שני: נניח כי $a^{(p-1)/2}\equiv 1\!\!\!{\pmod {p}}$ . לכל $p$ ראשוני קיים שורש פרימיטיבי, כלומר איבר מסדר $\phi (p)=p-1$ אשר חזקותיו שקולות מודולו $p$ לאיברים $1,2,\ldots ,p-1$ בסדר כלשהו.
לכן קיים שורש פרימיטיבי $r$ המקיים $r^{k}\equiv a\!\!\!{\pmod {p}}$ עבור $1\leq k\leq \phi (p)$ כלשהו. מתקיים $(r^{k})^{(p-1)/2}=r^{k(p-1)/2}\equiv a^{(p-1)/2}\equiv 1\!\!\!{\pmod {p}}$ .
הסדר $\phi (p)$ מחלק את $k{\frac {p-1}{2}}$ ולכן $b={\frac {k}{2}}$ מספר שלם. מתקיים $(r^{b})^{2}=r^{2b}=r^{k}\equiv a\!\!\!{\pmod {p}}$ ולכן $a$ שארית ריבועית מודולו $p$ .