Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
2  
@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

4 Answers 4

up vote 6 down vote accepted

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$$

share|improve this answer
2  
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.

share|improve this answer

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

share|improve this answer
    
That's precisely the same as the first proof I gave, except it's by contradiction. –  Bill Dubuque May 2 '12 at 6:52
1  
as stated in the question "I want to prove this by contradiction" –  Joseph May 2 '12 at 7:03
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. –  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.

share|improve this answer
    
This sort of thing makes you really appreciate the fundamental theorem! –  Brett Frankel May 2 '12 at 4:24
1  
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
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. –  Brian M. Scott May 2 '12 at 5:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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