16
$\begingroup$

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!

$\endgroup$
5
  • 22
    $\begingroup$ Is this homework? Here's a hint: by Euclid's algorithm, $\gcd(a,b) = 1$ if and only if there exist integers $x$ and $y$ with $ax+by=1$. Then $(ax+by)^2 = a^2(x^2) + b(2axy + by^2) = 1$. What can you conclude? $\endgroup$
    – user7530
    Oct 25, 2011 at 8:13
  • $\begingroup$ @user7530, this only shows that $gcd(a^2,b)=1$. But Greg's hint to cube it worked for me. $\endgroup$ Oct 25, 2011 at 8:26
  • 14
    $\begingroup$ @Dan Brumleve: user7530's hint applied twice (first for a, then for b) works too. $\endgroup$
    – J. J.
    Oct 25, 2011 at 8:29
  • $\begingroup$ @user7530 +1 - Your comment is the best answer. $\endgroup$
    – GeoffDS
    Oct 25, 2011 at 20:41
  • $\begingroup$ Beware that SE tweeted this post so it got much wider than normal exposure. As usual, this means that earlier and more elementary answers have a much higher number of votes than they normally would due to drive-by voting. $\endgroup$ Jul 10, 2022 at 9:17

5 Answers 5

42
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ +1 Incidentally, I've yet to see a proof using unique prime factorization that doesn't become a lot more elegant when you use this fact instead. $\endgroup$
    – user7530
    Oct 25, 2011 at 8:22
  • $\begingroup$ That is really helpful, thanks! I hadn't thought of cubing the equation; now I can factor $a^2$ or $b^2$ out of every term and get the linear combination I needed. $\endgroup$
    – misi
    Oct 25, 2011 at 8:23
  • 3
    $\begingroup$ It is misleading to call this a "gcd golden rule" since it fails miserably in many common non-Bezout UFDs, e.g. $\,\Bbb Z[x],\ \Bbb Q[x,y].\,$ But the result holds true here and can be proved very simply and more generally without using prime factorizations but instead using basic gcd laws - see my answer. $\endgroup$ Jul 10, 2019 at 21:22
10
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Downvoter: Care to explain? $\endgroup$
    – user5137
    Apr 11, 2012 at 22:36
7
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

Let us assume for the sake of contradiction that $\gcd(a^{2},b^{2}) \neq 1$.

Then there exists an integer $c > 0$ such that $c \mid a^{2}$ and $c \mid b^{2}$.

Now, let $p$ be any prime factor of $c$.

Hence, $p \mid a^{2}$ and $p \mid b^{2}$.

Therefore, $p \mid a$ and $p \mid b$, contracting the assumption that $\gcd(a, b) = 1.$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .