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

1.1k Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

You need both parts of your work to get the proof.

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