# If $b^2$ is the largest square divisor of $n$ and $a^2 \mid n$, then $a \mid b$.

I am trying to prove this:

$n$, $a$ and $b$ are positive integers. If $b^2$ is the largest square divisor of $n$ and $a^2 \mid n$, then $a \mid b$.

I want to prove this by contradiction, and I don't want to go via the fundamental theorem of arithmetic to do the contradiction. Can I prove this purely from properties of divisibility and GCD?

Since $b^2$ is the largest square divisor of $n$,

$$a^2 \le b^2 \implies a \le b.$$

Let us assume that $a \nmid b$. Now, I want to arrive at the fact that there is a positive integer $c$ such that $c > b$ and $c^2 \mid n$. This will be a contradiction to the assumption that $b^2$ is the largest square divisor of $n$.

How can I do this?

-
Hint: if $a^2$ and $b^2$ both divide $n$, then so does their least common multiple. Show this is a square $c^2$ with $c > b$. –  Michael Kasa May 2 '12 at 3:57
@MichaelKasa I am trying to use the properties of divisibility and GCD only. The concept of least common multiple has not been introduced yet in the book, so I want to limit myself to these properties only. –  Lone Learner May 2 '12 at 4:02
The least common multiple of $x$ and $y$ is their product divided by their gcd. So you can say that $a^2 b^2 / g^2$ divides $n$, where $g$ is the gcd of $a$ and $b$. If $a$ doesn't divide $b$, then $g < a$ and $ab/g > b$, a contradiction. –  Michael Kasa May 2 '12 at 4:08
@Michael Your prior comment seems to assume $\rm\:(a^2,b^2) = (a,b)^2.\:$ How do you justify that? Also, how do you propose to prove $\rm\:lcm(a^2,b^2) = c^2\:$ without using FTA? –  Bill Dubuque May 2 '12 at 6:44
Note $\$ This is a subproblem of the OP's prior question. See also this meta-question about its reopening. –  Bill Dubuque May 2 '12 at 19:16

Hint $\$ Suppose $\rm\:A^2\:|\:B^2C,\:$ and $\rm\:C\:$ is squarefree. Cancel $\rm\:(A,B)^2\:$ to get $\rm\:a^2\:|\:b^2 C,\ (a,b)=1.\:$ Hence $\rm\:a^2\:|\:C\:$ by Euclid's Lemma. But $\rm\:C\:$ is squarefree, so $\rm\:a=1,\:$ so $\rm\:A = (A,B),\:$ i.e. $\rm\:A\:|\:B.$

Remark $\$ Above is $(1\Rightarrow 2)$ in the $5$ characterizations of squarefree that I gave here.

The Bezout-based proof in Brett's answer can be expressed more concisely as follows: $$\rm a^2\:|\:b^2c\:\Rightarrow\:a^2\:|\:(bc)^2\:\Rightarrow\: a\:|\:bc\Rightarrow\: a^2\:|\:a^2c,abc,b^2c\:\Rightarrow\: a^2\:|\:(a,b)^2c\:\Rightarrow\: (a/(a,b))^2\:|\:c$$

-
In case it's is unfamiliar to the OP, I'll mention that $(a,b)$ is another notation for $\gcd(a,b)$. –  Brian M. Scott May 2 '12 at 4:39
Note $\rm\: a = A/(A,B),\ b = B/(A,B)\:$ to be explicit. –  Bill Dubuque May 2 '12 at 4:46
@BillDubuque Recommend the long line to be split as \begin{align*} a^2 | b^2c \Rightarrow a^2 | (bc)^2 &\Rightarrow a^2 | a^2c, abc, b^2c \\ &\Rightarrow a^2 | (a,b)^2c \Rightarrow (a/(a,b))^2 | c \end{align*} My +1 for this answer. –  Kirthi Raman May 6 '12 at 13:56

