Pregunta elemental sobre una prueba falsa y los máximos comunes divisores

Question

Tengo una pregunta para un ejercicio - para el cual tengo una solución equivocada - y quería pedirles que me ayuden a entender mi error de pensamiento. El ejercicio era el siguiente:

Sea $a, b, n \in \mathbb{N}$ . Demuestre que $\gcd(a,b) = \gcd(a,b+na)$ .

Mi solución fue (en pocas palabras):

• Sea $d := \gcd(a,b)$ .
• Entonces demostré que $d$ es un divisor común de ambos $a$ y $b + na$
• Entonces demostré, que cualquier divisor común $c$ de $a$ y $b+na$ es menor o igual que $d$
• Después de eso, llegué a la conclusión de que por definición $d = \gcd(a,b+na)$ y con la definición de $d$ Habría $\gcd(a,b) = \gcd(a,b+na)$ así que mi prueba estaba completa.

Sin embargo, mi tutor no aceptó la prueba. Me enseñó la prueba "correcta", en la que tendría que haber $d := \gcd(a,b)$ y $e := \gcd(a,b+na)$ y luego demostrar $d \leq e \leq d$ .

De todos modos, entiendo su prueba. Pero sigo sin entender dónde está mi error de pensamiento. Después de todo, si mi punto de partida sería, digamos, $d := 9$ y hubiera podido mostrar los pasos después, entonces podría concluir $9 = \gcd(a,b+na)$ ¿No?

Cualquier comentario será bienvenido, ¡muchas gracias de antemano!

EDITAR ¡Vaya, habéis respondido rápido! Muchas gracias. Volveré a preguntar a mi tutor el jueves. En aras de la exhaustividad, voy a formular mi prueba completa (mi prueba original está en alemán, así que tal vez habrá algo perdido en la traducción, la [Referencia] son referencias a nuestro guión).

Sea $a,b,n \in \mathbb{N}$ . Sea $d := \gcd(a,b)$ . Por definición significa $d \mid a$ y $d \mid b$ por lo que con [Referencia] se cumple lo siguiente: $d \mid (b + na)$ . Por lo tanto, $d$ es un divisor común de ambos $a$ y $b + na$ . Demostraremos ahora, que $d$ es el máximo común divisor.

Sea $c$ sea cualquier divisor común de $a$ y $b + na$ . Por lo tanto, $c$ divide $a$ y como tal $c \mid na$ y por ello $c \mid ((b + na) - na) = b$ (de nuevo debido a [Referencia]). Así que $c$ divide $b$ por lo que $c$ es un divisor común de ambos $a$ y $b$ . Desde $d$ era el máximo común divisor de $a$ y $b$ tenemos $c \leq d$ .

Por definición del máximo común divisor obtenemos $d = \gcd(a,b+na)$ .

Fin de la prueba. Mi tutor escribió, que sólo mostré $\gcd(a,b+na) \leq \gcd(a,b)$ y también hay que mostrar la otra dirección. Hoy me ha enseñado la prueba "correcta"/"ideal". Pero le preguntaré de nuevo el jueves.

Answer 1

En mi opinión tu tutor está claramente equivocado, demasiado centrado en la prueba a la que está acostumbrado. A menudo es un problema. Permítanme decir que me enfrenté a este problema todo el tiempo, ya que tendía a pensar fuera de la caja y encontrar mi propia, soluciones correctas, diferentes a la canónico uno.

Demostraste por definición, que es una prueba totalmente válida. Por lo tanto, técnicamente no tienes que demostrar nada más.

Sin embargo, como parece que tu tutor no entiende estos conceptos básicos, tienes que ser más listo que él y ser capaz de contraargumentarle (es decir, explicarle por qué su afirmación es claramente errónea).

Mi tutor escribió, que sólo mostré $gcd(a,b+na)\leq gcd(a,b)$ y también hay que mostrar la otra dirección.

En la primera parte de su prueba demostrando que $d$ es divisor de $a$ y $b$ has demostrado que $gcd(a,b) = d \leq gcd(a,b+na)$ . Por definición de $gcd$ (¡el nombre incluso lo representa!) para cualquier divisor dado $z$ de ambos $x$ y $y$ tenemos $z\leq gcd(x,y)$ . Sustituyendo $x=a$ y $y=b+na$ tiene la declaración que su tutor dice que falta.

Permíteme insistir una vez más: no necesitas esa explicación en tu prueba, que es perfectamente válida. Esto es sólo para demostrar que la afirmación de su tutor es errónea.

---

Como anécdota...

En el curso de probabilística que una vez tuvimos algunos simple tarea de combinatoria. Ahora no recuerdo los detalles, pero en realidad es irrelevante. Hice mis cálculos, los verifiqué y como resultado obtuve una solución bonita.

En la siguiente lección presenté la solución en la pizarra. Imagínense mi sorpresa cuando me enteré de que mi solución era incorrecta. Alguien más había hecho la tarea en la pizarra el camino correcto y, efectivamente, los resultados no se parecían en nada. Si no recuerdo mal, ¡incluso se utilizaron potencias diferentes! Por supuesto, la nueva solución era correcto y de acuerdo con la clave, pero yo estaba seguro de que la mía también era correcta (a pesar de todas las probabilidades y de la aparente diferencia), así que la defendí y pedí que me indicaran dónde había cometido un error. Nadie, ni siquiera el tutor, pudo encontrar nada. Finalmente, el tutor dijo que podría ser que los dos polinomios fueran equivalentes y que si yo era capaz de demostrar que que la equivalencia Tendré todo el curso aprobado con la máxima nota.

Huelga decir que me llevó 3 meses de trabajo, algunos cálculos horribles y algún teorema peculiar de la teoría de números, pero lo conseguí. Los dos resultados son equivalentes.

Answer 2

Fin de la prueba. Mi tutor escribió, que sólo mostré $\gcd(a,b+na) \leq gcd(a,b)$ y también hay que mostrar la otra dirección.

Estoy bastante seguro de que $\gcd(a,b+na) \geq gcd(a,b)$ se deduce de $d:=\gcd(a,b)$ y $d\mid(b+na)$ (más la definición de $\gcd$ ).