# Is it possible to prove $a^2\mid x$ and $b^2\mid x$ implies $ab\mid x$ without using canonical prime decomposition?

I want to prove the statement: If $a$, $b$, $x$ are integers with $ab\neq 0,$ and $a^2\mid x$, $b^2\mid x$, then $ab\mid x$. Here $u\mid v$ means that $u$ divides $v$. I know it is easy if using the canonical prime decomposition (i.e., the fundamental theorem of arithmetic). My question is, is it possible to prove it without using the canonical prime decomposition?

I have tried as follows: Let $g=\gcd(a,b)$ and suppose $a=g\alpha$, $b=g\beta$. Then $\gcd(\alpha,\beta)=1$, that is, $\alpha$ and $\beta$ are coprime. Moreover, $\alpha\beta\mid x$. But I do not know how to show $g^2\alpha\beta\mid x$, that is, $ab\mid x$.

Let $$\rm\ r = X/(AB).\,$$ Then $$\rm \,r^2 = \overbrace{(X/A^2)}^{\large \in\,\Bbb Z}\overbrace{(X/B^2)}^{\large \in\,\Bbb Z} =: n\in \Bbb Z\$$ so $$\ r\in\Bbb Z\$$ by

Theorem $$\ \ \ \rm r = \sqrt{n}\;\;$$ is integral if rational,  for $$\:\rm n\in\mathbb{N}$$

