# Understanding this proof by contradiction

Let $c$ be a positive integer that is not prime. Show that there is some positive integer $b$ such that $b \mid c$ and $b \leq \sqrt{c}$.

I know this can be proved by contradiction, but I'm not sure how to approach it. Usually I write the proof in the form $P \rightarrow Q$, and then if we can prove $P \land \neg Q$ is false, $P \rightarrow Q$ must be true.

In this case, I wrote it as:

If $c$ is a composite, positive integer, then $b \mid c$ and $b \leq \sqrt{c}$, for some positive integer $b$.

I'm guessing that as long as I assume that $b \nmid c$ or $b > \sqrt{c}$, then this is still valid as $\neg Q$; that is, I don't have to assume the converse of both parts of $Q$?

Moving on, if $b > \sqrt{c}$, and $b \mid c$, then $br=c$ for some integer $r$, which means $r < \sqrt{c}$.

And this is where I get stuck.

-
Isn't b = 1 an obvious solution...? –  KennyTM Sep 13 '10 at 17:51
@Kenny: The main question is in trying to prove by contradiction, not the actual result. –  Aryabhata Sep 13 '10 at 18:02
@Moron: the problem is misstated. It should say that b is greater than 1. –  Qiaochu Yuan Sep 13 '10 at 18:05
@Qiaochu: Yes, but the way I see it, the question is mainly about getting a proof by contradiction. Whether the actual result is trivial or not is immaterial :-) –  Aryabhata Sep 13 '10 at 18:10
@Qiaochu: The book definitely says "b a positive integer", but no doubt a fault on the author's behalf. –  persepolis Sep 13 '10 at 18:44

When you negate statements with quantifiers, you need to flip the quantifiers. For example, the opposite of "every dog is black" is not "every dog is not black," but "there exists some dog which is not black."

In this case, the correct negation of "there exists some $b$ such that $b | c$ and $b \le \sqrt{c}$," if you want to keep the condition that $b$ is a divisor, is "for all $b$ such that $b | c$, $b > \sqrt{c}$." This is the statement from which you can prove a contradiction: for every $b$ that satisfies this condition, $\frac{c}{b}$ must also satisfy this condition, giving the contradiction $c > c$.

(And everywhere you want the condition that $b > 1$ or else the problem is trivial as KennyTM says in the comments.)

-
+1: For explaining in English! –  Aryabhata Sep 13 '10 at 18:02

What you want is to assume that every b that divides c is "too large" and derive a contradiction; however, you don't need proof by contradiction here at all. If b divides c and is too large, then it's easy to show directly that $c/b$ also divides c and is small enough.

This also can be phrased with contradiction: assume $c/b > \sqrt{c}$ and $b > \sqrt{c}$ then $c=(c/b)\cdot b > \sqrt{c}\cdot\sqrt{c}=c$ - contradiction.

-

I: That there exists some $b$ with $b|c$ is true by the definition (c is not prime).

Now we assume that - as II - there is no $b \leq \sqrt c$.

Since there has to be some $b$ due to I, this $b$ now has to meet $b > \sqrt c$.

Now $z = \frac{c}{b}$ surely is an integer that divides $c$ too, and, furthermore, $z \leq \sqrt c$. Therefore, by assuming II, we disprove II - Contradiction, q.e.d.

-