מתוך ויקיפדיה, האנציקלופדיה החופשית
מבחן אוילר , הנקרא על שם המתמטיקאי לאונרד אוילר , הוא מבחן לבדיקה אם מספר כלשהו
a
{\displaystyle \ a}
שארית ריבועית של מספר ראשוני
p
{\displaystyle \ p}
נוסח מבחן אוילר:
יהי
p
{\displaystyle \ p}
a
{\displaystyle \ a}
זר ל-
p
{\displaystyle \ p}
a
{\displaystyle \ a}
p
{\displaystyle \ p}
אם ורק אם
a
(
p
−
1
)
/
2
≡
1
(
mod
p
)
{\displaystyle a^{(p-1)/2}\equiv 1{\pmod {p}}}
כיוון ראשון : נניח כי
a
{\displaystyle \ a}
p
{\displaystyle \ p}
x
{\displaystyle \ x}
x
2
≡
a
(
mod
p
)
{\displaystyle x^{2}\equiv a{\pmod {p}}}
המשפט הקטן של פרמה
x
p
−
1
≡
1
(
mod
p
)
{\displaystyle x^{p-1}\equiv 1{\pmod {p}}}
x
p
−
1
=
x
2
(
p
−
1
)
/
2
=
(
x
2
)
(
p
−
1
)
/
2
=
a
(
p
−
1
)
/
2
{\displaystyle \ x^{p-1}=x^{2(p-1)/2}=(x^{2})^{(p-1)/2}=a^{(p-1)/2}}
a
(
p
−
1
)
/
2
≡
1
(
mod
p
)
{\displaystyle a^{(p-1)/2}\equiv 1{\pmod {p}}}
כיוון שני : נניח כי
a
(
p
−
1
)
/
2
≡
1
(
mod
p
)
{\displaystyle a^{(p-1)/2}\equiv 1{\pmod {p}}}
U
p
{\displaystyle \ U_{p}}
חבורה ציקלית , אזי קיים לה יוצר, יהי
g
∈
Z
/
p
Z
{\displaystyle g\in \mathbb {Z} /p\mathbb {Z} }
a
∈
Z
/
p
Z
{\displaystyle a\in \mathbb {Z} /p\mathbb {Z} }
a
=
g
α
{\displaystyle \ a=g^{\alpha }}
α
{\displaystyle \ \alpha }
a
(
p
−
1
)
/
2
=
(
g
α
)
(
p
−
1
)
/
2
=
g
α
(
p
−
1
)
/
2
=
1
(
mod
p
)
{\displaystyle \ a^{(p-1)/2}=(g^{\alpha })^{(p-1)/2}=g^{\alpha (p-1)/2}=1{\pmod {p}}}
סדר של
g
{\displaystyle \ g}
p
−
1
{\displaystyle \ p-1}
p
−
1
{\displaystyle \ p-1}
α
(
p
−
1
)
/
2
{\displaystyle \ \alpha (p-1)/2}
α
/
2
{\displaystyle \ \alpha /2}
β
=
α
/
2
{\displaystyle \ \beta =\alpha /2}
x
=
g
β
{\displaystyle \ x=g^{\beta }}
x
2
=
(
g
β
)
2
=
g
2
β
=
g
α
=
a
{\displaystyle \ x^{2}=(g^{\beta })^{2}=g^{2\beta }=g^{\alpha }=a}
a
{\displaystyle \ a}
p
{\displaystyle \ p}
