How can I prove that $\gcd(a,b)=1\implies \gcd(a^2,b^2)=1$ without using prime decomposition?
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$.
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 \mid x$ and $d \mid y$ (ie $d$ is a common divisor of $x$ and $y$), and
- 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.
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.