Mostrando $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, o $9$

Question

Dado que n es un entero positivo que mostrar $\gcd(n^3 + 1, n^2 + 2) = 1$, $3$, o $9$.

Estoy pensando que yo debería ser el uso de la propiedad de gcd que dice que si a y b son enteros, entonces mcd(a,b) = mcd(a+cb,b). Lo que me permite hacer cosas como decidir que $\gcd(n^3 + 1, n^2 + 2) = \gcd((n^3+1) - n(n^2+2),n^2+2) = \gcd(1-2n,n^2+2)$ y, a continuación, utilizando el teorema de Bezout puedo conseguir $\gcd(1-2n,n^2+2)= r(1-2n) + s(n^2 +2)$ y puedo expandir esto a $r(1-2n) + s(n^2 +2) = r - 2rn + sn^2 + 2s$ sin Embargo después de algún tiempo de la persecución a la ruta con varias sustituciones y factorings me he metido en ninguna parte.

¿Alguien puede proporcionar una sugerencia en cuanto a cómo debería estar buscando en este problema?

Answer 1

Como nota, $\gcd(n^3+1,n^2+2) = \gcd(1-2n,n^2+2)$.

Ahora, continuando de esa manera, $$\begin{align*} \gcd(1-2n, n^2+2) &= \gcd(2n-1,n^2+2)\\ &= \gcd(2n-1, n^2+2+2n-1)\\ &= \gcd(2n-1,n^2+2n+1)\\ &= \gcd(2n-1,(n+1)^2). \end{align*}$$

Considere ahora $\gcd(2n-1,n+1)$. Tenemos: $$\begin{align*} \gcd(2n-1,n+1) &= \gcd(n-2,n+1) \\ &= \gcd(n-2,n+1-(n-2))\\ &=\gcd(n-2,3)\\ &= 1\text{ or }3. \end{align*}$$ Por lo tanto, el mcd de a $2n-1$ $(n+1)^2$ es $1$, $3$, o $9$. De ahí que el mismo es cierto de la original de la dpc.

Answer 2

Jugando a lo largo de las líneas que estaban explorando debería funcionar. Vamos a hacerlo un poco casualmente, con el objetivo de siempre para reducir la potencia máxima de $n$.

Si $m$ divide tanto a a$n^3+1$$n^2+2$, $m$ divide $n(n^2+2)-(n^3+1)$, por lo que se divide $2n-1$. (Lo tienes).

Pero si $m$ divide $n^2+2$$2n-1$, $m$ divide $2(n^2+2)-n(2n-1)$, por lo que se divide $n+4$. (Este movimiento es un poco arriesgado. En algunos casos este tipo de medida podría introducir espurias comunes divisores. Pero (i) En este caso no; y (ii) vamos a comprobar al final de todos modos si nuestra lista de candidatos es correcta.)

Pero si $m$ divide $n+4$$2n-1$, $m$ divide $2(n+4)-(2n-1)$, por lo que se divide $9$.

No nos funcionan de forma explícita con el mayor de los divisores comunes, por lo que estamos no ha terminado. Debemos mostrar que $1$, $3$ y $9$ son todos alcanzable. Para $\gcd$ $1$, deje $n=0$. Para $\gcd$ $3$, deje $n=2$. Para $\gcd$ $9$, deje $n=4$.

Answer 3

Estoy realizando una congruencia procedimiento, por lo que tienen diferentes enfoques.

Si $p \, | \, n^3 + 1$$p \, | \, n^2 + 2$,$2n \equiv 1 \pmod p$, lo que significa que $$ -8 \equiv 8n^3 = (2n)^3 \equiv 1^3 \equiv 1 \pmod p, $$ por lo tanto $9 \equiv 0 \pmod p$ y asumiendo $p$ es un excelente medio $p = 3$. Esto significa que el $\gcd$ es una potencia de $3$. Ahora estoy revisando los poderes de $3$ a mano, usando congruencias.

EDIT : Como milagro del comentario dice, tengo demasiado llevar por la simpatía de los números primos tanto : una buena manera de decir que esta prueba se hace es que $9 \equiv 0 \mod p$$p \, | \, 9$, por lo tanto conseguir ejemplos es suficiente para recibir nuestra respuesta.

---

Si $n \equiv 0 \pmod 3$, $\gcd$ es claramente $1$.

Si $n \equiv 1 \pmod 3$, $n^3 + 1 \equiv 1 \pmod 3$ de modo que el $\gcd$ es de nuevo $1$.

Si $n \equiv 2 \pmod 3$,$9 \, | \, n^3 + 1$$3 \, | \, n^2 + 2$. Pero dejando $n = 3k+2$ nos damos cuenta de que \begin{align*} (3k+2)^3 + 1 & = (3k)^3 + 3 \cdot (3k)^2 \cdot 2 + 3 \cdot 3k \cdot 2^2 + 2^3 +1 \\& \equiv 9(k+1)\pmod{27} \end{align*} que es $0$ si y sólo si $k \equiv 2 \pmod 3$. Llevar! Tenemos $$ (3k+2)^2 + 2 \equiv (3k)^2 + 2 \cdot (3k) \cdot 2 + 2^2 + 2 = 9k^2 + 12k + 6 \equiv 0 \pmod{27} $$ si y sólo si $$ 3k^2 + 4k + 2 \equiv 0 \pmod 9 $$ pero la lectura de esta $\bmod 3$, obtenemos $k \equiv 1 \pmod 3$, una contradicción.

Debo decir que es un poco más largo que el $\gcd$ prueba : yo esperaba que la gente se ponga a $\gcd$ prueba, por lo que he mostrado esta vez. Me gustan esas pruebas porque son mecánicos, no tuve que pensar mucho para escribir, simplemente me eligió a ir por este camino y las cosas siempre salen como uno espera (suponiendo que la pregunta pide algo que es verdad, obviamente)... Ahora sólo he probado que el $\gcd$ divide $9$ : de nuevo, para mostrar que el $3$ posibilidades de suceder, sálgase de ejemplos como los de André Nicolas.

---

Espero que ayude,

Answer 4

Deje $\:\rm d = (n^3+1,\:n^2+2).\:$ Observa que el $\rm \ d \in \{1,\:3,\:9\} \iff\ d\:|\:9\iff 9\equiv 0\pmod d\:.$

mod $\rm (n^3\!-a,n^2\!-b)\!:\ a^2 \equiv n^6 \equiv b^3\:$ $\rm\:a=-1,\:b = -2\:\Rightarrow 1\equiv -8\:\Rightarrow\: 9\equiv 0\:. \ \ $ QED

O, si usted no sabe la congruencia aritmética, ya que $\rm\: x-y\:$ divide $\rm\: x^2-y^2$ $\rm\: x^3-y^3$

$\rm n^3-a\ |\ n^6-a^2,\:\ n^2-b\ |\ n^6-b^3\ \Rightarrow\ (n^3-a,n^2-b)\ |\ n^6-b^3-(n^6-a^2) = a^2-b^3 $

Nota cuánto más simple la prueba está usando congruencias vs divisibilidad de las relaciones en binomios. Similar congruential pruebas surgir cuando se calcula el modulo ideales generados por binomios.