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

1 Answer
Jun 10, 2016

Answer:

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.