Suppose that $n=ka^2=mb^2$. If $d=\gcd(a,b)$, we can divide through by $d^2$ to get an equation $n'=ka'^2=mb'^2$ with $\gcd(a',b')=1$, and clearly $a\mid b$ iff $a'\mid b'$ iff $a'=1$, so we might as well assume from the start that $\gcd(a,b)=1$ and try to show that $a=1$.

Write $b=aq+r$ with $0\le r<a$, and note that $\gcd(a,r)=1$. Then $$ka^2=mb^2=m(aq+r)^2=mq^2a^2+2mqra+mr^2\;,$$ so $a^2\mid 2mqa+mr^2$, and in particular $a\mid mr^2$. Since $\gcd(a,r)=1$, $a\mid m$; let $m'=m/a$. Then $a\mid 2m'qa+m'r^2$, so $a\mid m'r^2$, and $a\mid m'$. Thus, $a^2\mid m$, and hence $(ab)^2\mid n$. The choice of $b$ now implies that $a=1$, as desired.

-

if you want to do it by contradiction starting with supposing $b^2$ is the largest square divisor of $n$, $a^2|n$ and $a \nmid b$. Then let $c=\frac{a}{gcd(a,b)}$. Since $a \nmid b$ we know that $a \neq b$ so $c>1$. Now, we can say that $c|a \implies c^2|a^2 \implies c^2|n$. Also, since $c$ and $b$ are relatively prime (by how we defined $c$), we can say $n=xb^2c^2=x(bc)^2$ since we are dealing in positive integers, it follows that $b < bc \implies b^2 < (bc)^2$ thus we have a contradiction.

${\bf Note:}$ You must divide out the gcd of a and b before multiplying to ensure they are relatively prime, otherwise you run the risk of getting a number larger than the original $b$ For example, say we have the number $2^23^25^2=900$ so I can say $15^2|900$ and $6^2|900$ but $900\neq 15^26^2x$ where $x$ is an integer

-
That's precisely the same as the first proof I gave, except it's by contradiction. –  Bill Dubuque May 2 '12 at 6:52
as stated in the question "I want to prove this by contradiction" –  Joseph May 2 '12 at 7:03
But any proof can trivially be turned into a proof by contradiction, viz. just as you did, i.e. preface it by the negation of the result. This does not count as a new proof. –  Bill Dubuque May 2 '12 at 12:40

Let $\operatorname{lcm}(a,b)=\frac{ab}{\gcd(a,b)}$. Since the $\gcd$ divides both $a$ and $b$, it's clear from the definition that the $\operatorname{lcm}$ is an integer divisible by both $a$ and $b$. And if $a$ does not divide $b$, then the $\operatorname{lcm}$ is strictly greater than $b$, since $a\neq \gcd(a,b)$. By this question, the squareroot of an integer is either an integer or irrational, so since $a^2b^2|n^2$, $ab|n$.

Pick $x$ and $y$ so that $ax+by=\gcd(a,b)$. Then $\frac{n}{(\operatorname{lcm}(a,b))^2}=\frac{n}{a^2b^2}\cdot (ax+by)^2=\frac{n}{a^2b^2}\cdot (a^2x^2+2abxy+b^2c^2)=\frac{nx^2}{b^2}+\frac{2nxy}{ab}+\frac{ny^2}{a^2}$ is an integer.

-
This sort of thing makes you really appreciate the fundamental theorem! –  Brett Frankel May 2 '12 at 4:24
I may be missing something obvious, but it seems to me that you need to do a bit of work to justify the step from $a^2b^2\mid n^2$ to $ab\mid n$ in the absence of the fundamental theorem. –  Brian M. Scott May 2 '12 at 4:45
@BrianM.Scott Yeah, I was hung up on that too for a bit. But the OP posted this question: math.stackexchange.com/questions/139737/… from which you can deduce that the squareroot of an integer is either an integer or irrational, which does the trick. –  Brett Frankel May 2 '12 at 5:02
It occurred to me after I commented that you might had that in mind, but it's probably good that we've now made it explicit. –  Brian M. Scott May 2 '12 at 5:05