First, let \(d=\gcd(a,z)\). Then we can write \(z^2=a^2 \cdot k\) for some integer \(k\), and immediately write \begin{equation*}(z')^2 d^2=(a')^2 d^2 k\end{equation*} for some integers \(z'\) and \(a'\), by definition of gcd. (That is, \(z=z'd\) and \(a=a'd\).)

Cancelling the \(d^2\) (yes, we do assume this property of integers) yields \begin{equation*}(z')^2=(a')^2 k\; .\end{equation*} Since \(\gcd(a',z')=1\), we have \(a'x+z'y=1\) for some \(x,y\in\mathbb{Z}\); now we substitute for \(1\) in \(a'\cdot 1\cdot x\) (!) to get \begin{equation*}a'(a' x+z'y)x+z'y=1\end{equation*}

Now we have that \(a'^2 x+z'(a'xy+y)=1\), so that \(\gcd((a')^2,z')=1\) as well. But of course \(a'\mid (z')^2\). Clearly if a positive number is a divisor, but their greatest common divisor is 1, then that number is going to have to be 1 by definition of divisors. So \(a'=1\). (If \(a'\) was negative, the same argument for \(-a'\) shows \(-a'=1\), so really \(a'=\pm 1\).)

Hence \(a=a'd=\pm d\), which is a divisor of \(z\), we have the desired result.

First, we will need a general fact about gcds: \begin{equation*}\gcd(x,y)^2=\gcd(x^2,xy,y^2)\end{equation*} See Exercise 3.6.14.

We know that \(1=\gcd(m,n)=\gcd(m,n,j)\), so \begin{equation*}m = m\cdot \gcd(m,n,j)=\gcd(m^2,mn,mj)=\gcd(m^2,j^2,mj)\end{equation*} Now we use the fact, so that \begin{equation*}m=\gcd(m,j)^2\end{equation*}. That's a perfect square.

The same argument with \(n\) and \(j\) yields \(n = \gcd(n,j)^2\).