Es gilt:
$$\large p=\sum _{ k=1 }^{ q }{ ggT(k,q) } = \sum_{d|q}d \cdot \phi(\frac{q}{d}) =\\ =\large\prod_{\rho|q }(\rho+k_{\rho}(\rho -1))\rho ^{k_{\rho }-1}= q \prod_{\rho|q }(1+k_{\rho}-\frac{k_{\rho}}{\rho })$$
Legende:
\( \phi () \) die eulersche Phi-Funktion,
d|q die Teiler von q,
\( \rho|q \) die Primfaktoren von \( q, k_{\rho} \) die Exponenten der Primfaktoren von q.
Mit den beiden Produktformeln lässt sich die Bedingung sofort erkennen.
$$\large p \in \mathbb{P} \leftrightarrow q \wedge 2q-1 \in \mathbb{P}$$
p ist genau dann prim, wenn gilt: q ist prim und 2q-1 ist prim.
