Prove that if perfect squares divide each other, then so do the originals - without primes I want to prove: $$\text{If }a^2|z^2,\text{ then }a|z.$$  Assume everyone is a positive integer, etc.  Unless I'm deluding myself, this is pretty easy to show using unique prime factorization.
But I want to do it without using primes or the (usual statement of the) FTA.  That is, using coprime is fine, using the so-called Bezout identity (XGCD algorithm), etc. is fine.  Is this even possible without essentially defining at least irreducibles, if not primes and prime factorization, along the way?
(See here for a more vague question I asked a while ago on this.)
 A: Hint $\ $ If $\: (z/a)^2 = n\:$ then $\,z/a\,$ is a root of $\:x^2 - n\:$ so $\:z/a\in \Bbb Z\:$ by the rational root test (RRT). Domains satisfying the monic case of the RRT are called integrally-closed. They are a much wider class of domains than UFDs. For example, the usual proof of RRT uses only gcds, so any gcd domain is integrally-closed.
Alternatively, cancelling the gcd $\, (a,z)\,$ twice from $z^2/a^2$ reduces to the case where $(a,z) = 1.\:$ Now, by Euclid's Lemma $\:(a,z)=1\Rightarrow(a,z^2)=1,\,$ so $\:a\,|\,z^2\Rightarrow a = \pm 1,\,$ so $\:z/a\in\Bbb Z.$
If you desire to learn more about this specific property then try searching on root-closed domains. A domain D is called $n$ root-closed if for every fraction $x$ over D we have $\,x^n\in{\rm D}\Rightarrow x\in\rm D.\,$ If this holds for all $\,n\in \Bbb N\,$ then one calls D root-closed. One interesting result using this property is the following (which applies to rings of algebraic integers).
D is a Dedekind domain with torsion class-group $\iff$ D is root-closed and for every $\,\{a,b,\ldots\}\subset\rm D\,$ there is an $\,n\in\Bbb N\,$ such that the ideal $(a^n,b^n,\ldots)\,$ is principal. Domains that satisfy the latter ideal-theoretic property are sometimes called almost-PIDs or API domains.
A: Since Bezout is fair game, one can use that if $gcd(a,b)=1$ and $a|bc$ then $a|c$.
Now if $a^2|b^2$ we may first remove the gcd from $a,b$ and have then $gcd(a,b)=1.$ Pick $k$ with $a^2k=b^2$. Note that $gcd(b,a^2)=1$ and we have $b|a^2k$ [since $b \cdot b=a^2k$]
Therefore we have $b|k$ and can write $k=bk'$. Put this into $a^2k=b^2$ to get
$$a^2\cdot bk'=b^2,$$
then we have $a^2k'=b$, so that $a \cdot (ak')=b$, i.e. $a|b$.
Not sure if the use of Bezout needs to be flushed out some, but I think that's all I used.
EDIT: At one point I used that $gcd(a,b)=1$ implies $gcd(a^2,b)=1$ This is OK since Bezout works both ways, that is $gcd(a,b)=1$ if and only if there are integers $x,y$ with $ax+by=1$. So from $gcd(a,b)=1$ there are $x,y$ with $ax+by=1$, so $a(ax+by)x+by=1$, and multiplying out we have $a^2x+abxy+by=1$ and then factoring $b$ out of the second two terms gives $a^2x+b(axy+y)=1.$ So by reverse Bezout we arrive at $gcd(a^2,b)=1.$
[Thanks to kcrisman for pointing out I originally had shown the converse of the desired implication!]
