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

Question

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

1 Answer

Impact of this question

6101 views around the world

You can reuse this answer
Creative Commons License

Answer 1 · 2016-06-10T06:31:29

Please see below.

Explanation:

We will prove this by assuming the contradiction.

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

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

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

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

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

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

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

Science

Math

Humanities

... and beyond

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

1 Answer

Explanation:

Related questions

Impact of this question