How to find gcd of $(a,a^n)$

Question

I'm trying to use the Euclidean Algorithm to find the gcd of $(a,a^n)$. I started out with:

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

but now I'm stuck in an endless loop of

$a = 0 \cdot 0 + a$

$0 = a \cdot 0 + 0$.

Where did I go wrong? Any tips would be appreciated.

Answer 1

You don't need the Euclidean algorithm for this scenario.

If $a,b$ are positive integers, and $a|b$, then $\gcd(a,b) = a$.

Hence, if $a,n$ are positive integers, then $\gcd(a,a^n)=a$.

But if you choose to use the Euclidean algorithm, just for the sake of it, then when you reach zero remainder, the $\gcd$ is the divisor that produced the zero remainder, which in this case, is $a$.

Alternatively, the initial divisor can be regarded as the initial remainder. Thus, for each division step, there's always a previous remainder, so when you first reach a remainder of zero, the previous remainder (which is the same as the divisor that produced the zero remainder) is the $\gcd$.

Thus, for your example, since you chose $a$ as the initial divisor, it's also the initial remainder. Since the next remainder is zero, the previous remainder, namely $a$, is the $\gcd$.

Answer 2

The point is that when you get a zero divisor in the Euclidean Algorithm, dividend is the GCD. In this case, the zero pops up more quickly than in most other cases.

Answer 3

You're done; $\gcd(a,0) = a$. You're stuck in a loop because no further reduction is possible.