In the second step, it is shown that any common divisor of a and b, including g, must divide rN−1; therefore, g must be less than or equal to rN−1.
În al doilea pas, se arată că orice divizor comun al lui a și b, inclusiv g, trebuie să-l dividă pe rN−1; deci, g trebuie să fie mai mic sau egal cu rN−1.