I want to prove: $$\text{If }\gcd(a,b)=1\text{ and }ab=n^2,\text{ then }a,b\text{ are also perfect squares.}$$ 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.)

  • 2
    $\begingroup$ See my answer here which uses only properties of gcds. Note the in $\Bbb Z$ (or any domain where nonzero nonunits factor into irreducibles), the existence of gcds is equivalent to uniqueness of factorization into irreducibles, since it easily implies that irreducibles are prime. $\endgroup$ – Math Gems Jan 24 '13 at 20:10
  • $\begingroup$ A very related question: Let $R$ be a Bezout domain. If $a,b$ are coprime and $ab$ is a square, does it follow that $a,b$ are squares ? $\endgroup$ – Amr Jan 24 '13 at 20:21
  • $\begingroup$ @Amr Yes, Bezout domains are gcd domains, so the above-linked proof works. $\endgroup$ – Math Gems Jan 24 '13 at 20:24
  • $\begingroup$ @MathGems Yes I know. I was just telling the OP that this may be a better way to ask the question $\endgroup$ – Amr Jan 24 '13 at 20:32
  • $\begingroup$ @MathGems - nice, yes you are right about this. Maybe I should just be asking about Bezout domains instead - haven't thought about the tower of domains in years, thanks. I up-voted MathGems' earlier answer, best I could do here. $\endgroup$ – kcrisman Jan 24 '13 at 20:58

According to this meta question and this meta answer, I will post @MathGems answer here as community wiki just so it's easier to find. (If they return they can post and I'll delete this.)Directly quoted:

Alternatively, and more generally, one can use gcds to explicitly show $\rm\:a,b\:$ are squares. Writing $\,\rm(m,n,\ldots)\:$ for $\rm\: gcd(m,n,\ldots)$ we have:

Theorem $\rm\ \ \color{#C00}{c^2 = ab}\, \Rightarrow\ a = (a,c)^2,\ b = (b,c)^2\: $ if $\rm\ \color{#0A0}{(a,b,c)} = 1\ $ and $\rm\:a,b,c\in \mathbb N$

Proof $\rm\ \ \ \ (a,c)^2 =\: (a^2,\color{#C00}{c^2},ac)\: =\: (a^2,\color{#C00}{ab},ac)\: =\: a\,\color{#0A0}{(a,b,c)} = a.\: $ Similarly $\rm \,(b,c)^2 = b.\ \ $ QED

Yours is the special case $\rm\:(a,b) = 1\ (\Rightarrow\ (a,b,c) = 1)$. The above proof uses only universal gcd laws (associative, commutative, distributive), so it generalizes to any gcd domain/monoid (where, generally, prime factorizations need not exist, hence the above proof is more general).

  • $\begingroup$ It is clear that if $x$ divides $a$ and $c$ then $x^2$ divides each of $a^2,c^2, ac$. So $(a,c)^2\leq (a^2,c^2,ac).$ But how do you show the reverse inequality? And how do you show the second inequality in the proof? $\endgroup$ – DanielWainfleet Sep 21 '16 at 2:47
  • $\begingroup$ I think this is general property of gcd "arithmetic" (an exercise in some texts?); recall that I'm just copying another answer here for reference. $\endgroup$ – kcrisman Sep 21 '16 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.