How to compute these GCD's? Please suggest me how to compute the GCD of theese really big numbers :


*

*GCD of $2^{120547564397}-1$ and $2^{356946681940}-1$ 

*GCD of $2^n-1$ and $n!$ where $n=3^{19}$


Thanks to Bill Dubuque's answer I understood that the first problem could be solved by the property that $gcd(f(m), f(n)) = f(gcd(m,n))$ if $ f(n) \equiv f(n-m) (mod\ f(m)),\ \ \ f(0)\ =\ 0$.
Any hints for the second one?
 A: HINT $\rm\ (2^a-1,\:2^b-1)\ =\ 2^{(a,b)}-1\ $ where $\rm\ (a,b) := gcd(a,b)\:.\ $ For proofs see here, or here - which has a polynomial analog.
A: I feel that the second one is only going to be possible to find computationally (although feel free to prove me wrong).  The primes dividing Mersenne numbers are difficult to guess -- so we can't exclude some prime $p<n$ from dividing $2^n-1$ without testing (although, of course we can exclude every $p>n$).
So, for each prime $p<n$ we can find the largest $x$ such that $p^x$ divides both $n!$ and $2^n-1$, then combine the results using the Chinese Remainder Theorem.  Some tips:


*

*The largest $a$ such that $p^a$ divides $n!$ is $a=\sum_{k \geq 1} \lfloor n/p^k \rfloor$.

*Then we can use Euler's Theorem to reduce the amount of computation required to find $2^n-1 \pmod {p^a}$ (or if you use some computer algebra system it'll do this for you).


There's approximately 60 million primes to process, so it will take a while, but it's not out-of-the-question.
A: Funny, your second question came up here a couple of days ago. I answered it here. Perhaps $n=3^{19}$ is too large to make this method practical, but Douglas explains how to do without using $N$.
