Es sei
s
i
∈
S
+
{\displaystyle s_{i}\in S_{+}}
i
k
=
ϵ
i
s
i
mod
p
{\displaystyle ik=\epsilon _{i}s_{i}\mod p}
festgelegt. Wir betrachten alle Vielfachen
j
k
{\displaystyle jk}
j
∈
S
=
(
Z
/
(
p
)
)
×
{\displaystyle j\in S=(\mathbb {Z} /(p))^{\times }}
S
{\displaystyle S}
k
{\displaystyle k}
k
{\displaystyle k}
(
−
i
)
k
=
−
i
k
=
−
ϵ
i
s
i
{\displaystyle (-i)k=-ik=-\epsilon _{i}s_{i}}
i
∈
S
+
=
{
1
,
…
,
t
}
{\displaystyle i\in S_{+}=\{1,\ldots ,t\}}
S
+
=
{
1
,
…
,
t
}
=
{
s
1
,
…
,
s
t
}
{\displaystyle S_{+}=\{1,\ldots ,t\}=\{s_{1},\ldots ,s_{t}\}}
t
!
=
∏
i
=
1
t
s
i
{\displaystyle t!=\prod _{i=1}^{t}s_{i}}
t
!
k
t
{\displaystyle t!k^{t}}
=
(
∏
i
=
1
t
i
)
(
∏
i
=
1
t
k
)
{\displaystyle (\prod _{i=1}^{t}i)(\prod _{i=1}^{t}k)}
=
∏
i
=
1
t
i
k
{\displaystyle \prod _{i=1}^{t}ik}
=
∏
i
=
1
t
ϵ
i
s
i
{\displaystyle \prod _{i=1}^{t}\epsilon _{i}s_{i}}
=
(
∏
i
=
1
t
ϵ
i
)
(
∏
i
=
1
t
s
i
)
{\displaystyle (\prod _{i=1}^{t}\epsilon _{i})(\prod _{i=1}^{t}s_{i})}
=
(
∏
i
=
1
t
ϵ
i
)
t
!
mod
p
{\displaystyle (\prod _{i=1}^{t}\epsilon _{i})t!\mod p}
Durch kürzen mit
t
!
{\displaystyle t!}
k
t
=
∏
i
=
1
t
ϵ
i
mod
p
{\displaystyle k^{t}=\prod _{i=1}^{t}\epsilon _{i}\mod p}
Eulersche Kriterium , nämlich
k
t
=
k
p
−
1
2
=
(
k
p
)
mod
p
{\displaystyle k^{t}=k^{\frac {p-1}{2}}=\left({\frac {k}{p}}\right)\mod p}
