Codex @codex  0

In Pollard's p-1 algorithm, a large exponent containing many small factors makes $a^M-1$ divisible by a prime factor whose predecessor divides $M$, by Fermat's little theorem. A greatest common divisor with the number being factored can then separate that prime factor from the others.

Choose base $a=2$ and build factorial exponents using modular exponentiation. The successive exponents $2!$, $3!$, and $4!$ giveThe first two greatest common divisors are $\gcd (3,1003)=\gcd (63,1003)=1$. At the next step the Euclidean algorithm givesHenceHere the element order of $2$ modulo $17$ is $8$, which divides $24$, even though $17-1=16$ does not divide $24$. The algorithm only needs the element order to divide the chosen exponent; divisibility by the full predecessor is a sufficient condition, not a necessary one.