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

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

Lemma. If $(x,y)=1$ then $(xz,y)=(z,y)$.

In words: we can add a factor to one side of the gcd provided it is coprime to the other side. Carefully adjoining factors $a$ and $b$ should allow to eventually get $(a^n,b^n)=1$ from $(a,b)=1$.

Here comes a proof of the following more general fact:

Theorem. If $(a,b)=1$ then $(a^m,b^n)=1$ for all $m,n>0$.

The adjoining of factors $a$ and $b$ is cleanest when done with induction.

Proof. By induction on $m+n$. True for $m+n=2$. $\checkmark$
Induction step: Let $m+n>2$ and suppose wlog $m>1$. Let $x=a$, $y=b^n$, $z=a^{m-1}$. By the induction hypothesis, $(x,y)=1$, and the lemma gives $$(\underset{xz}{a^m},\underset y{b^n})=(\underset xa\cdot \underset z{a^{m-1}},\underset y{b^n})=(\underset z{a^{m-1}},\underset y{b^n})$$ which is $1$ by the induction hypothesis, as $m-1+n<m+n$. $\square$

-

Suppose $\gcd(a^n,b^n)\gt1$. Let $d\gt1$ be a common divisor, and let $p$ be a prime divisor of $d$. Then $p$ divides both $a^n$ and $b^n$. But an elementary induction argument, using the theorem that if a prime divides a product of two numbers then it divides one of the two factors, shows that $p\mid x^n$ implies $p\mid x$ for any (integer) $x$. Hence $p$ divides both $a$ and $b$, implying $p\mid\gcd(a,b)$, which contradicts the assumption $\gcd(a,b)=1$.

Note: The key step, $p\mid x^n\Longrightarrow p\mid x$, is Proposition 12 of Book IX in Euclid's Elements.

-

Master plan for proof — You just need to show that $\gcd(\alpha,\beta) = 1 \implies \gcd(\alpha^n,\beta) = 1$.

Why? After you prove that, the key is \begin{align} 1 = \gcd(a^n,b) & = \gcd(b,a^n) \\ & {\huge{\color{cyan}{=}}} \gcd(b^n,a^n) = \gcd(a^n,b^n) \end{align}.
The cyan equality hails from the master plan by cause of substituting $\alpha = b$ and $\beta = a^n$.

From Bézout's identity, $\gcd(a,b) = 1 \iff \exists \; x,y: ax + by = 1$

Given $\gcd(a,b) = 1$, there exist integers $x$ and $y$ such that $ax + by = 1$. So $(ax + by)^n = 1$.

Expand $(ax + by)^n$ by reason of Binomial Theorem —
$(ax+by)^{n} = \sum_{0 \le k \le n}\dbinom{n }{k}(ax)^k(by)^{n -k}$ $= \color{brown}{\dbinom{n }{n}(ax)^n(by)^{n - n}} + \color{blue}{\sum_{0 \le k \le n - 1} \dbinom{n}{k}(ax)^k(by)^{n -k}}$

Therefore $(ax + by)^n = \color{brown}{a^nx^n}$ + the blue bunch of other terms that are each divisible by $b$.
So there exists $y'$ such that $\color{brown}{a^nx^n} + \color{blue}{by'} = 1$.
So by reason of all those equalities in the master plan, $\gcd(a^n,b) = 1$.

-

Lemma: $\gcd(a,b)=1\implies\gcd\left(a^2,b^2\right)=1$

Proof: By Bezout, $\gcd(a,b)=1$ implies \begin{align} ax+by&=1\\ a^2x^2&=1-2by+b^2y^2\\ \left(2y-by^2\right)b&=1-a^2x^2\\ \left(2y-by^2\right)^2b^2&=1-2a^2x^2+a^4x^4\\ \left(2x^2-a^2x^4\right)a^2+\left(2y-by^2\right)^2b^2&=1 \end{align} Therefore, $\gcd\left(a^2,b^2\right)=1$.$\qquad\square$

Corollary: $\gcd(a,b)=1\implies\gcd\left(a^{2^n},b^{2^n}\right)=1$

Proof: Induction using the Lemma.$\qquad\square$

Thus, for any $k$, we can find an $n$ so that $k\le2^n$. The Corollary says that there are $x_n$ and $y_n$ so that $$a^{2^n}x_n+b^{2^n}y_n=1$$ and therefore, $$a^k\left(a^{2^n-k}x_n\right)+b^k\left(b^{2^n-k}y_n\right)=1$$ Thus, $\gcd(a,b)=1\implies\gcd\left(a^k,b^k\right)=1$.

