9
$\begingroup$

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.

  • 0
    TonyK : ~10^5 . .2011-02-01

2 Answers 2

3

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$.

  • 0
    Perhaps you meant to say this only holds when $\gcd(2, m) = 1$?2011-03-28
3

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.

  • 0
    I'm out of votes for today; otherwise I'd vote for this one.2011-03-28