Demostrar que $\gcd(3^n-2,2^n-3)=\gcd(5,2^n-3)$

Question

Demostrar que $\gcd(3^n-2,2^n-3)=1$ si y sólo si $\gcd(5,2^n-3)=1$ $n$ Dónde está un número natural.

No veo una manera fácil de comprobarlo usando el Algoritmo euclidiano, pero parece cierto que ambos gcd no $1$ sólo si $n = 3+4k$. ¿Hay una manera fácil de probar la declaración?

Answer 1

Tenemos $2^n=1,2,4,3\bmod5$$3^n=1,3,4,2\bmod5$$n=0,1,2,3\bmod4$. Por lo tanto $2^n-3,3^n-2$ son ambos divisibles por 5 iff $n=3\bmod4$ $\gcd(2^n-3,5)=5$ fib $n=3\bmod4$ (para otros $n$ es 1).

A la pregunta original, en este sitio le pidió una prueba de que $\gcd(2^n-3,5)=\gcd(2^n-3,3^n-2)$ todos los $n$. Dada la observación anterior, que ascendió a la afirmación de que (1) $\gcd(2^n-3,3^n-2)=5$ $n=3\bmod4$ y (2) $\gcd(2^n-3,3^n-2)=1$$n\ne3\bmod4$.

He encontrado que $$\gcd(2^{3783}-3,3^{3783}-2)=26665=5\cdot5333$$ which showed that (1) is false for $n=3783$.

Por Fermat Poco Teorema tenemos que $2^{5332}=3^{5332}=1\bmod5333$, por lo que se deduce que el $2^n-3=3^n-2=0\bmod5333$ todos los $n=3783\bmod5332$. Desde $3783=3\bmod4$$5332=0\bmod4$, los valores de $n$ que $5333$ es un factor de $\gcd(3^n-2,2^n-3)$ son un subconjunto de aquellos para los que $5$ es un factor.

Sin embargo, se supo que la pregunta vino de la OMI LongList de 1972, en la que simplemente le pidió que los valores de $n$ tenemos $\gcd(3^n-2,2^n-3)>1$. La pregunta en este sitio ha sido modificado para pedir (en efecto) para una prueba de (2).

Parece como si (2) es probablemente cierto, pero por el momento no veo cómo demostrarlo.

---------- Añadido El 17 De Junio De 2016 --------

@i707107 ha tenido la amabilidad de proporcionar referencias a algunos papeles por el ruso y el polaco matemáticos, en el período 1999-2003 (ver http://www.fq.math.ca/Papers1/43-2/paper43-2-6.pdf y referencias incluidas). Ellos incluyen $$\gcd(2^{712999}-3,3^{712999}-2)=5\cdot18414001$$ where 18414001 is a prime and $712999=3\bmod4$. El último párrafo del 2000 de papel por Kazimierz Szymiczek (que murió el año pasado) se lee:

"Otra conjetura queremos hacer va en la dirección opuesta. Los resultados numéricos sugieren que tres de las cuatro sucesivas parejas $2^n-3$ $3^n-2$ son relativamente primos. Aún no sabemos si los hay infinitamente muchos exponentes $n$ que $2^n-3$ $3^n-2$ son relativamente primos. La conjetura es que hay infinitamente muchos de estos exponentes."

Así que parece que sigue abierta la cuestión de si $\gcd(2^n-3,3^n-2)=1$$n\ne3\bmod4$. Que es probablemente la razón por la que la pregunta propuesta por Rumanía por la OMI nunca llegó más allá de la OMI, 1972 Larga Lista.

Answer 2

Esto no responder la pregunta por completo. Esto proporciona más información que la que proporciona las respuestas anteriores y comentarios. También, el método que aquí difiere ligeramente de la siguiente referencia, pero las ideas principales son el papel.

De acuerdo a la referencia http://www.fq.math.ca/Papers1/43-2/paper43-2-6.pdf

Obtenemos primos comunes divisores de $2^n-3$$3^n-2$, de la siguiente manera:

1. Encontrar un número primo $p$ satisfactorio $$ \gcd(\mathrm{ord}_p (3\cdot 2^{-1}), \mathrm{ord}_p (6)) = 1 \ \mathrm{o} \ 2. $$

2. Para tales prime $p$, vamos a $\ell = \mathrm{ord}_p(3\cdot 2^{-1})$$k=\mathrm{ord}_p(6)$. Encontrar entero soluciones para: $$ \ell x - k y = 2.$$

3. Queremos $x\geq 1$ desde el Paso 2. A partir de $1$, encontramos: $$ 2^{\ell x -1} \ \mathrm{mod} \ p \ \mathrm{y} \ 3^{\ell x -1} \ \mathrm{mod} \ p $$

4. Si se $3$ $2$ respectivamente, entonces el primer $p$ es el mínimo común divisor de a $2^n-3$ $3^n-2$ donde $n=\ell x -1$.

Un programa de SAGE que escribí, no es exactamente siga el algoritmo anterior, pero fue un éxito en la búsqueda de, al menos, los tres primos $5$, $5333$, $18414001$.

for p in primes(4,40000000): 
a=2.inverse_mod(p); 
b=Mod(Mod(3,p)*a,p).multiplicative_order(); 
c=Mod(6,p).multiplicative_order(); 
if gcd(b, c)==1: 
    g,s,t=xgcd(b, -c); 
    h=(2*s)%c; 
    print p, Mod(b*h-1,4), power_mod(3,b*h-1,p), power_mod(2,b*h-1,p);

con los siguientes resultados:

5 3 2 3
5333 1 5331 5330
18414001 3 2 3

La segunda línea de resultado puede ser debido a que el programa carece de proceder en el Paso 2 y el Paso 3. Con más cuidado, podría ser posible la aplicación de estas y obtener un resultado correcto 5333 3 2 3.

No era posible para mí completamente resolver el (equivalente) problema:

$\bullet$ Si $p|\gcd(2^n-3,3^n-2)$,$n\equiv 3 \ \mathrm{mod} \ 4$.

Pero, ahora tengo uno más que conjeturas:

$\bullet$ Si $\gcd(\mathrm{ord}_p (3\cdot 2^{-1}), \mathrm{ord}_p (6)) = 1$, entonces no existe $n$ tal que $p|\gcd(2^n-3,3^n-2)$.

Ambas de estas preguntas que aún permanecen abiertas.