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

This seems clear, but i don't know how to prove this..

I was trying to show this by induction such that if $a^{n+1}$ = $rs$ and $b^{n+1}$ = $rt$, then $s,t$ are divisible by $a,b$ respectively, but i think this is a wrong way..

-
Suppose prime $p\mid a^n$ and $p\mid b^n$, thus $p\mid a$ and $p\mid b$, so $p\mid\gcd(a,b)$. –  Frank Science Jul 5 '12 at 3:01
Induction is the way to go here! Prove by induction that $(a^n,b)=1$.Then that $(a,b^n)=1$. Profit. –  Pedro Tamaroff Jul 5 '12 at 3:01
Possible duplicate of math.stackexchange.com/questions/63323/… –  lhf Jul 5 '12 at 3:20
@lhf Not exactly a duplicate since that question specifically asks for the proof using fundamental theorem of arithmetic. –  user17762 Jul 5 '12 at 3:21

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.

-
I guess it is $p_i \ne q_j$ –  Rajesh D Jul 5 '12 at 3:25
@RajeshD Yes, thanks for pointing that out. –  William Jul 5 '12 at 3:26
+1 for giving the simple, elegant proof. –  mlbaker Jul 5 '12 at 6:41

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$.

-

The proof is by induction. Let us denote $\gcd(a,b) = d$.

For $n=1$, there is nothing to prove. Assume that it is true for all $n \leq k$ i.e. $\gcd(a^n,b^n) = d^n$ for all $n \leq k$. We now need to prove that $\gcd(a^{k+1},b^{k+1}) = d^{k+1}$. Since $\gcd(a^k,b^k) = d^k$, there exists $x_k,y_k \in \mathbb{Z}$ such that $a^k x_k + b^k y_k = d^k$. We also have $x,y \in \mathbb{Z}$ such that $ax+by = d$. Hence, we get that $$(ax+by) \left( a^k x_k + b^k y_k \right)^2 = d^{2k+1}.$$ Expanding this, we get that $$a^{k+1} \left( a^k x_k^2 x + a^{k-1} b x_k^2 y + 2 b^k x_k y_k x \right) + b^{k+1} \left( b^k y_k^2 y + ab^{k-1} y_k^2 x + 2 a^k x_k y_k y \right) = d^{2k+1}.$$ Since $d|a$ and $d|b$, we have that $a = d e$ and $b = df$. Hence, we get that $$a^{k+1} \left( d^k e^k x_k^2 x + d^k e^{k-1} f x_k^2 y + 2 d^k f^k x_k y_k x \right) + b^{k+1} \left( d^k f^k y_k^2 y + d^k ef^{k-1} y_k^2 x + 2 d^k e^k x_k y_k y \right) = d^{2k+1}.$$ This gives us that $$a^{k+1} \left( e^k x_k^2 x + e^{k-1} f x_k^2 y + 2 f^k x_k y_k x \right) + b^{k+1} \left( f^k y_k^2 y + ef^{k-1} y_k^2 x + 2 e^k x_k y_k y \right) = d^{k+1}.$$ Hence, we have found integers $$x_{k+1} = \left( e^k x_k^2 x + e^{k-1} f x_k^2 y + 2 f^k x_k y_k x \right), \, y_{k+1} = \left( f^k y_k^2 y + ef^{k-1} y_k^2 x + 2 e^k x_k y_k y \right)$$ such that $$a^{k+1} x_{k+1} + b^{k+1} y_{k+1} = d^{k+1}.$$ Hence, we have that $\gcd(a^{k+1}, b^{k+1}) \vert d^{k+1}$. It is also true that $d^{k+1} \vert a^{k+1}$ and $d^{k+1} \vert b^{k+1}$, since $d \vert a$ and $d \vert b$. Hence, $d^{k+1} \vert \gcd(a^{k+1}, b^{k+1})$. Hence, we get that $$\gcd(a^{k+1}, b^{k+1}) = \gcd(a,b)^{k+1}.$$ Hence, by the principle of mathematical induction, we have that $$\gcd(a^n,b^n) = \gcd(a,b)^n, \,\, \forall n \in \mathbb{Z}^+.$$

-
This is the best answer posted. One rarely has to appeal to the sledgehammer of unique factorization. –  Potato Jul 5 '12 at 3:32
@Potato Personally I like André Nicolas's one a bit more. Both answers used Bézout critically but André's argument seems cleaner due to the Binomial trick. –  Ragib Zaman Jul 5 '12 at 3:42
I did not see André's! His is good as well! My point is that I see the fundamental theorem used in many places where Bézout and little ingenuity will suffice. –  Potato Jul 5 '12 at 3:44
@RagibZaman Yes. Andre's answer is indeed elegant. Though if $(a,b) = d > 1$, I think you need to resort to an argument similar to mine. –  user17762 Jul 5 '12 at 4:51
I can't see how unique factorization can possibly be a sledgehammer when dealing with anything in number theory at any level at least at senior high school or college. Marvis's proof has the charm of dealing with it using induction yet he uses Bezout's Identity, which I guess could also be called "sledgehammer" –  DonAntonio Jul 5 '12 at 11:55

Assuming that we're working in a Unique Factorization Domain, then the factorizations of $a^n$ and $b^n$ are simply the factorizations of $a$ and $b$, repeated $n$ times. Then if there were a common factor between $a^n$ and $b^n$, there would be a common irreducible factor between $a^n$ and $b^n$, and this would have to appear in the factorizations of both $a$ and $b$, and since $\operatorname{gcd}(a,b) = 1$, $\operatorname{gcd}(a^n,b^n) = 1$.

-

Hint $\$ prime $\rm\,p\:|\:a^n,b^n\:\Rightarrow\:p\:|\:a,b\:$ since prime $\rm\:p\:|\:d_1\cdots d_k\:\Rightarrow\:p\:|\:d_1\$ or $\rm\,\ldots\,$ or $\rm \,p\:|\:d_k\,$

Alternatively, more generally, see my post here on the "freshmans dream" for gcds or ideals.

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 that $\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.

-