Es gilt:
p=k=1∑qggT(k,q)=d∣q∑d⋅ϕ(dq)==ρ∣q∏(ρ+kρ(ρ−1))ρkρ−1=qρ∣q∏(1+kρ−ρkρ)
Legende:
ϕ() die eulersche Phi-Funktion,
d|q die Teiler von q,
ρ∣q die Primfaktoren von q,kρ die Exponenten der Primfaktoren von q.
Mit den beiden Produktformeln lässt sich die Bedingung sofort erkennen.
p∈P↔q∧2q−1∈P
p ist genau dann prim, wenn gilt: q ist prim und 2q-1 ist prim.