55.6k views
5 votes
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$

User Tmdavison
by
7.7k points

1 Answer

5 votes

Answer:

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.

User Galeb Nassri
by
6.5k points