How can I prove that $\gcd(a,b)=1\implies \gcd(a^2,b^2)=1$ without using prime decomposition?

Question

How can I prove that if $\gcd(a,b)=1$, then $\gcd(a^2,b^2)=1$, without using prime decomposition? I should only use definition of gcd, division algorithm, Euclidean algorithm and corollaries to those. Thanks for your help!

Answer 1

The golden rule for all problems about greatest common divisors, I claim (especially if you're specifically trying to avoid using prime decomposition), is the fact that $\gcd(a,b)$ is equal to the smallest positive integer $g$ that can be written in the form $g=ax+by$ with $x,y$ integers.

In particular, $\gcd(a,b)=1$ if and only if there exist integers $x$ and $y$ such that $ax+by=1$. (This is not true with 1 replaced by a larger integer! It's true because 1 is the smallest positive integer there is.)

That's my general hint; my specific hint is to cube both sides of the equation $ax+by=1$.

Answer 2

This can actually be done in a strictly multiplicative structure, in which we might not have (or care about) addition. In particular, let $M$ be a commutative cancellative monoid under the operation $\cdot$. In other words, for all $x,y,z\in M$, $x\cdot y = y\cdot x$ and if $x \cdot y=x \cdot z$ then $y=z$. As is customary, from now on we'll write $xy$ instead of $x \cdot y$.

So, for $x,y\in M$, we say that $d\in M$ is a greatest common divisor of $x$ and $y$ if:

1. $d \mid x$ and $d \mid y$ (ie $d$ is a common divisor of $x$ and $y$), and
2. For all $d'\in M$ with $d'\mid x$ and $d' \mid y$, we have $d' \mid d$.

It is easy to prove that greatest common divisors are unique up to unit multiples (ie if $d_1$ and $d_2$ are greatest common divisors of $x$ and $y$, then there exists an invertible element $u\in M$ such that $x=uy$).* With this caveat in mind, we'll use the notation $d=\gcd(x,y)$ to mean that $d$ is a greatest common divisor of $x$ and $y$. Of course, saying $\gcd(x,y)=1$ really means that the only common divisors of $x$ and $y$ are units of $M$.

We say that $M$ is a GCD-monoid if every pair of elements in $M$ have a greatest common divisor.

So, with this definition (which reduces to Greg Martin's definition above in the case when we consider $M=\mathbb{Z}\setminus\{0\}$ under multiplication), we first prove the following proposition.

Proposition: Let $M$ be a GCD-monoid and $a,b\in M$ with $\gcd(a,b)=1$. Then, for any $c\in M$ with $a\mid bc$, we have $a \mid c$.

Sketch of proof: We have $a\alpha =bc$ for some $\alpha\in M$. Since $M$ is a GCD-monoid, let $d:=\gcd(b,\alpha)$. Then,

$ad=\gcd(ab,a\alpha)=\gcd(ab,bc)=\gcd(a,c)b$. However, since $d \beta =b$ for some $\beta\in M$, we have $\beta \mid a$ and $\beta \mid b$, hence $\beta$ is invertible in $M$, $a=\gcd(a,c)$, and $a \mid c$. $\blacksquare$

(Note that I technically used the result that $x \cdot \gcd(y,z)=\gcd(xy,xz)$, but that can also be proved using the definition of gcd above.)

So, assume $\gcd(a,b)=1$ and suppose we have a common divisor $x$ of $a^2$ and $b^2$. So, $x\alpha=a^2$ and $x\beta=b^2$ for some $\alpha,\beta\in M$. Then,

$x\alpha \beta = \beta a^2 = \alpha b^2$

whence $a \mid \alpha b^2$. By the proposition above, $a \mid \alpha$, and it follows that $x \mid a$. By a symmetric argument, $x \mid b$. Therefore $x$ is an invertible element in $M$ and $\gcd(a^2,b^2)=1$.

In fact, you can use the same argument (with a bit more care) to show that $\gcd(a^m,b^n)=1$ for all $m,n\in \mathbb{N}$.

* - In the integers, the usual convention is to sidestep this by restricting greatest common divisors to be positive. However, there are plenty of algebraic structures where there are more than two invertible elements. In practice, the distinctions made amongst unit multiples of an element are often ignored.

Answer 3

Below are sketches of four proofs. Note: proofs cubing the Bezout gcd equation are a special case of the first proof below - which works more generally, e.g. in $\,\Bbb Z[x],\ \Bbb Q[x,y]$ - see "Beware" below.

---

Hint $\rm\,\ \color{#c00}{(a,b)} (a^2,b^2) = \color{#c00}{(a,b)}^3,\, $ true since both sides $\rm\: =\: (a^3,\,a^2b,\,ab^2,\,b^3)\, $ by applying basic gcd laws (distributive, commutative, associative), cf. here. Cancelling $\,\rm \color{#c00}{(a,b)}\ne 0\,$ from both sides of above yields $\rm\, (a^2,b^2) = (a,b)^2.\,$ OP is special case $\,\rm (a,b)= 1.\,$

---

Or $\rm\, (a^2,b^2) = (a,b)^2,\,$ a gcd Freshman's Dream, is provable by cancelling $\rm\,(a,b)^2\,$ to reduce to case $\rm\,\,(a,b)=1\,$ (OP). $ $ Then Euclid's Lemma, i.e. $\rm\,(x,y)=1=(x,z)\,\Rightarrow\,(x,yz)=1,\,$ yields $\rm\,(a,b)=1\,\Rightarrow\,(a,b^2)=1\,\Rightarrow\,(a^2,b^2)=1\,$ (or we can prove it locally, i.e. one prime at a time: $ $ prime $\rm\,p\mid a^2,b^2\,\Rightarrow\,p\mid a,b,\,$ contra $\rm\,(a,b)=1)$.

---

Or Gauss's Lemma (GL) yields a quick proof. Let $\rm\:{\cal C}(f)\:$ denote the content of a polynomial, i.e. the gcd of its coefficients. GL $\rm\: \Rightarrow\ {\cal C}(f\:g)\ =\ {\cal C}(f)\ {\cal C}(g)\ $ so

$$\rm (a,b)^2\! =\ {\cal C}\:(ax\! +\! b)\ {\cal C}\:(a x\! -\! b)\, =\, {\cal C}\:((a x\! +\! b)(ax\! -\! b))\, =\, {\cal C}\:(a^2 x^2\! -\! b^2)\, =\, (a^2,b^2)\qquad$$

---

More generally here the Freshman's Dream $\rm\:(a,b)^n = (a^n,b^n),\,$ has a unified proof for arithmetic of GCDs and cancellable ideals using basic arithmetic laws (as in first proof above)

Beware The first $2$ proofs above work in every gcd domain (domains where all gcds $\:\!(a,b)\:\!$ exist), but common proofs in $\,\Bbb Z\,$ via Bezout fail to generalize to familiar UFDs like $\,\Bbb Z[x],\, \Bbb Q[x,y]\,$ where gcds generally do not have linear (Bezout) form, e.g. in $\,\Bbb Q[x,y]\,$ we have $\,(x,y) = 1\,$ but this gcd is not of Bezout form, else $\,x\:\!g(x,y) + y\:\! f(x,y) = 1,\,$ so eval at $\,x = y = 0\,$ yields $\,0 = 1.\,$ Ditto for $(2,x)$ in $\,\Bbb Z[x]$.

Answer 4

I think you can use the following property to show $\gcd(a^{2},b^{2})=1$ if $\gcd(a,b)=1$.
$\gcd(a,b)=1$ and $\gcd(a,c)=1$ then $\gcd(a,bc)=1$. Note that from this you can also see that $\gcd(a^{n},b^{n})=1$,