1
$\begingroup$

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.

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

3 Answers 3

5

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

2

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)

  • 0
    How does this answer change if it's by contrapositive?2017-09-17