Prueba de la propiedad asociativa gcd:

Question

Estoy tratando de probar la propiedad asociativa para el $\gcd(a,b)$ función.

$$\gcd( a ,\space \gcd(b,c) ) = \gcd(\space \gcd(a,b) , c )$$

Déjalo:

$$e = \gcd( a ,\space \gcd(b,c) )\text{ and }f = \gcd(\space \gcd(a,b) , c )$$

Desde aquí se puede ver que

$$ e\mid a,\gcd(b,c) \Longleftrightarrow e\mid a,b,c $$

Y de manera similar,

\begin{align*} f|\gcd(a,b),c &\Longleftrightarrow f\mid a,b,c\\ &\Longleftrightarrow f\mid e\\ &\Longleftrightarrow e\mid f \end{align*}

Si $ e\mid f$ y $f\mid e \Longrightarrow |e| = |f| $ y como $e$ y $f$ son ambas no negativas tenemos el resultado, $e = f$ según sea necesario.

¿Esta prueba es sólida?

Answer 1

La idea es buena. Pero los numerosos símbolos lógicos oscurecen la lógica del argumento.

Como usted escribió, deje que $e=\gcd(a,\gcd(b,c))$ y $f=\gcd(\gcd(a,b),c)$ .

Queremos demostrar que $e$ divide $f$ y $f$ divide $e$ . Demostremos que $e$ divide $f$ . (Observación: no es buena idea intentar demostrar dos cosas a la vez).

Porque $e=\gcd(a,\gcd(b,c))$ se deduce que $e$ divide $a$ y $e$ divide $\gcd(b,c)$ . Así que $e$ divide $a$ , $b$ y $c$ .

De ello se desprende que $e$ divide $\gcd(a,b)$ y $e$ divide $c$ . Esto implica que $e$ divide $\gcd(\gcd(a,b),c)$ Es decir, $e$ divide $f$ .

El hecho de que $f$ divide $e$ se demuestra de la misma manera.

Observación: Hemos utilizado sin pruebas el hecho de que $x$ divide $y$ y $z$ si y sólo si $x$ divide $\gcd(y,z)$ . Una dirección es obvia. Pero si definimos $\gcd(y,z)$ como el mayor divisor común de $y$ y $z$ no es obvio que si $x$ divide $y$ y $z$ entonces $x$ divide $\gcd(y,z)$ . Pero podemos conseguirlo utilizando el Teorema de Bezout, y de otras maneras.

Answer 2

Podemos probar de la siguiente manera:

Denotemos $(x,y)$ como gcd $(x,y)$

Que las potencias más altas de los primos $p$ en $a,b,c$ son $A,B,C$ respectivamente.

Por lo tanto, la mayor potencia de $p$ que divide $(b,c)$ será máximo $(B,C)$

Del mismo modo, la mayor potencia de $p$ que divide $(a,b)$ será máximo $(A,B)$

Por lo tanto, la mayor potencia de $p$ que divide $(a,(b,c))$ será máximo $(A, $ max $(B,C))=$ max $(A,B,C)$

Del mismo modo, la mayor potencia de $p$ que divide $((a,b),c)$ será máximo $($ max $(A,B),C))=$ max $(A,B,C)$

Así que, $(a,(b,c))=(a,(b,c))=(a,b,c)$