¿Cómo calcular estos GCD ' s?

Question

Por favor, me sugieren cómo calcular el MCD de esos números realmente grandes:

1. GCD de $2^{120547564397}-1$ y $2^{356946681940}-1$
2. GCD de $2^n-1$ y $n!$ donde $n=3^{19}$

Gracias a Bill Dubuquede respuesta comprendí que el primer problema podría ser solucionado por la propiedad que $gcd(f(m), f(n)) = f(gcd(m,n))$ si $ f(n) \equiv f(n-m) (mod\ f(m)),\ \ \ f(0)\ =\ 0$.

¿Cualquier sugerencias para la segunda?

Answer 1

% Toque $\rm\ (2^a-1,\:2^b-1)\ =\ 2^{(a,b)}-1\ $donde $\rm\ (a,b) := gcd(a,b)\:.\ $ para las pruebas ver aquí, o aquí - que tiene un polinomio análogo.

Answer 2

Creo que el segundo es sólo va a ser posible encontrar computacionalmente (aunque siéntase libre de demostrar que estoy equivocado). La división de los números primos los números de Mersenne son difíciles de adivinar, por lo que no se puede excluir a algunos de los mejores $p<n$ partir de la división de $2^n-1$ sin pruebas (aunque, por supuesto, podemos excluir a todos los $p>n$).

Así, para cada uno de los prime $p<n$ podemos encontrar el mayor $x$ tal que $p^x$ divide tanto a a$n!$$2^n-1$, luego se combinan los resultados utilizando el Teorema del Resto Chino. Algunos consejos:

• El mayor $a$ tal que $p^a$ divide $n!$$a=\sum_{k \geq 1} \lfloor n/p^k \rfloor$.
• Entonces podemos usar el Teorema de Euler para reducir la cantidad de cálculos necesarios para encontrar $2^n-1 \pmod {p^a}$ (o si usas algún sistema de álgebra computacional que va a hacer esto para usted).

Hay aproximadamente 60 millones de números primos a proceso, por lo que tomará un tiempo, pero no hacia fuera-de-la-pregunta.

Answer 3

Divertido, tu segunda pregunta surgió aquí un par de días atrás. Yo se la contesto aquí. Tal vez $n=3^{19}$ es demasiado grande para hacer este método práctico, pero Douglas explica cómo hacerlo sin usar $N$.