If $\gcd(a,b)=1$, then $\gcd(a^n,b^n)=1$

Let $a = p_1 ... p_n$ and $b = q_1 ... q_m$ be the prime factorization of $a$ and $b$ (possibly with repetition). $gcd(a,b) = 1$ implies that $p_i \neq q_j$ for all $1 \leq i \leq n$ and $1 \leq j \leq m$. Hence $a^k = p_1^k ... p_n^k$ and $b^k = q_1^k ... q_m^k$ also have no prime factors in commmon. So $gcd(a^k, b^k) = 1$, as well.

We use Bézout's Theorem. Recall that the integers $c$ and $d$ are relatively prime iff there exist integers $x$ and $y$ such that $cx+dy=1$.

Suppose that $\gcd(x,y)=1$, and let $x$ and $y$ be integers such that $ax+by=1$. Then $(ax+by)^{2n-1}=1$. Now imagine expanding $(ax+by)^{2n-1}$ using the Binomial Theorem. There are $2n$ terms in the expansion. The first $n$ terms are divisible by $a^n$, and the last $n$ are divisible by $b^n$. It follows that there are integers $u$ and $v$ such that $a^n u+b^n v=1$. Thus $\gcd(a^n,b^n)=1$.

Lemma: $\gcd(a,b)=1\implies\gcd\left(a^2,b^2\right)=1$

Proof: By Bezout, $\gcd(a,b)=1$ implies $$ \begin{align} ax+by&=1\\ a^2x^2&=1-2by+b^2y^2\\ \left(2y-by^2\right)b&=1-a^2x^2\\ \left(2y-by^2\right)^2b^2&=1-2a^2x^2+a^4x^4\\ \left(2x^2-a^2x^4\right)a^2+\left(2y-by^2\right)^2b^2&=1 \end{align} $$ Therefore, $\gcd\left(a^2,b^2\right)=1$.$\qquad\square$

Corollary: $\gcd(a,b)=1\implies\gcd\left(a^{2^n},b^{2^n}\right)=1$

Proof: Induction using the Lemma.$\qquad\square$

Thus, for any $k$, we can find an $n$ so that $k\le2^n$. The Corollary says that there are $x_n$ and $y_n$ so that $$ a^{2^n}x_n+b^{2^n}y_n=1 $$ and therefore, $$ a^k\left(a^{2^n-k}x_n\right)+b^k\left(b^{2^n-k}y_n\right)=1 $$ Thus, $\gcd(a,b)=1\implies\gcd\left(a^k,b^k\right)=1$.