# Prove that if $n=ab$, $a$ and $b$ are positive integers, then $a \leq \sqrt{n}$ or $b \leq \sqrt{n}$

Prove that if $n=ab$, $a$ and $b$ are positive integers, then $a \leq \sqrt{n}$ or $b \leq \sqrt{n}$

1. Method chosen: Proof by contradiction.

2. suppose $n=ab$, $a$ and $b$ are positive integers, then $a>\sqrt{n}$ and $b>\sqrt{n}$

3. Let $n=30$ and $a=5$, $b=6$.

4. $5 >\sqrt{30}$ and $6>\sqrt{30}$.

5. Contradiction, $5 > \sqrt{30}$ is false.

6. Therefore it is not the case $a>\sqrt{n}$ and $b>\sqrt{n}$, so it is true that $a \leq \sqrt{n}$ or $b \leq \sqrt{n}$

Did I do this right? Any help would be appreciated.

-
You only proved that $5\times 6$ is 30 and that $5$ is not greater than $\sqrt{30}$. This is a far cry from every showing that every factorization of $30$ has the desired property, let alone the general case of any $n$, which is what you are supposed to prove. –  Arturo Magidin May 23 '12 at 2:07

No, you've only disproved one very specific possible counterexample. A bona fide proof by contra-diction disproves every possible counterexample. I would first establish some machinery:

• If $u>0$ and $v>0$ then $uv>0$.
• If $u>v>0$ and $w>0$ then $(u-v)>0,w>0\implies (u-v)w>0$, hence $uw>vw$.
• If $u>v>0$ and $w>x>0$ then $uw>vw>0$ and $wv>xv>0$ hence $uw>xv>0$.

This establishes that inequalities can be multiplied together, so long as we pay attention to signs and the symbols. In particular, $a>\sqrt{n}$ and $b>\sqrt{n}$ imply $ab>n$, contradicting our hypothesis $n=ab$.

Hence it cannot be the case that both of $a,b$ are strictly greater than $\sqrt{n}$. The logical negation of this proposition is that at least one of $a,b$ are less than or equal to $\sqrt{n}$.

-

You need to show it more generally than just for n=30.

from 2 on:

3) Then $$n = ab > \left( \sqrt{n}\right)^2$$ 4) This implies that $$n>n$$ which is a contradiction. Thus the assumption that $a > \sqrt{n}$ AND $b>\sqrt{n}$ is false.

Alternatively you could go about it by saying that a and b are the smallest possible values greater than n since they are both integers each would be n+1.

$$n \neq (n+1)^2$$

Small Changes 2) instead of "then" -> "and" (your not coming to a conclusion your stating an assumption/condition)

-
He didn't even prove it for $n=30$; he only proved it for $n=30$, $a=5$, and $b=6$. –  Arturo Magidin May 23 '12 at 2:07