Recíprocamente, si "n" es primo, entones existe una raíz primitiva módulo "n" y cualquier raíz primitiva pasará ambos pasos del algoritmo.