6
$\begingroup$

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?

  • 0
    **Note** $\ $ This is$a$subproblem of the OP's [prior question.](http://math.stackexchange.com/q/139737/242) See also this [meta-question](http://meta.math.stackexchange.com/q/4095/242) about its reopening.2012-05-02

4 Answers 4

6

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$

  • 0
    @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.2012-05-06
2

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, 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.

2

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

  • 1
    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.2012-05-02
1

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.

  • 1
    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.2012-05-02