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?

  • 4
    $\begingroup$ Where is Bill Dubuque, now that we need him? $\endgroup$ – Gerry Myerson Oct 13 '13 at 12:09
  • $\begingroup$ 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!) $\endgroup$ – Eric Stucky Oct 13 '13 at 12:13
  • $\begingroup$ 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. $\endgroup$ – Stefan4024 Oct 13 '13 at 12:25

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

  • $\begingroup$ 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. $\endgroup$ – Stefan4024 Oct 13 '13 at 12:31
  • 1
    $\begingroup$ 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. :) $\endgroup$ – user14972 Oct 13 '13 at 12:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.