= Solution
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!$ give
$$
2^2\equiv4,\qquad 2^6\equiv64,\qquad
2^{24}\equiv64^4\equiv35\pmod{1003}.
$$
The first two <greatest common divisors> are $\gcd(3,1003)=\gcd(63,1003)=1$. At the next step the <Euclidean algorithm> gives
$$
\gcd(2^{24}-1,1003)=\gcd(34,1003)=17,
\qquad 1003=29\cdot34+17.
$$
Hence
$$
\boxed{17\text{ is a factor of }1003,\qquad1003=17\cdot59.}
$$
Here 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.
Back to article page