Proof $$\ \$$ Writing $$\rm\,\ r = a/b,\ \ \gcd(a,b) = 1\ \Rightarrow\ ad\!-\!bc \,=\, \color{#C00}{\bf 1}\;$$ for some $$\:\rm c,d \in \mathbb{Z}\$$ by Bezout.

$$\rm\color{#C00}{That\,}$$ and $$\rm\: r^2\! = \color{#0a0}{ n}\:\Rightarrow\ 0 \,=\, (a\!-\!br)\, (c\!+\!dr) \, =\, ac\!-\!bd\color{#0a0}{ n} \:+\: \color{#c00}{\bf 1}\cdot r,\$$ so $$\rm\ r = bdn\!-\!ac \in \mathbb{Z}$$

Remark  There are many ways to prove this Theorem going back to the ancient proofs of irrationality of $$\,\sqrt 2.\,$$ See this thread for many proofs. One can also use the Rational Root Test and variants, or descent on denominators, or principality of denominator ideals, e.g. here or here. There are over a handful of variants in my older posts on related topics.

• I found the use of $a$, $b$ in the proof confusing, because $a$ and $b$ are bound at the top of the post, where they have a different meaning. Maybe $s$ and $t$? Aug 17, 2017 at 3:49
• Good answer. I hadn't seen that $(a-br)(c+dr)$ trick before. Aug 17, 2017 at 4:26
• @Thomas Thanks. That idea was inspired by a proof of Dedekind. It generalizes to give a proof of the monic case of the Rational Root Test by reduction of degree - as I explain here. Aug 17, 2017 at 4:39
• @Bill Dubuque. Thank you very much. I've got it. But I think the following argument is easier: Now that $ad-bc=1,$ we have $a^2d-abc=a.$ Since $n=a^2/b^2,$ so $a^2=nb^2.$ Hence $a=a^2d-abc=nb^2d-abc,$ which implies that $b$ divides $a.$ Thus $r=a/b$ is integral.
– azc
Aug 17, 2017 at 4:42
• @azc There are various ways to arrange the algebra. I chose that one since it generalizes nicely, e.g. see the link in my reply to Thomas. Aug 17, 2017 at 4:49

Sure it's possible. Let $r$ be a rational number, and $r^2=n$ an integer. Then, $r$ must be an integer, too: if we assume $k<r<k+1$ for an integer $k$, and $m$ is the smallest positive integer so that $mr$ is integer, let's consider $m'=m(r-k)$: it's an integer $<m$, and $m'r=mn-k\cdot mr$ is integer, contradicting the minimality of $m$. So if the square root of an integer is rational, it must be integer. Now if $a^2|x$ and $b^2|x$, $$\frac{x}{a^2}\cdot\frac{x}{b^2}=\left(\frac{x}{ab}\right)^2$$ is an integer, so the rational number $\frac{x}{ab}$ must be an integer as well.

• That's one of the standard proofs by denominator descent (discussed more conceptually here).. See also the comparison between slow and fast descent in the Remark here. Aug 17, 2017 at 3:37

Ah, this is easy one.

Let $g=gcd(a,b)$, then tere are relatively prime $c, d$ such that $a=gc$ and $b=dg$.

Since $a^2|x$ we have $x=a^2\cdot t$. Thus $d^2g^2 |g^2c^2t$. So $d^2|c^2t$.

But $c,d$ are relatively prime so $d^2|t$. So $t = d^2\cdot s$ for some integer $s$ and now we have $x=a^2\cdot d^2\cdot s = ab cds$.

Other people have reduced the problem to a proof of:

Theorem: If $n^2\mid m^2$ then $n\mid m$.

There are lots of ways to prove this. I found what I think is a novel proof.

Proof: Let $d=\gcd(m,n).$ Then $d=mx+ny$ for some pair $x,y$. So $d^{2k+1}=(mx+ny)^{2k+1}$ for any integer $k\geq 0$. But the right side is divisible by $n^{2k}$, since each term in the expansion is a multiple of$m^{i}n^{2k+1-i}$ for some $i$. If $i=2j$ is even, then $n^{2j}\mid m^{2j}$, and $n^{2(k-j)}\mid n^{2k+1-2j}$. Likewise, for $i=2j+1$.

So this means that $d\mid n$ and $n^{2k}\mid d^{2k+1}$ for all $k$. This means that $\left(\frac nd\right)^{2k}\mid d$ for all $k$. If $d<n$, then $\frac{n}{d}>1$, so for some* $k$, $\left(\frac nd\right)^{2k}>d$, which is a contradiction.

So we must have $d=n$, and thus $n\mid m$.

This proof generalizes. If $n^a\mid m^a$ and $d=\gcd(m.n)=mx+ny$ then you can show that for all $k> 0$, $n^{ak}\mid d^{ak+a-1}$ for all $k$ and thus that $\left(\frac{n}{d}\right)^{ak}\mid d^{a-1}$ for all $k$, which means that $\left(\frac{n}{d}\right)^{ak}$ is bounded, so $n=d$ and $n\mid m$.

* (You can come up with the specific $k=d$. This is because $2^{2d}>2^d>d$ for all $d$, and (under the assumption) $\frac{n}{d}\geq 2$.)

You don't even need the full Bézout's identity, just some version of a division algorithm.

You do need:

Lemma: If $d<n$ then for infinitely many $k\in\mathbb N,$ we have that $d^{k+1}<n^k.$

From there, we can write $m=nq+d$, with $0\leq d<n.$ But if $d=0$ we are done. Otherwise, we have $d=m-nq,$ and we take the same tack, and get that $n^{ak}\mid d^{ak+a-1}$ for all $k$, which means that $(n^a)^k\leq (d^a)^{k+1}.$

An interesting example might be when $m,n\in R[x],$ where $R$ is some commutative ring with no nilpotents, and $n$ is monic. Then we can divide $m$ by $n$ and get a remainder $d$ of degree less than the degree of $n.$ Even though we might not get a full division algorithm in this ring, nor Bezout, but we can still conclude that if $n^a\mid m^a$ then $n\mid m.$

An alternative way of putting this is:

If $R$ is a commutative ring, and $m,n\in R[x]$ with $n$ monic and $n^a\mid m^a$ for some $a\geq 1$ then if $m=nq+d$ with $\deg(d)<\deg(n)$ then $d$ is nilpontent in $R[x].$

• I was just going to put in the extra edit that $n \mid m$. Aug 17, 2017 at 3:55