Cómo encontrar el CDG de $(a,a^n)$

Question

Estoy tratando de usar el Algoritmo Euclidiano para encontrar el CDG de $(a,a^n)$ . con el que empecé:

$a^n = a \cdot a^{n-1} + 0$

pero ahora estoy atrapado en un bucle sin fin de

$a = 0 \cdot 0 + a$

$0 = a \cdot 0 + 0$ .

¿En qué me equivoqué? Cualquier consejo sería apreciado.

Answer 1

No necesitas el algoritmo euclidiano para este escenario.

Si $a,b$ son enteros positivos, y $a|b$ entonces $\gcd(a,b) = a$ .

Por lo tanto, si $a,n$ son enteros positivos, entonces $\gcd(a,a^n)=a$ .

Pero si se opta por utilizar el algoritmo euclidiano, sólo por el hecho de hacerlo, entonces cuando se llega al resto cero, el $\gcd$ es el divisor que produjo el resto cero, que en este caso, es $a$ .

Alternativamente, el divisor inicial puede considerarse como el resto inicial. Así, para cada paso de la división, siempre hay un resto anterior, por lo que cuando se llega por primera vez a un resto de cero, el resto anterior (que es el mismo que el divisor que produjo el resto cero) es el $\gcd$ .

Así, para su ejemplo, ya que eligió $a$ como el divisor inicial, también es el resto inicial. Como el siguiente resto es cero, el resto anterior, es decir $a$ es el $\gcd$ .

Answer 2

La cuestión es que cuando se obtiene un divisor cero en el Algoritmo Euclidiano, el dividendo es el GCD. En este caso, el cero aparece más rápidamente que en la mayoría de los otros casos.

Answer 3

Ya está; $\gcd(a,0) = a$ . Estás atrapado en un bucle porque no es posible una mayor reducción.