Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$?

share|cite|improve this question
(Why is this true?) Fermat's little theorem says $m^{p-1}\equiv 1 \pmod p$. Do you mean why is Fermat's little theorem true? I don't understand what the author meant by $n$ not dividing $m-1$ either. But $g$ exists because, for instance, Euclid's algorithm gives it constructively. – Kevin Carlson Oct 16 '12 at 22:40
I know Fermat's little theorem. I am just not seeing the implications to get $m \equiv 1\mod p$ – CodeKingPlusPlus Oct 16 '12 at 22:52
Don't $m$ and $p$ have to be relatively prime for Fermat's Little Theorem? – CodeKingPlusPlus Oct 16 '12 at 22:53
Right-so $m=2^{10000!}-kp(n/p)$ and if $m, p$ weren't relatively prime, $p$ would divide $m$, and so would also have to divide $2^{10000!}$. So, come to think, $p=2$ has to be specifically excluded. But for any odd $p$, $m$ is relatively prime to $p$ as desired. – Kevin Carlson Oct 16 '12 at 23:01
What is $(n/p)$? – CodeKingPlusPlus Oct 16 '12 at 23:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.