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.

Please suggest me how to compute the GCD of theese really big numbers :

  1. GCD of $2^{120547564397}-1$ and $2^{356946681940}-1$
  2. 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?

share|improve this question

3 Answers 3

up vote 8 down vote accepted

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.

share|improve this answer
    
And what exactly $2^{(a,b)}-1$ means here ? –  Quixotic Feb 2 '11 at 21:30
1  
$(a,b)$ is the GCD of $a$ and $b$. –  Yuval Filmus Feb 2 '11 at 21:32
    
@Yuval Filmus:Thanks that's helps for the first one. :-) –  Quixotic Feb 2 '11 at 21:35

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.

share|improve this answer

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

share|improve this answer

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.