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

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

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

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

• Please explain in details. – user1942348 Mar 21 '15 at 18:40
• 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. – Ibrahim Tencer Mar 21 '15 at 21:06

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.

• 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! – Fermat Mar 21 '15 at 18:58
• As $$\gcd(a,b)=d\iff \gcd({a\over d},{b\over d})=1$$ – Fermat Mar 21 '15 at 19:02
• Yeah we can add that line – AgentS Mar 21 '15 at 19:04
• It seems to me there's a tacit lemma lurking in the background here: If $(r,s)=(r,t)=1$, then $(r,st)=1$. – Barry Cipra Mar 21 '15 at 19:08
• 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$$ – Fermat Mar 21 '15 at 19:14

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

• How is $(a^3,a^2b,ab^2,b^3)=(a,b)^3$ any more obvious than $(a^2,b^2)=(a,b)^2$? – Barry Cipra Mar 21 '15 at 19:05
• @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).\ \$ – Bill Dubuque Mar 21 '15 at 19:11
• Ah, thanks! I was just being stoneheaded. – Barry Cipra Mar 21 '15 at 19:16
• 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. – Barry Cipra Mar 21 '15 at 20:09
• 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. – Barry Cipra Mar 21 '15 at 20:40

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.

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