# 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.)

-
In $\mathbb Z/4\mathbb Z$ we have $0^2|2^2$ but $0 \nmid 2$. So any proof that works for $\mathbb Z$ must use some property that $\mathbb Z/4\mathbb Z$ does not have. – marlu Jan 24 '13 at 21:10

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!]

-
Yes, that's fine, it's essentially the same as the alternative proof I gave. – Math Gems Jan 24 '13 at 23:12
Thanks, Math Gems; I was a bit worried I didn't stick to the OP's requirements. +1 on your answer, which gave the right name Euclid's Lemma to the essential step (I had forgotten what that was called). – coffeemath Jan 24 '13 at 23:25
This is more the level of detail I'm hoping to leave for posterity. Fix the edit so the logical implication makes sense and I'll accept it (am I right that currently it looks like you proved $gcd(a^2,b)=1$ implies $gcd(a,b)=1$, not the converse which you need? Or am I again missing something? $ax+by=1$ doesn't universally mean that $x$ can be a multiple of $a$...). – kcrisman Jan 25 '13 at 2:50
I.e. I guess we need that if $gcd(a,b)=1$ then $ax+by=1=a\cdot 1 \cdot x +by=1$ so that $a(ax+by)x+by=1$ or $a^2 x^2+b(ayx+y)=1$, which as you point out is $\iff gcd(a^2,b)=1$. – kcrisman Jan 25 '13 at 3:09
Oops. I did go the wrong way and showed $\gcd(a^2,b)=1$ implies $gcd(a,b)=1$. It looks like your last comment is the proof, same one I obtained working on a solution set for a number theory class I taught a few years back! Will fix. Thanks. – coffeemath Jan 25 '13 at 8:53

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.

-
I like the great generality, though I have to say that I am glad I didn't encounter all these different types of domains when they could have distracted me... cool theorem about the class group. – kcrisman Jan 25 '13 at 2:48