3
$\begingroup$

How to prove $\gcd(a^2, b^2) = (\gcd(a, b))^2$?

My attempt:

Let $\gcd(a, b) = d$.

Then $d|a$ and $d|b$ then $d^2|a^2$ and $d^2|b^2$. i.e $d^2$ divides $a^2 ~~\&~~ b^2$.

$\endgroup$
  • $\begingroup$ your approach is correct. $\endgroup$ – user97615 Nov 25 '16 at 16:20
  • $\begingroup$ Prime factorization $\endgroup$ – Jacob Wakem Nov 25 '16 at 16:26
7
$\begingroup$

Hint: Factor $a$ and $b$ into primes. If $a=p_1^{n_1}\\cdot\ldots\cdot p_k^{n_k}$ and $b=p_1^{m_1}\cdot\ldots\cdot p_k^{m_k}$ with each $n_i,m_i\ge 0$. Then

$$(a,b)=p_1^{\min\{n_1,m_1\}}\cdot\ldots\cdot p_k^{\min\{n_k,m_k\}}.$$

$\endgroup$
  • $\begingroup$ Please explain in details. $\endgroup$ – user1942348 Mar 21 '15 at 18:40
  • 1
    $\begingroup$ If you square a number this amounts to doubling all the exponents in its prime factorization. $\min(2x,2y) = 2\min(x,y)$ so this proves it. You can prove virtually any fact about $\gcd$ using this method; it's usually much easier and more direct. $\endgroup$ – Ibrahim Tencer Mar 21 '15 at 21:06
2
$\begingroup$

If $\gcd(a,b)=d$, then
$a = a'd$
$b = b'd$
and $\gcd(a',b') = 1$

