Proof by contradiction concerning prime numbers. Where is the contradiction?

Question

Statement to be proved:

Prove that if $n > 1$ is not divisible by any prime number $p$ where $p \le \sqrt{n}$ then $n$ is a prime number.

Suppose we assume that $n$ is composite. We then prove that $n$ is divisible by a prime number $\le \sqrt{n}$.

We proved that a composite number is divisible by a prime number $\le \sqrt{n}$. Can we fairly deduce from this that a prime number is not divisible by a number $\le \sqrt{n}$? I doubt this. As far as this proof is concerned, for all we know, both composite and prime numbers could be divisible by a prime number $\le \sqrt{n}$. Where is the contradiction?

Answer 1

Your question really concerns the logic of contrapositives. You are proving that a sufficient condition for $n$ to be prime is that no prime number less than or equal to $\sqrt n$ divides $n$. One way of doing that is to show that a necessary condition for $n$ to be composite (negation of $n>1$ being prime) is the negation of the condition given above.

So, the logic works as follows. You want to show $P$ implies $Q$ (so $P$ is the sufficient condition). The method is to prove the contrapositive of the implication, that $\neg Q$ implies $\neg P$ (i.e. proving $\neg P$ is a necessary condition for $\neg Q$). Given that the contrapositive has been proven, one can be certain of $P$ implies $Q$ as well. One way to see that is to compare truth tables. But, one may be convinced the following argument: $P\implies Q$ follows from $\neg Q\implies \neg P$ since $P$ and $\neg Q$ would entail $\neg P$ a contradiction.

Answer 2

I am not sure if I understand your question. But if you want to prove that if $n$ is composite there must be at least one prime $p\leq\sqrt{n}$ that divides it:

1. Each composite number has at least two prime factors.
2. Assume the smallest prime that divides $n$ is $p$, and the next smallest $q$

Now if $p \gt \sqrt{n}$, that means $q \gt \sqrt{n}$, since if it wasn't, then it would not be larger than $p$.

Two numbers multiplied together which both are larger than $\sqrt{n}$ can not be equal to $n$, because the square root function is strict increasing. Therefore the smallest prime dividing $n$ must be $\leq \sqrt{n}$.

Answer 3

" Can we fairly deduce from this that a prime number is not divisible by a number <= sqrt(n)?"

Well, obviously[#], but that's not at issue at all. We were never asked to prove any such thing at all and we don't need to.

We were asked to prove "If $n >1$ is not divisible by any number, $k$ $1 < k \le \sqrt{n}$ then $n$ is prime".

We did a proof by contradiction "If $n$ is composite, then $k|n$ for some $k$"

THEREFORE "If $n$ is not divisible $\implies$ $n$ is not composite $\implies$ $n$ is prime."

Did we prove that $n$ prime $\implies$ $n$ is not divisible by any number less than $\sqrt{n}$? No, we did not. Why should we have? That was not what we were trying to show

=====

[#] Well, duh. If $n$ is prime it's not divisible by anything other than itself and 1. Duh!

Answer 4

we know any positive integer is always greater than its sq.root of itself like $25>\sqrt{25}$ then $n>\sqrt{n}$. now given $p\le \sqrt{n}$ therefore $n > \sqrt{n}\ge p$. then $n>p$ and $p>1$. therefore $p$ not equal to $n$ nor $1$.

let $p$ divides $n$. now $p$ is neither $n$ nor $1$ but divides $n$.

now if $n$ is prime then it would only be divisible by $n$ and $1$. but $p$ divides $n$ though it is neither $n$ nor $1$.

therefore $n$ is not prime , i.e $n$ will be prime if it is not divisible by $p$ such that $p\le\sqrt{n}$. (proved)