מבחן אוילר

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

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

הוכחה

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

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

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

• תבנית:MathWorld