That means
$a^2 = {a'}^2d^2$
$b^2 = {b'}^2d^2$
and $\gcd({a'}^2,{b'}^2) = 1$ $ ~~\color{red}{ \star }$

Hence $\gcd(a^2,b^2)=d^2$.

$ ~~\color{red}{ \star }$ pelase see this.

$\endgroup$
  • 2
    $\begingroup$ Not a good solution in my opinion because you've used the fact that if $\gcd (a',b')=1$ then $\gcd(a'^2,b'^2)=1$ this is what the question asks to prove! $\endgroup$ – Fermat Mar 21 '15 at 18:58
  • $\begingroup$ As $$\gcd(a,b)=d\iff \gcd({a\over d},{b\over d})=1$$ $\endgroup$ – Fermat Mar 21 '15 at 19:02
  • $\begingroup$ Yeah we can add that line $\endgroup$ – AgentS Mar 21 '15 at 19:04
  • 1
    $\begingroup$ It seems to me there's a tacit lemma lurking in the background here: If $(r,s)=(r,t)=1$, then $(r,st)=1$. $\endgroup$ – Barry Cipra Mar 21 '15 at 19:08
  • 2
    $\begingroup$ Knowing the fact that I mentioned in the first comment, the proof can be done in a line: $$\gcd(a,b)=d\implies \gcd({a\over d},{b\over d})=1\implies \gcd\big(({a\over d})^2,({b\over d})^2\big)=1\implies \gcd(a^2,b^2)=d^2$$ $\endgroup$ – Fermat Mar 21 '15 at 19:14
2
$\begingroup$

$\begin{align}(a,b)(a^2,b^2) =&\ (a^3,a^2b,ab^2,b^3)\quad [\text{by basic gcd laws - see Remark below}]\\ =&\ (a,b)^3\end{align}$

Thus $\ (a^2,b^2) = (a,b)^2\ $ by cancelling $\,(a,b) \neq 0.\ \ $ [See here for the cubic analog]


Or: Gauss's Lemma (GL) yields a slick proof. Let $\rm\:{\cal C}(f)\:$ denote the content of a polynomial, i.e. the gcd of its coefficients. Then GL $\rm\: \Rightarrow\ {\cal C}(f\:g) \color{#c00}{\overset{\rm GL_{\phantom |}\!}=}\ {\cal C}(f)\ {\cal C}(g)\ $ so

$$ (a,b)^2\! =\ {\cal C}\:(ax\! +\! b)\ {\cal C}\:(a x\! -\! b)\, \color{#c00}{\overset{\rm GL_{\phantom |}\!}=}\, {\cal C}\:((a x\! +\! b)(ax\! -\! b))\, =\, {\cal C}\:(a^2 x^2\! -\! b^2)\, =\, (a^2,b^2)\qquad$$


Replying to comments, we used only basic gcd laws (associative & commutative & distributive), e.g. let's do the gcd analog of the binomial theorem (in detail)

$\ (a,b)^2\! = (a,b)(a,b) = ((a,b)a,(a,b)b) = ((a^2,ba),(ab,b^2)) = (a^2,ba,ab,b^2) = (a^2,ab,b^2)$

Similarly $\,(a,b)^3 = (a,b)(a,b)^2 = (a,b)(a^2,ab,b^2) =\,\cdots\, = (a^3,a^2b,ab^2,b^3)$

By induction $\ (a,b)^n = (a^n, a^{n-1}b,\cdots\,ab^{n-1},b^n)\ $ is straightforwardly proved.

Such gcd arithmetic requires no ingenuity, it is analogous to multiplying polynomials.

The proof generalizes to the Freshman' Dream $\,(a,b)^n = (a^n,b^n)\,$ for gcds and invertible ideals.

$\endgroup$
  • 1
    $\begingroup$ How is $(a^3,a^2b,ab^2,b^3)=(a,b)^3$ any more obvious than $(a^2,b^2)=(a,b)^2$? $\endgroup$ – Barry Cipra Mar 21 '15 at 19:05
  • $\begingroup$ @Barry It's just gcd binomial expansion using basic gcd laws (associative, commutative, distributive). The latter is not "obvious" since $\,(a,b)^2 = (a^2,ab,b^2).\,$ It requires proof to show it equals $\,(a^2,b^2).\ \ $ $\endgroup$ – Bill Dubuque Mar 21 '15 at 19:11
  • $\begingroup$ Ah, thanks! I was just being stoneheaded. $\endgroup$ – Barry Cipra Mar 21 '15 at 19:16
  • 1
    $\begingroup$ But isn't it a theorem (or lemma, if you like) in its own right that $(a,b)(c,d)=(ac,ad,bc,bd)$? It's easy enough to show, based purely on the definition of greatest common divisor, that $(a,b)(c,d)$ divides $(ac,ad,bc,bd)$. But showing the other direction, it seems to me, requires additional work. $\endgroup$ – Barry Cipra Mar 21 '15 at 20:09
  • 1
    $\begingroup$ Bill, many thanks for the additional replies. I agree, it's all ultimately trivial gcd arithmetic, but that's sort of my point: We don't know which, if any, of these easily proved points the OP has at his or her disposal. $\endgroup$ – Barry Cipra Mar 21 '15 at 20:40
1
$\begingroup$

I'll use the notation of Michael's answer.

Since $g_2\mid a^2$, $g_2\mid b^2$, $g_1\mid a$ and $g_1\mid b$, there are integers $p,q,r,s$ such that:

$$a^2 = g_2p, \ b^2=g_2q, \ a=g_1r, \ b=g_1s \ ,$$

with $gcd(p,q)=1$ and $gcd(r,s)=1$. Manipulating those expressions, is easy to get that $r^2q=s^2p$ and, by Euclid's lemma, $r^2\mid p$ and $p\mid r^2$ thus $p=r^2$ (assuming positive integers), similarly, $q=s^2$ so finally

$$g_1^2 = \frac{a^2}{r^2}=\frac{g_2p}{r^2} = g_2$$

Here I use that if $gcd(r,s)=1$, then $gcd(r^2,s^2)=1$. This is much easier to prove than the general case so my reasoning is not circular.

$\endgroup$
0
$\begingroup$

Hint (for the easy direction): Suppose that $g_1=\gcd(a,b)$ and $g_2=\gcd(a^2,b^2)$. Since $g_1\mid a$ and $g_1\mid b$, then $g_1^2\mid a^2$ and $g_1^2\mid b^2$. Therefore, by the definition of the greatest common divisor, $g_1^2\mid g_2$.

$\endgroup$

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.