$\forall n\in\mathbb{Z}$ , encontrar el $\gcd(n^2+1, (n+1)^2+1)$ ?

Question

$\forall n\in\mathbb{Z}$ , encontrar el $\gcd(n^2+1, (n+1)^2+1)$ .

Creo que es un ejercicio sencillo, pero lo entiendo:

$(n+1)^2+1=n^2+2n+2$ .

$n^2+2n+2 = (n^2+1)+(2n+1)$

entonces $\gcd(n^2+1, (n+1)^2+1)=\gcd(n^2+1, 2n+1)$

y $\displaystyle n^2+1 = \frac{n(2n+1)}{2}+\left(-\frac{n}{2}+1\right)$

entonces $\gcd(n^2+1, 2n+1)=\gcd(2n+1, \frac{n}{2}-1)$ .

Pero gcd es sobre números enteros y $\dfrac{n}{2}-1$ no es siempre un número entero, así que, ¿necesito ayuda?

Answer 1

Dejemos que $d=\gcd(n^2+1, (n+1)^2+1)$

Así que $d$ divide su diferencia

$d|2n+1$ por lo que al multiplicar por $n$ se obtiene $d|2n^2+n$

Pero $d|2n^2+2$ así que $d|n-2$ así que $d|2n-4$ así que $d|5$

Al considerar todos los residuos modulo $5$ de $n^2+1$ y $(n+1)^2+1$ podemos ver que $\gcd$ es $5$ si $n\equiv2$ mod $5$ y $1$ de lo contrario.

Answer 2

Tenga en cuenta que $$(2n+3)(n^2+1) - (2n-1)((n+1)^2+1) = 5.$$

Para obtener esta ecuación, establezca $(n+a)(n^2+1)-(n+b)(n^2+2n+2) = c$ para algunas constantes $a,b,c$ y equiparar los coeficientes. Esto da $b = -\tfrac{1}{2}$ , $a = \tfrac{3}{2}$ y $c = \tfrac{5}{2}$ . A continuación, multiplica ambos lados por $2$ .

Por lo tanto, $\text{gcd}(n^2+1,(n+1)^2+1)$ divide $5$ (que es primordial).

Entonces, como $n^2+1 \equiv 0 \pmod{5}$ si $n \equiv 2,3 \pmod{5}$ y $(n+1)^2+1 \equiv 0 \pmod{5}$ si $n \equiv 1,2 \pmod{5}$ tenemos que $$\text{gcd}(n^2+1,(n+1)^2+1) = \begin{cases}5 & \text{if} \ n \equiv 2 \pmod{5} \\ 1 & \text{otherwise}\end{cases}.$$

Answer 3

Su paso que dice $\displaystyle n^2+1 = \frac{n(2n+1)}{2}+\left(-\frac{n}{2}+1\right)$ es correcto pero no útil. Estamos trabajando en los naturales y esta amenaza (si $n$ ni siquiera) para sacarnos de los naturales.

Si hacemos una hoja de cálculo y probamos los números pequeños encontramos que el GCD es $1$ a menos que $n\equiv 2 \pmod 5$ , en cuyo caso es $5$ . Podemos ver que si $n \equiv 2 \pmod 5$ , $n^2+1 \equiv (n+1)^2+1 \equiv 0 \pmod 5$ . Ahora tenemos que preguntar si hay otros números $k$ donde $n^2\equiv (n+1)^2 \equiv -1 \pmod k$ . Esto requiere que $2n+1 \equiv 0 \pmod k$ . Podemos factorizar $k$ exigir que $2n+1 \equiv 0 \pmod p$ para algún primo $p$ dividiendo $k$ . Si lo elevamos al cuadrado obtenemos $4n^2+4n+1\equiv 4n-3\equiv 0, n \equiv \frac 34 \pmod p$ donde se aprovecha el hecho de que $\Bbb Z_p$ es un campo para dividir. Ahora $n^2 \equiv -1 \pmod p$ dice $9 \equiv -16 \pmod p$ y el único primo es $5$ . Así que el $\gcd$ es $1$ a menos que $n \equiv 2 \pmod 5$ en cuyo caso es $5$ .