A Test for Primality is the following: Given an integer n>1, to test whether n is prime check to see if it is divisible by a prime number less than or equal to it’s square root. If it is not divisible by any of these numbers then it is prime.
Show that this is a valid test.
(a) Prove $\forall n,r,s \in \mathbb N^+, rs≤n→(r≤\sqrt{n} \vee s≤\sqrt{n})$
(b) Prove $\forall n \in \mathbb N^+, \neg P(n) \to \exists p \in \mathbb N, (P(p)\wedge (p≤\sqrt{n})\wedge p \vert{n})$
(c) State the contrapositive of the statement of part (b).
I understand how to solve part c) and believe for part a) I understand as well. My main problems arise when I attempt to prove part b) and do not know how to do it no matter how many times I read over course content.
Any help would be much appreciated!
Let us take a fixed number and denote it by $K$.
We know that :
$$\sqrt K \times \sqrt K = K$$
Let $A$ be a factor of $K$ such that $\sqrt K \lt A.$
Then we must have $A \times B = \sqrt K \times \sqrt K$ for some value of $B$ , and since $A$ is bigger than $\sqrt K$ , it implies that $B$ must be smaller than $\sqrt K$.
Hence If a number has factor bigger than the square root of the number , It must also have a factor lesser than the square root of that number.