Question

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

Answer 1

Please see below.

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=pxxq`.

Also let `m=sqrtn` and here `m` may or may not be an integer. This means that `n=mxxm`.

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.