מבחן אוילר

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

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

הוכחה

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

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

כיוון שני: נניח כי $\sqrt{a^{p-1}}\equiv 1(\mathrm{mod}p)$ . כיוון ש-$U_p$ חבורה ציקלית, אזי קיים לה יוצר, יהי $g\in \mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}}$ היוצר שלה. מכיוון ש-$a\in \mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}}$ אז $a=g^{\alpha }$ עבור $\alpha$ כלשהו. $\sqrt{a^{p-1}}=\sqrt{(g^{\alpha }{)}^{p-1}}=\sqrt{g^{\alpha (p-1)}}\equiv 1(\mathrm{mod}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