Question

Prove that a positive integer $n \geq 2$ is prime if and only if there is no positive integer greater than $1$ and less than or equal to $\sqrt{n}$ that divides $n$

Answer 1

Proof given by contradiction.

Explanation:

Given that:

`n \geq 2`

To prove:

`n` is prime if and only if no positive integer > 1 and
`\leq`
`\sqrt n` divides
`n`.

Solution:

First of all, let
`n` is a composite number i.e. not a prime number such that:

`n =a* b`

and
`a` and
`b` are prime and
`a` divides
`n` and
`b` also divides
`n`.

Let
`\sqrt n = p`

or
`n = p* p`

1.
`\underline{a < p}`:

`a` is prime and is a divisor of
`n`.

2.
`\underline{a>p}`:

`n = a* b = p* p`

We have assumed that
`a > p \Rightarrow b <p`

`b` is a prime number and is a divisor of
`n`.

But we are given that no prime number
`\leq \sqrt n` divides
`n` but we have proved that
`b < \sqrt n` divides
`n`.

So, it is a contradiction to our assumption.

Therefore, our assumption is wrong that
`n` is a composite number.

Hence, proved that
`n` is a prime number.