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$
  • 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 '11 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$ – Dan Brumleve Oct 25 '11 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 '11 at 8:29
  • $\begingroup$ @user7530 +1 - Your comment is the best answer. $\endgroup$ – Graphth Oct 25 '11 at 20:41
39
$\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$
  • $\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 '11 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 '11 at 8:23
  • 2
    $\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$ – Bill Dubuque Jul 10 at 21:22
9
$\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$
  • $\begingroup$ Downvoter: Care to explain? $\endgroup$ – user5137 Apr 11 '12 at 22:36
4
$\begingroup$

Hint $\rm\,\ (a,b) (a^2,b^2) = (a,b)^3,\, $ true since both sides $\rm\: =\: (a^3,\:a^2b,\:ab^2,\:b^3)\, $ by employing basic gcd laws (distributive, commutative, associative). Cancelling $\,\rm (a,b)\ne 0\,$ from both sides of above yields that: $\rm\ (a^2,b^2) = (a,b)^2.\,$ Yours is the special case $\,\rm (a,b)= 1.\,$ See this answer further discussion on gcd arithmetic and its analogy with integer arithmetic.

Alternatively $\rm\, (a^2,b^2) = (a,b)^2,\,$ the 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, 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.$

Alternatively 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 invertible ideals using simple arithmetic laws.

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

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.