-

You just need to show that $\gcd(a,b) = 1 \implies \gcd(a^n,b) = 1$, then you have $1 = \gcd(a,b) = \gcd(a^n,b) = \gcd(b,a^n) = \gcd(b^n,a^n) = \gcd(a^n,b^n)$.

From Bézout's identity, $\gcd(a,b) = 1 \iff \exists x,y: ax + by = 1$

Given $\gcd(a,b) = 1$, there exist integers $x$ and $y$ such that $ax + by = 1$. So $(ax + by)^n = 1$.

You can expand $(ax + by)^n$ to get $a^nx^n$ plus a bunch of other terms that are each divisible by $b$. So there exists $y'$ such that $a^nx^n + by' = 1$, so $\gcd(a^n,b) = 1$.

-

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 $(ax+by)^{2n-1} = \sum_{0 \le k \le 2n - 1}\dbinom{2n - 1}{k}(ax)^k(by)^{(2n - 1)-k}$
$= \color{blue}{\sum_{0 \le k \le n - 1} \dbinom{2n - 1}{k}(ax)^k(by)^{(2n - 1)-k}}+ \color{brown}{\sum_{n \le k \le 2n - 1} \dbinom{2n - 1}{k}(ax)^k(by)^{(2n - 1)-k}}$

There are $2n$ terms in the expansion. Note — this part is opposite to Andre Nicolas's answer.
The first $n$ — the blue terms — are divisible by $b^n$.
The last $n$ terms — the brown terms — are divisible by $a^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$.

-

Here's a colored, edited version of user17762's answer.

The proof is by induction. Let us denote $\gcd(a,b) = d$. It's given $\gcd(a,b) = 1 \iff$
by Bezout's Lemma, there exist $x,y \in \mathbb{Z}$ such that $ax+by = d. (\dagger)$

Assume that the statement is true for all $n \leq k$. Scilicet $\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$.

Multiply this with $(\dagger)$ to result in \begin{align} (ax+by) \left( a^k x_k + b^k y_k \right)^2 & = d^{2k+1}. \\ \color{green}{a^{2k + 1}xx_k^2 + a^{k + 1}2b^kx_ky_kx} \color{blue}{+ ab^{2k}yk^2x} &= \\ + \color{red}{a^{2k}bx_k^2y} + b^{k + 1}2a^kx_ky_ky + b^{2k+1}y_k^2y \end{align}

$LHS = \color{green}{a^{k+1} \left( a^k x_k^2 x \color{red}{+ 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 + \color{blue}{ab^{k-1} y_k^2 x} + 2 a^k x_k y_k y \right)$

Since $d|a$ and $d|b$, we have that $\color{brown}{a = d e}$ and $\color{brown}{b = df}$. $LHS = a^{k+1} \left( \color{brown}{d^k e^k} x_k^2 x + \color{brown}{d^k e^{k-1} f} x_k^2 y + 2\color{brown}{ d^k f^k} x_k y_k x \right) + b^{k+1} \left( \color{brown}{d^k f^k} y_k^2 y + \color{brown}{d^k ef^{k-1}} y_k^2 x + 2 \color{brown}{d^k e^k} x_k y_k y \right)$

Divide both sides by $d^k$ to result in $$a^{k+1} \underbrace{( e^k x_k^2 x + e^{k-1} f x_k^2 y + 2 f^k x_k y_k x)}_{\huge{x_{k+1}}} + b^{k+1} \underbrace{\left( f^k y_k^2 y + ef^{k-1} y_k^2 x + 2 e^k x_k y_k y \right)}_{\huge{y_{k+1}}} = d^{k+1}.$$ Hence, we have found integers $x_{k+1}, \, y_{k+1}$ such that $a^{k+1} x_{k+1} + b^{k+1} y_{k+1} = d^{k+1}$
$\iff \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})$.

In all , we get that $\gcd(a^{k+1}, b^{k+1}) = \gcd(a,b)^{k+1}.$
Hence, by the principle of mathematical induction $\gcd(a^n,b^n) = \gcd(a,b)^n, \,\, \forall n \in \mathbb{N}.$

-

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.

-

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

-
Nicely done. (+1) The extra detail to your answer added by Dwayne Pouiller brought this to my notice, and I added another Bezout proof. – robjohn Jan 4 '14 at 23:20

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 Dachiraju 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. – dx7hymcxnpq Jul 5 '12 at 6:41

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

-