# How to prove $\gcd(a^m,b^m) = \gcd(a,b)^m$ using Bézout's Lemma

The problem is to prove the following

If $\gcd(a,b) = c$, then $\gcd(a^m, b^m) = c^m$

I know that this can be solved easily by proving that $c\mid a \implies c^m \mid a^m$ and $c\mid b \implies c^m \mid b^m$. So the greatest common divisor of $a^m$ and $b^m$ is $c^m$. But the problem is that I want to use Bézout's Lemma (Identity) to prove this.

I first introduce the following notation:

$$a = ca' \quad \quad b = cb', \quad \quad \text{where (a',b') = 1.}$$

Now from Bézout's Lemma, becaus $a'$ and $b'$ are coprime integers then we have integer solutions for the following equation:

$$a'x + b'y = 1$$

It's obvious that also the following equation has an integer solution:

$$a'^mx_1 + b'^my_1 = 1$$

Although I'm not able to prove this using Bézout's Lemma.

Now multiply both sides by $c^m$ we get:

$$(a'c)^mx + (b'c)^my = c^m$$ $$a^mx + b^my = c^m$$

But Bézout's Lemma states that for given $c^m$ is the greatest common multiplier of $a^m$ and $b^m$ or it is a multiplier of it.

But how to prove that it's not a multiplier of the greatest common multiper, and in fact is the greatest common multiplier. Is it possible to solve this problem with Bézout's Lemma?

• Where is Bill Dubuque, now that we need him? – Gerry Myerson Oct 13 '13 at 12:09
• Your formula after "It is obvious", like many formulas following the phrase "it is obvious", is false. $2(2)+3(-1)=1$, but $2^2(2)+3^2(-1)=8-9=-1$. (But the question is intriguing!) – Eric Stucky Oct 13 '13 at 12:13
• To make it clear. I meaned that: $$ax + by = 1$$ Have solution if (a,b) = 1. That also implies: $$a^mx + b^my = 1$$ have solution. I didn't mean $x$ and $y$ are same numbers, they are just some variables, which are integer solutions. But anyway to make it more clear I'll edit the question. – Stefan4024 Oct 13 '13 at 12:25

Your argument "this can be solved easily" only amounts to a proof that that $c^m$ divides the GCD: it doesn't actually prove $c^m$ actually is the GCD.
The rest of your work provides the other half: that the GCD divides $c^m$.
The only way I see to do the first half of the proof with Bezout's lemma doesn't really amount to anything different: it observes that $c^m | a^m$ and $c^m | b^m$, and thus $c^m | a^m x + b^m y$ for all $x,y$.
Here's a useful trick to fill in your gap: if $c x + d y = 1$, then we also have $(c x + d y)^{2m-1} = 1$ (any power at least $2m-1$ would suffice for this trick). You can expand this and collect terms to find an identity $c^m u + d^m v = 1$.
• Nice answer. It seemed that I had both parts, but I wasn't able to connect them. And I love your useful trick. Previously I raised both sides to $m$, an I was unable to do the rest of the work. – Stefan4024 Oct 13 '13 at 12:31
• If you raise both sides to the $m$ power, then you can still rearrange to get $c^m u + dv = 1$. Then you repeat the trick. :) – user14972 Oct 13 '13 at 12:32