Defining the dividend in a gcd problem 
Use induction to show that if $(a, b) = 1$, then $(a, b^n) = 1$ for all $n \ge 1$.

I have set up the skeleton of the proof by induction, but having trouble showing the most important(?) step:
$(a, b^n) = 1$ for $n = 1$ by hypothesis. 
Let  $1  = ax + by =  \ldots =(ax + b^{n + 1}y)$. 
$(a, bb^n) | a, bb^n \to (a, bb^n) |  (ax + b^{n + 1}y) \to (a, bb^n) |  1$.
I am having problem filling in the missing equalities $1  = ax + by =  \ldots =(ax + b^{n + 1}y)$. Is that even possible?
 A: The result clearly holds when $n=1$. We show that if the result holds when $n=k$, then the result holds when $n=k+1$. 
So we wish to show that $(a,b^{k+1})=1$. Suppose to the contrary that $a$ and $b^{k+1}$ have a non-trivial common divisor. Then $a$ and $b^{k+1}$ have a common prime divisor $p$. Since $p$ divides $b^k\cdot b$, it follows that $p$ divides $b^k$ or $p$ divides $b$. But $p$ cannot divide $b$, since $(a,b)=1$. And $p$ cannot divide $b^k$, since if it does we have $(a,b^k)\gt 1$, contradicting the induction hypothesis.
Remarks: $1.$ If you wish to use a Bezout Identity argument, you could say that there exist integers $s$ and $t$ such that $as+tb=1$. By the induction hypothesis, there exist integers $u$ and $v$ such that $au+b^kv=1$. Multiply. We 
get
$$a(sau+sb^kv+tbu)+b^{k+1}(tbv)=1,$$
and the result follows.
$2.$ Another way to prove the induction step is to prove the preliminary lemma that if $(a,s)=1$ and $(a,t)=1$ then $(a,st)=1$. Then for the induction step we take $s=b^k$ and $t=b$. 
A: If we have $x,y$ so that
$$
ax+by=1
$$
then we can use the Binomial Theorem to get
$$
\begin{align}
1
&=(ax+by)^n\\
&=\sum_{k=0}^n\binom{n}{k}(ax)^k(by)^{n-k}\\
&=\overbrace{\color{#C00000}{b^n}y^n}^{k=0\text{ term}}+\color{#C00000}{a}x\sum_{k=1}^n\binom{n}{k}(ax)^{k-1}(by)^{n-k}
\end{align}
$$
A: Here's a non-induction proof:
Let $b = p_1^{m_1}\cdots p_k^{m_k}$ be the prime facotrization of $b$. Then $b^n = p_1^{n\cdot m_1}\cdots p_k^{n \cdot m_k}$. 
Suppose $\gcd(a,b^n) = d > 1$. Then $d = p_1^{l_1}\cdots p_k^{l_k}$, where $0 \leq l_i \leq n \cdot m_i$ for $i = 0,1,\ldots,k$, and $l_i \geq 1$ for at least one $i$. 
Let $d' = p_1^{l_1 \mod{m_1}}\cdots p_k^{l_k \mod{m_k}}$. Note that $d>1 \Rightarrow d' >1$. Clearly $d'|d$, and thus $d'|a$. But also $d'|b$ since $0 \leq l_i \mod{m_i} \leq m_i$ for each $i$. Thus $\gcd(a,b) \geq d' >1$, contradiction.
