Efficient method to compute $\mathrm{gcd}(2^n-1,n!)$ 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.
 A: 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$.
A: 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.
