Demostrar que $\gcd(x, y)=\gcd(x,ax+y)$ ¿Sería este el razonamiento correcto?

Question

Sabemos que $\gcd(x, y) = d$ al dividir d $x$ y $y$ Ahora supongamos que hay $x'$ y $y'$ enteros tales que

$$x = d \cdot x' \implies d|x \\y = d \cdot y' \implies d|y$$

entonces $a \cdot x$ sería

$$a\cdot x = a \cdot d \cdot x'$$

y así $a \cdot x + y$ es igual a

$$a \cdot d \cdot x' + d \cdot y' = d(a \cdot x' + y')$$

que es divisible por d y sabemos que $\gcd(x, y) = d$ Por lo tanto $\gcd(x, y) = \gcd(x, ax + y)$

Gracias de antemano.

Answer 1

No, esto no es correcto.

Usted demostró, que $d|x$ y $d|y$ implica $d|(ax+y)$ . Así que, básicamente, has demostrado que $\gcd(x,y)|\gcd(x,ax+y)$ . Pero todavía no sabes, si $\gcd(x,y)=\gcd(x,ax+y)$ .

Trata de probar la otra dirección asumiendo $d|x$ y $d|(ax+y)$ . Esto implicará $\gcd(x,ax+y)|\gcd(x,y)$ .

Entonces, has terminado.

Answer 2

Sugerencia : Lo que falta en tu prueba es demostrar que $\gcd(ax'+y',x')=1$ . ¿Puede proceder desde aquí?

Para demostrarlo, considere el siguiente razonamiento (por contradicción): Supongamos que $\gcd(ax'+y',x') \neq 1$ entonces existe un número natural $b>1$ tal que $b| (ax'+y')$ y $b|x'$ . Por lo tanto, $b|y'$ .

Pero, ¿es esto posible si $\gcd(x,y)=d$ ??

Answer 3

Una forma ligeramente diferente de ver esto es la siguiente:

1) Si d|x y d|y, entonces d|(ax+y) por tu argumento; así que cualquier divisor común de x e y es un divisor común de x y ax+y.

2) Del mismo modo, si d|x y d|(ax+y), entonces d|y [ya que x=cd y ax+y=bd da y=bd-ax=bd-acd=(b-ac)d]; por lo que cualquier divisor común de x y ax+y es un divisor común de x e y.

Como x e y tienen el mismo conjunto de divisores comunes que x y ax+y gcd(x,y)=gcd(x,ax+y).

Answer 4

Aquí hay una prueba en un estilo diferente, más calculador.

(Estoy asumiendo que todas las variables son enteras, y $\;s,t \geq 0\;$ .)

Tenemos que demostrar una igualdad relacionada con la divisibilidad, por lo que ayuda recordar que cualquier entero no negativo $\;s\;$ y $\;t\;$ son iguales si tienen los mismos divisores: $$(0)\;\;\;s = t \;\equiv\; \langle \forall d :: d|s \equiv d|t \rangle$$

Además, la propiedad clave de $\;\gcd(x,y)\;$ es que sus divisores (y sólo éstos) dividen a ambos $\;x\;$ y $\;y\;$ : $$(1)\;\;\;\langle \forall d :: d|\gcd(x,y) \;\equiv\; d|x \land d|y \rangle$$ (En realidad, ésta podría ser la definición si nos limitáramos a los números no negativos).

Traduciendo la declaración original con $(0)$ y $(1)$ se nos pide que demostremos $$\langle \forall d :: d|x \land d|y \;\equiv\; d|x \land d|(a \cdot x + y) \rangle$$ o de forma equivalente (extrayendo el conjunto común) $$\langle \forall d : d|x : d|y \equiv d|(a \cdot x + y) \rangle$$

Esto último lo podemos demostrar fácilmente, para cualquier $\;d\;$ de la siguiente manera: $$\begin{align} & d|y \;\equiv\; d|(a \cdot x + y) \\ \Leftarrow & \;\;\;\;\;\text{"property of divisibility: numbers are equally divisible if their difference is"} \\ & d|(a \cdot x) \\ \Leftarrow & \;\;\;\;\;\text{"property of divisibility: a divisor of a factor also divides the product"} \\ & d|x \\ \end{align}$$ lo que completa la prueba.