# 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)$. – Yai0Phah 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

## 12 Answers

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

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

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

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

Hint $$\$$ prime $$\rm\,p\mid a^n,b^n\Rightarrow\:p\mid a,b\:$$ since prime $$\rm\:p\mid d_1\cdots d_k\:\Rightarrow\:p\mid d_1\$$ or $$\rm\,\ldots\,$$ or $$\rm \,p\mid 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.

Corollary $$\,\ (A^n,B^n) = (A,B)^n$$

Proof  Cancelling $$\, c^n := (A,B)^n$$ reduces it to the above, by $$\,(A/c,B/c) = (A,B)/c = 1$$

• Remark  Scaling extends it to $\rm\ \large (a^n,b^n) = (a,b)^n\$ by exploiting that it is homogeneous. – Bill Dubuque Oct 10 '18 at 20:23

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

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

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.

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

I expose more steps in NovaDenizen's answer.

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

I add more details to Andre Nicolas's answer.

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