I need some help understanding this algorithm. I want to factor $n$. Suppose $n$ has a factor $p$ s.t. the primes that divide $p-1$ are less than $10,000$. And $p-1$ divides $10000!$.
Let $m = 2^{10000!} \mod n$
By Fermat's Little Theorem, since $p-1$ divides $10000!$ we have:
$m \equiv 1 \mod p$ (Why is this true)?
The book then states: There is an excellent chance that $n$ does not divide $m-1$, so that $g = \gcd(m-1, n)$ will be a non-trivial divisor of $n$
How could $n$ ever divide $m-1$ since $m-1$ is smaller than $n$? And how is there a guaranteed $ g = \gcd(m-1, n)$?