Prove that if a number is not divisible by a number less than its square root, then it is a prime number?

Jun 10, 2016

Explanation:

We will prove this by assuming the contradiction.

Let us assume that a positive integer $n$ is not a prime number but composite number and

let us assume that $n$ can be factorized as $n = p \times q$.

Also let $m = \sqrt{n}$ and here $m$ may or may not be an integer. This means that $n = m \times m$.

Now if $p < m$, we have a number $p$ which is less than $m$, the square root of $n$, which is a factor of $n$ and hence, we have a number which is a factor of $n$.

Now, if we do find $p$ as factor of $n$ but $p > n$, then for other factor $q$, we must have $q < n$ as factor of $n$.

In any case, if $n$ is composite we do have a factor of $n$, which is less than $m$, the square root of $n$.

By implication, if we are not able to find such a $p$ (or $q$), it is obvious that $n$ is a prime number.