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.

$\endgroup$
2
  • 1
    $\begingroup$ How large is very large? n=1000? n=1000000? $\endgroup$
    – TonyK
    Commented Jan 31, 2011 at 18:54
  • $\begingroup$ TonyK : ~10^5 . . $\endgroup$ Commented Feb 1, 2011 at 3:10

2 Answers 2

3
$\begingroup$

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

$\endgroup$
3
  • $\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
    Commented Feb 1, 2011 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$ Commented Mar 28, 2011 at 10:45
  • $\begingroup$ Perhaps you meant to say this only holds when $\gcd(2, m) = 1$? $\endgroup$ Commented Mar 28, 2011 at 11:02
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I'm out of votes for today; otherwise I'd vote for this one. $\endgroup$ Commented Mar 28, 2011 at 9:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .