Let $n\ge 2$ be an integer. If $\gcd(a,b^n)=1$, then $\gcd(a,b)=1$ Then I know $ax+b^ny=1$, but I can't figure out what to do from here.  
What could I do to prove this?  
 A: If $\gcd(a,b) = c > 1$, then $c \mid a$ and $c \mid b$. So $c \mid b^n$. So $c \mid ax + b^ny = 1$ contradiction. 
A: Write $a=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$ and $b=p_1^{\beta_1}p_2^{\beta_2}\dots p_k^{\beta_k}$ where $\{p_1,\dots,p_k\}$ is the union of the prime factors of $a$ and $b$ and all of the exponents are nonnegative (read: possibly zero) integers. Then 
$$\gcd(a,b)=p_1^{\min\{\alpha_1,\beta_1\}} p_2^{\min\{\alpha_2,\beta_2\}}\dots p_k^{\min\{\alpha_k,\beta_k\}}=1$$ which implies that for all $i=1,\dots,k$, $\min\{\alpha_i,\beta_i\}=0$. 
Now, $b^n=p_1^{n\beta_1}p_2^{n\beta_2}\dots p_k^{n\beta_k}$. For each $i$, if $0=\min\{\alpha_i, \beta_i\}$ then $0=\min\{\alpha_i, n\beta_i\}$ (prove by cases if you want).
$$\gcd(a,b^n)=p_1^{\min\{\alpha_1,n\beta_1\}} p_2^{\min\{\alpha_2,n\beta_2\}}\dots p_k^{\min\{\alpha_k,n\beta_k\}}=p_1^0 p_2^0 \dots p_k ^0 = 1$$ 
A: We are given $\gcd(a,b^n) = 1$. This means $ax+b^n y = 1 \implies ax+b(b^{n-1}y) = 1$.
Hence, $\gcd(a,b) \vert 1 \implies \gcd(a,b) = 1$.
A: Hint $\,\ c\mid a,b \,\Rightarrow\, c\mid a,b^n\Rightarrow c = 1\,$ (else $\,c>\color{#c00}1\,$ would be a common divisor of $\,a,b^n$ greater than the greatest common divisor of $\,a,b^n,\,$ which $= \color{#c00}1\,$ by hypothesis). 
A: This is simplest using the lattice of divisibility: if $a | b$ and $c | d$, then $\gcd(a,c) | b$ and $\gcd(a,c) | d$, and therefore $\gcd(a,c) | \gcd(b,d)$.
