Es sei
n
=
p
1
r
1
⋯
p
k
r
k
{\displaystyle {}n=p_{1}^{r_{1}}\cdots p_{k}^{r_{k}}}
chinesischen Restsatz
ist
(
Z
/
(
n
)
)
×
≅
(
Z
/
(
p
1
r
1
)
)
×
×
⋯
×
(
Z
/
(
p
k
r
k
)
)
×
.
{\displaystyle {}{\left(\mathbb {Z} /(n)\right)}^{\times }\cong {\left(\mathbb {Z} /(p_{1}^{r_{1}})\right)}^{\times }\times \cdots \times {\left(\mathbb {Z} /(p_{k}^{r_{k}})\right)}^{\times }\,.}
Es sei
a
=
(
a
1
,
…
,
a
k
)
{\displaystyle {}a=(a_{1},\ldots ,a_{k})}
n
{\displaystyle {}n}
n
{\displaystyle {}n}
(
a
i
)
n
−
1
=
1
mod
p
i
r
i
{\displaystyle {}(a_{i})^{n-1}=1\mod p_{i}^{r_{i}}\,}
für jeden Index
i
{\displaystyle {}i}
a
i
{\displaystyle {}a_{i}}
Z
/
(
p
i
r
i
)
{\displaystyle {}\mathbb {Z} /(p_{i}^{r_{i}})}
Fakt
möglich ist; für
p
i
=
2
{\displaystyle {}p_{i}=2}
(
p
i
−
1
)
p
i
r
i
−
1
{\displaystyle {}(p_{i}-1)p_{i}^{r_{i}-1}}
n
−
1
{\displaystyle {}n-1}
p
i
{\displaystyle {}p_{i}}
n
−
1
{\displaystyle {}n-1}
n
−
1
{\displaystyle {}n-1}
p
−
1
{\displaystyle {}p-1}
r
i
≥
2
{\displaystyle {}r_{i}\geq 2}
p
i
{\displaystyle {}p_{i}}
(
Z
/
(
p
i
r
i
)
)
×
{\displaystyle {}{\left(\mathbb {Z} /(p_{i}^{r_{i}})\right)}^{\times }}
p
=
2
{\displaystyle {}p=2}
p
|
(
n
−
1
)
{\displaystyle {}p{|}(n-1)}
Für die Umkehrung ist nach Voraussetzung
r
i
=
1
{\displaystyle {}r_{i}=1}
a
=
(
a
1
,
…
,
a
k
)
{\displaystyle {}a=(a_{1},\ldots ,a_{k})}
a
n
−
1
=
(
a
1
n
−
1
,
…
,
a
k
n
−
1
)
=
(
(
a
1
p
1
−
1
)
n
−
1
p
1
−
1
,
…
,
(
a
k
p
k
−
1
)
n
−
1
p
k
−
1
)
=
(
1
,
…
,
1
)
=
1
.
{\displaystyle {}a^{n-1}=\left(a_{1}^{n-1},\,\ldots ,\,a_{k}^{n-1}\right)=\left({\left(a_{1}^{p_{1}-1}\right)}^{\frac {n-1}{p_{1}-1}},\,\ldots ,\,{\left(a_{k}^{p_{k}-1}\right)}^{\frac {n-1}{p_{k}-1}}\right)=\left(1,\,\ldots ,\,1\right)=1\,.}
Also ist
n
{\displaystyle {}n}
