How can we compute the value of $\mathrm{gcd}(2^n-1,n!)$ efficiently where $n$ is very large? I couldn't think of any fast and efficient method.

  • 1
    $\begingroup$ How large is very large? n=1000? n=1000000? $\endgroup$ – TonyK Jan 31 '11 at 18:54
  • $\begingroup$ TonyK : ~10^5 . . $\endgroup$ – Prasoon Saurav Feb 1 '11 at 3:10

One crude way uses Fermat's little theorem. $2^{p-1} \equiv 1 \mod p$ so that $p$ divides $2^p - 1$ only when $p-1$ divides $n$. For general integers $m$, Fermat's little theorem says $2^{\phi(m)} - 1 \equiv 0 \mod m$ where $\phi(\cdot)$ is the Euler phi function. So maybe the problem boils down to finding $m$ such that $\phi(m)$ divides $n$.

  • $\begingroup$ Your second sentence is true only if $2$ is a primitive root mod $p$. (I'm assuming that $2^p$ is a typo for $2^n$.) For instance, $7$ divides $2^3-1$, but $6$ doesn't divide $3$. $\endgroup$ – TonyK Feb 1 '11 at 12:57
  • $\begingroup$ @TonyK: I'm not sure I understand your counterexample. 2 is not a primitive root modulo 7, as you have shown, yet $7 \mid 2^6 - 1$. The reason this doesn't hold modulo 6 is because $2 \not\in \mathbb{Z}_6^*$. $\endgroup$ – Zach Langley Mar 28 '11 at 10:45
  • $\begingroup$ Perhaps you meant to say this only holds when $\gcd(2, m) = 1$? $\endgroup$ – Zach Langley Mar 28 '11 at 11:02

Here's what I would do:

Initialise a large integer $N = 2^n - 1$. (This requires 1 or 2 kilobytes.)

For each prime $p \le n$, compute $2^n$ mod $p$ = $2^{n \mod (p-1)}$ mod $p$, using a square-and-multiply algorithm (see this Wikipedia article for details). If the result is $1$, then $N$ is divisible by $p$, and we want the highest power of $p$ that divides both $N$ and $n!$

The highest power of $p$ that divides $n!$ is just $a = \sum_{r=1}^K \lfloor \frac{n}{p^r}\rfloor$, where $K$ is any integer such that $p^K>n$ (see e.g. this article). So try to divide $N$ by $p$ up to $a$ times, stopping if the remainder is non-zero. The number of times that this succeeds is the power that we want.

Now just multiply together all these prime powers.

Note that $N$ gets smaller and smaller as the computation proceeds, limiting the amount of arithmetic required. It might be faster to process the primes in reverse order, to accelerate this trend; experimentation will tell.

  • $\begingroup$ I'm out of votes for today; otherwise I'd vote for this one. $\endgroup$ – Carl Brannen Mar 28 '11 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.