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.

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.

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

2 Answers 2

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

share|improve this answer

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)

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

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.