מבחן אוילר

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

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

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

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