Prove that if $\gcd(a,b)=1$ then $\gcd(a^m, b)=1$ I am using the Euclidean Algorithm (EA) for proof. Let $a>b$ and by EA we have
$$
\begin{align}
a=q_0 b+r_1 & & &  \text{where }0\leq r_{1}<b \\
b=q_1 r_1+r_2 & & & \text{where }0\leq r_2<r_1 \\
\vdots & & & \vdots \\
r_{n}=q_{n+1}r_{n+1}+r_{n+2} & & & \text{where } 0\leq r_{n+1}<r_{n+2} \\
r_{n+1}=q_{n+2}r_{n+2}
\end{align}
$$
where $ r_{n+2}=1$ beacuse the $\gcd(a,b)=1$. Now for $a^2$ we have
$$\hspace{30pt} a^2=q_{0}^\prime b + r_{1}^\prime\hspace{70pt}\text{where }0\leq r_{1}^\prime<b$$
Here I stuck and don't know to continue the prove because the value of $r_{1}$ is not necessarily to be equal to $r_{1}^\prime$ 
 A: Use Fundamental theorem of arithmetic. Let:
$$a=\prod_{i=1}^{k}p_i^{\alpha_i}$$
$$b=\prod_{i=1}^{m}q_i^{\beta_1}$$
Where $p_i,q_i$ are prime and $k,m,\alpha_1,\beta_i \in \mathbb{N} \cup \{0\}$ for $i=1,2,\ldots,\max(k,m)$.
By $\gcd(a,b)=1$ you know that $\{p_1,p_2,\ldots, p_k\} \cap \{q_1,q_2,\ldots,q_m\}=\emptyset$. But :
$$a^n=\prod_{i=1}^{k}p_i^{n\alpha_i}=\prod_{i=1}^{k}p_i^{\gamma_i}$$
Where $\gamma_i=n\alpha_i$.
You know that set $\{p_1,p_2,\ldots, p_k\}$ and $ \{q_1,q_2,\ldots,q_m\}$ are disjoint, so $\gcd(a^n,b)=1$.
A: I prefer to argue as follows. Suppose that $\gcd(a^m,b)\gt 1$.  Then some prime $p$ divides $\gcd(a^m,b)$. Thus $p$ divides $a^m$ and $p$ divides $b$.
From $p$ divides $a^m$ (with $m\ge 1)$ we conclude by Euclid's Lemma that $p$ divides $a$. It follows that $p$ divides $\gcd(a,b)$, contradicting the fact that $\gcd(a,b)=1$.
Remarks: $1.$ Here is a kind of cute alternate proof. Since $\gcd(a,b)=1$, there exist integers $x$ and $y$ such that $ax+by=1$. It follows that
$$(ax+by)^{m+1}=1.$$
If we expand $(ax+by)^{m+1}$ using the Binomial Theorem, we get an expression of the shape $a^mX+bY$. Since this is $1$, it follows that $a^m$ and $b$ are relatively prime. 
To identify $X$ and $Y$, it is useful to look at the special case $m=2$ or $m=3$. 
$2.$ The Euclidean Algorithm strategy is an interesting one. However, I do not see an obvious way to write what happens when we apply it to $a^m$ and $b$ in terms of what happens when we apply it to $a$ and $b$. 
