For all $n \geq 1$, and positive integers $a,b$ show: If $\gcd (a,b)=1$, then $\gcd(a^n,b^n)=1$ For all $n \geq 1$, and positive integers $a,b$ show: 
If $\gcd (a,b)=1$, then $\gcd(a^n,b^n)=1$
So, I wrote the $gcd (a,b)=1$ as a linear combination: $ax+by=1$
And, I wrote the $gcd(a^n,b^n)=1$ as a linear combination: $a^n (u)+b^n (v)=1$
can I write the second linear combinations with $x,y$ and then raise the first equation to the nth power or not? 
 A: You can use the unique prime factorization to show this result logically . If $a$ & $b$ are relatively prime then they have no common prime factors. Therefore any power of $a$ & $b$ will just repeat each of the prime factors $n$ times. Therefore $a^n$ and $b^n$ still have no common prime factors and therefore are relatively prime.  
A: $$
(a,b)=1\implies ax+by=1
$$
Therefore
$$
\begin{align}
a^nx^n
&=(1-by)^n\\
&=1+b\left(\sum_{k=1}^n\binom{n}{k}b^{k-1}(-y)^k\right)
\end{align}
$$
and
$$
a^nx^n-b\left(\sum_{k=1}^n\binom{n}{k}b^{k-1}(-y)^k\right)=1
$$
Thus, $(a^n,b)=1$. Apply the process again to get $(a^n,b^n)=1$

Another Approach is presented in this answer.
A: There are many ways to prove this, depending on one's background and the desired generality. Below are a few, some well-known, some not. First, the most obvious is to use the fundamental theorem of arithmetic, i.e. existence and uniqueness of prime factorizations, e.g. as follows:
Hint $\ $ prime $\,p\:|\:a^n,b^n\:\Rightarrow\:p\:|\:a,b,\:$ since prime $\:p\:|\:d_1\cdots d_k\:\Rightarrow\:p\:|\:d_1\ $ or $\,\ldots\,$ or $\:p\:|\:d_k\,$   
Alternatively, it may be derived as  a simple inductive consequence of Euclid's Lemma, i.e. $\,(a,b)=1=(a,\,c)\ \color{#c00}{\Rightarrow}\,(a,bc)=1.\,$ Hence for $\,c=b\,$ we infer $\,(a,b^2)=1,\,$ and by induction $\,(a,b)=1=(a,b^n)\color{#c00}\Rightarrow\,(a,b^{n+1})=1.\,$ Reversely, inducting in the same way on powers of $\,a,\,$
$\,(b^n,a) = 1\,\color{#c00}\Rightarrow\, (b^n,a^2) = 1\,\ldots\,\color{#c00}\Rightarrow\, (b^n,a^k) = 1.$
Alternatively, Gauss's Lemma (GL) yields a quick proof. Let $\rm\:{\cal C}(f)\:$ denote the content of a polynomial, i.e. the gcd of its coefficients. GL states $\rm\: {\cal C}(f\,g)\ =\ {\cal C}(f)\ {\cal C}(g)\ $ hence
$\rm\qquad\qquad\qquad\ \ 1\ =\ (a,b)\ =\ {\cal C}\:(a\ x + b)\ =\  {\cal C}\:(a\ x - b)$
$\rm\qquad\qquad \Rightarrow\ \ 1\ =\ {\cal C}\:((a\ x + b)\:(a\ x - b))\ =\ {\cal C}\:(a^2\: x^2 - b^2)\: =\: (a^2,b^2)$ 
Iterating shows $\rm\,(a^n,b^n) = 1\,$ for $\rm\,n = 2^k,\,$ hence for all $\rm\:n,\:$ by $\rm\,m\le n\,\Rightarrow\,(a^m,b^m)\:|\:(a^n,b^n),\,$ another example of the "up then down" (or interval) induction.
More generally, one easily proves the Freshman's Dream $\,(a,b)^n = (a,b)^n\,$ for gcds or invertible ideals, by simple high-school arithmetic using their familiar arithmetical laws (associative, commutative, distributive,cancellative) along with the more special idempotent law $(a,a) = (a).$ The Bezout-based proofs in the answer of André and Rob are special cases of this method.
A: As you wrote, there exist integers $x$ and $y$ such that $ax+by=1$. It follows that
$$(ax+by)^{2n-1}=1.$$
Expand $(ax+by)^{2n-1}$ using the Binomial Theorem. Any term $\binom{2n-1}{k}(ax)^k (by)^{2n-1-k}$ of the expansion is divisible by $a^n$ or $b^n$.  For if $k\ge n$, the term is divisible by $a^n$, and if $k\le n-1$ then the term is divisible by $b^n$. 
Thus $1$ is an integer linear combination of $a^n$ and $b^n$. 
Remark: We used the smallest exponent $2n-1$ that makes the argument work. Any exponent $\ge 2n-1$ also works. 
A: Lemma 1. If $a$ divides $bc$ and $\gcd(a,b)=1$, then $a|c$.
Proof. If $\gcd(a,b)=1$, then there are $x,y$ integers such that $ax+by=1$. Thus, $acx+bcy=c$, and $a$ divides $a$ and $bc$, so it divides $acx+bcy$, thus it also divides $c$.
Lemma 2. If $\gcd(e,f)=1$, then $\gcd(e,f^n)=1$ for all $n\geq 1$.
Proof (by induction on $n$). The base case $n=1$ is clear. Now suppose that if $\gcd(e,f)=1$, then $\gcd(e,f^n)=1$. Let $d$ be a common divisor of $e$ and $f^{n+1}$. Since $\gcd(e,f^n)=1$ and $d|(f^n)\cdot f$ it follows that $d$ divides $f$. But $\gcd(e,f)=1$, so $d=1$. Hence, $\gcd(e,f^{n+1})=1$ and this proves the induction step. Therefore, by the principle of mathematical induction, $\gcd(e,f)=1$ implies $\gcd(e,f^n)=1$ for all $n\geq 1$.
Proposition. If $\gcd(a,b)=1$, then $\gcd(a^m,b^n)=1$ for all $n,m\geq 1$.
Proof. By Lemma 2, if $\gcd(a,b)=1$, then $\gcd(a,b^n)=1$ for all $n\geq 1$. And again by Lemma 2, if $\gcd(b^n,a)=1$, then $\gcd(b^n,a^m)=1$ for all $m\geq 1$, as claimed.
