Take the 2-minute tour ×
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.

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.

share|improve this question
1  
How large is very large? n=1000? n=1000000? –  TonyK Jan 31 '11 at 18:54
    
TonyK : ~10^5 . . –  Prasoon Saurav Feb 1 '11 at 3:10

2 Answers 2

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.

share|improve this answer
    
I'm out of votes for today; otherwise I'd vote for this one. –  Carl Brannen Mar 28 '11 at 9:04

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

share|improve this answer
    
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$. –  TonyK Feb 1 '11 at 12:57
    
@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^*$. –  Zach Langley Mar 28 '11 at 10:45
    
Perhaps you meant to say this only holds when $\gcd(2, m) = 1$? –  Zach Langley Mar 28 '11 at 11:02

Your Answer

 
discard

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

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