Question

Prove that a positive integer n is prime, if no prime p less than or equal to √n divides n.
From RD Sharma class 10 HOTS.

Answer 1

Let us prove the result through contradiction.

Let n>0 be a composite number.
hence, n will have a factor a such that 1<a<n.
i.e, we can write n=ab, where a,b are positive integers and 1<a and b<n

We may assume that b<=a
Let b>√n

√n<b<a
hence, a>√n
n=ab > √n*√n=n
Gives, n>n, which is a contradiction.

Hence this is a contradiction to our assumption. Thus for every positive integer n is prime, if no prime p less than or equal to √n divides n.