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!
How can I prove that $\gcd(a,b)=1\implies \gcd(a^2,b^2)=1$ without using prime decomposition?
-
21Is 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? – 2011-10-25
-
0@user7530, this only shows that $gcd(a^2,b)=1$. But Greg's hint to cube it worked for me. – 2011-10-25
-
14@Dan Brumleve: user7530's hint applied twice (first for a, then for b) works too. – 2011-10-25
-
0@user7530 +1 - Your comment is the best answer. – 2011-10-25
4 Answers
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$.
-
0+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. – 2011-10-25
-
0That 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. – 2011-10-25
-
0See my answer for a more concise way of viewing this - which generalizes widely. – 2011-10-26
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:
- $d \vert x$ and $d \vert y$ (ie $d$ is a common divisor of $x$ and $y$), and
- For all $d'\in M$ with $d'\vert x$ and $d' \vert y$, we have $d' \vert 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\vert bc$, we have $a \vert 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 \vert a$ and $\beta \vert b$, hence $\beta$ is invertible in $M$, $a=gcd(a,c)$, and $a \vert 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 \vert \alpha b^2$. By the proposition above, $a \vert \alpha$, and it follows that $x \vert a$. By a symmetric argument, $x \vert 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.
-
0Downvoter: Care to explain? – 2012-04-11
Hint $\rm\,\ (a,b)\ (a^2,b^2)\, =\, (a,b)^3\!,\ $ true since both sides $\rm\: =\: (a^3,\:a^2\:b,\:a\:b^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, also is provable by cancelling $\rm\,(a,b)^2$ to reduce to the case $\rm\,\,(a,b)=1\,$ (the OP). $ $ Then applying 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. a 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$$
A more general approach is my prior post on the Freshman's Dream $\rm\:(a,b)^n = (a^n,b^n),\,$ where I give a unified proof for arithmetic of GCDs and invertible ideals using simple arithmetic laws.
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$,