Demostrar que $\gcd(n!+1,(n+1)!+1)=1$

Question

Me gustaría resolver ésta de forma similar a mi pregunta anterior: ¿Es esta una prueba válida para $(2n+1,3n+1)=1$ ?

He encontrado un post algo relacionado que utiliza un método diferente: Cómo demostrar que $\gcd(n! + 1, (n + 1)! + 1) \mid n$ ?

Entonces, ¿cómo lo haría? Puedo escribir lo anterior como:

$\exists \ d \ \in \mathbb{Z}$

1. $n!+1 \equiv 0$ (mod $d$ )
2. $(n+1)!+1 \equiv 0$ (mod $d$ )

No estoy seguro de qué hacer a continuación. ¿Algún consejo?

Gracias.

Answer 1

Por el algoritmo euclidiano $$\left(n!+1,\ (n+1)!+1\right)=\left(n!+1,\ (n+1)!+1-(n!+1)\right)$$ $$=\left(n!+1,n\cdot n!\right).$$ Está claro que los dos últimos deben ser relativamente primos, ya que si $p|\ (n!\cdot n)$ entonces $p| n!$ (y hay un +1 extra por ahí).

Answer 2

Aquí hay una puramente ecuación prueba. En pocas palabras $\rm\ k = (n-1)!\ $ en

Teorema $\rm\ \ ((n+1)\ n\ k+1,\ n\ k+1)\ =\ 1$

Prueba $\ \ $ Trabajar en el módulo del gcd $\rm\: := d\:$ tenemos

$(1)\rm\quad\quad (n+1)\ n\ k\ \equiv\: -1\quad\quad$ por $\rm\ d\ |\ (n+1)\ n\ k+1$

$(2)\rm\quad\quad\phantom{(n+1)\ } n\ k\ \equiv\: -1\quad\quad$ por $\rm\ d\ |\ n\ k+1$

$(3)\rm\quad\quad\phantom{(n+1)\ n\ } n\ \equiv\,\ \ \ 0\quad\quad $ sustituyendo $\:(2)\:$ en $\:(1)\:$

$(4)\rm\quad\quad\phantom{(n+1)\ n\ } 0\ \equiv\: -1\quad\quad$ sustituyendo $\:(3)\:$ en $(2)$

Por lo tanto, concluimos que $\rm\: 0\ \equiv\ 1,\, $ es decir $\rm\ d\ |\ 1\quad$ QED

Desenrollando las relaciones lineales utilizadas en la prueba anterior (o, de forma equivalente, utilizando el algoritmo euclidiano extendido) se obtiene la relación de Bezout que di en la pregunta que enlazaste, a saber

$$ \rm 1\ =\ (n-1)!\ ((n+1)!+1)\ +\ (1-(n+1)!/n)\ (n!+1)$$

Obsérvese cómo lo que parece magia visto en términos de relaciones de divisibilidad se reduce a una relación puramente mecánico proceso de eliminación en forma de ecuación. En la teoría de los números superiores aprenderá con más precisión cómo los métodos del álgebra lineal, como la eliminación gaussiana, se extienden de los campos a ciertos anillos, por ejemplo, las formas normales de Hermite y Smith de Google.

Answer 3

Supongamos que $m$ es un número entero positivo que divide a ambos $n! + 1$ y $(n+1)! + 1$ . El objetivo es demostrar que $m = 1$ . Tenga en cuenta que $m$ también divide $(n+1)*(n! + 1) - ((n+1)! + 1)$ que es igual a $(n+1)! + (n+1) - (n+1)! - 1 = n$ . Desde $m$ divide $n$ También divide $n!$ . Ya que divide $n! + 1$ además, divide $n! + 1 - n!$ o simplemente $1$ . Por lo tanto, $m = 1$ según sea necesario.

Answer 4

Esto es una aplicación directa al algoritmo de la división que dice:

para dos enteros cualesquiera a,b, a>b se cumple lo siguiente: $$a = qb + r$$

Si demostramos que $0<r<b$ hemos terminado.

Sustituir $a$ por $(n+1)!+1$ , $q$ por $n$ , $b$ por $(n!+1)$ y $r$ por $n!-n+1$ que es mayor que $0$ y menos de $b$ según sea necesario.

Más aclaraciones :

El lado izquierdo es: $$(n+1)!+1$$ mientras que el lado derecho es: $$n(n!+1)+(n!-n+1) \Longrightarrow nn!+n+(n!-n+1) \Longrightarrow n!(n+1)+1 \Longrightarrow (n+1)!+1$$

Answer 5

Esto es sólo una alternativa al enfoque de la respuesta de Eric Naslund.

De la norma $(a,b)=(a,b-ka)$ para cualquier $k$ junto con $(a,b)=(b,a)$ y $(a,b)=(|a|,|b|)$ tenemos

$$\begin{align} (n!+1,(n+1)!+1) &=(n!+1,(n+1)!+1-(n+1)(n!+1))\\ &=(n!+1,-n)\\ &=(n,n!+1)\\ &=(n,n!+1-(n-1)!n)\\ &=(n,1)\\ &=1 \end{align}$$