¿Cómo se demuestra que dos números generales $n! + 1$ y $(n+1)! + 1$ son relativamente primos?

Question

¿Cómo se demuestra que dos números generales $n! + 1$ y $(n+1)! + 1$ son relativamente primos?

No me importa si alguien utiliza un ejemplo diferente, quiero aprender a demostrar esta clase de problemas.

Mi profesor parece hacer mucho hincapié en que se puede utilizar el algoritmo de la división, o encontrar el máximo común divisor utilizando el algoritmo de la división más bien, con el fin de evaluar la naturaleza de la prima relativa y estoy un poco confundido en cuanto a cómo aplicarlo.

Answer 1

Supongamos que $d$ divide a ambos. Entonces $d$ divide $(n+1)(n!+1)$ y $(n+1)!+1$ , por lo que divide su diferencia, que es $n$ .

Pero si $d$ divide $n!+1$ y $n$ entonces $d$ divide $n!+1$ y $n!$ Así que $d$ divide $1$ .

Answer 2

Usaré $\big(a,b\big)$ para denotar el gcd de $a$ y $b$ . La idea básica del algoritmo de división es que $(a,b) = (a - kb,b)$ para cualquier número entero $k$ .

\begin {align*} \Big ¡((n+1)! ¡+ 1 \; , \; n! + 1 \Big ) &= \Big ([(n+1)! + 1] - (n+1)[n! + 1] \N - , \N - n! + 1 \Big ) \\ &= \Big ((n+1)(n!) - (n+1)(n!) + 1 - (n+1) \N - , \N - n! + 1 \Big ) \\ &= \Big ¡(-n , \N; n! + 1 \Big ) \\ &= \Big ¡(n , \; n! + 1 \Big ) \\ &= \Big ¡(n , \; n! + 1 - (n-1)!(n) \Big ) \\ &= \Big (n , \; 1 \Big ) \\ &= 1 \\ \end {align*}

Answer 3

La identidad clave es $$\gcd (a,b) = \gcd (a-kb ,b).$$

Por lo tanto, la tarea consiste en elegir el $k$ de manera que la expresión se simplifique.

En este caso particular, es el más 1 el que está bloqueando la bonita estructura multiplicativa, por lo que se puede elegir $k=1$ para eliminarlo lo que da

$$\gcd ((n+1)!+1,n!+1) = \gcd (n\cdot n! ,n!+1).$$

Pero esto es claramente 1 porque cada factor de $n\cdot n!$ es relativamente primo de $n!+1$ .

(Tenga en cuenta que las otras respuestas eligen $k=n+1$ para eliminar el factorial en lugar del 1, por lo que normalmente tienes más de una buena opción para elegir $k$ .)

Answer 4

Sugerencia $\ $ Poner $\, k = n!\,$ en la siguiente reducción gcd euclidiana

$$(k\!+\!1,(n\!+\!1)k\!+\!1) = (\color{#c00}{k\!+\!1},(n\!+\!1)(\color{#c00}{k\!+\!1})\!-\!n) = (\color{}{k\!+\!1},-n)\,\ \ \left[\,= 1\ \ {\rm if}\ \ n\mid k\,\right]$$

Generalmente $\ (k\!+\!1,f(k)) = (k\!+\!1,f(-1))\,\ $ [ $=1\,$ si $\,f(-1)\mid k\,$ ] donde la primera igualdad emplea reducción modular gcd combinado con el teorema del resto del polinomio es decir $\bmod k\!+\!1\!:\ \,\color{#c00}{k\equiv -1}\Rightarrow f(\color{#c00}k)\equiv f(\color{#c00}{-1}),\,$ para cualquier polinomio $\,f(x)\,$ con entero coeficientes. Por encima tenemos $\,f(x) = (n\!+\!1)x+1\,$ así que $\,f(-1) = -n$

Answer 5

Una pista: $$(n+1)!+1\ =\ (n+1)\,n!\,+1 = (n+1)\,(n!+1)\ -\ (n+1)\ +1$$