
Prove that a positive integer n is prime, if no prime p less than or equal to $\sqrt n $ divides n.
Answer
485.7k+ views
Hint: In certain questions of proving statements we use either the direct step by step proof or assuming its contradiction or contrapositive method.
Here we use the contradiction method by assuming the opposite of the given statement and proving it is wrong. Thus as we need to prove the property of a prime number n, we assume n to be a composite number with the same given property and prove our assumption is wrong.
Prime number n indicates that the only factors of n are 1 and n itself. The numbers except primes with factors other than 1 and n are called composite numbers. Elaborating the previous sentence we can say a composite number n will have a factor x in between 1 and n such that n=xy where x and y are positive integers and factors of n.
Complete step-by-step answer:
Step 1: Let us assume the contradiction of the statement which is let $n \geqslant 0$ be a composite number. Thus n has a factor x such that $1 < x < n$ .
So we can write n=xy where x and y are positive integers such that $1 < x,y < n$
Let us assume $y \leqslant x$ (can be assumed either way)
As we are assuming the contradiction, let $y > \sqrt n $ … (1)
Thus $\sqrt n < y < x$ implies $\sqrt n < x$ or $x > \sqrt n $ … (2)
From formula (1) and formula (2) , $n = xy > \sqrt n \times \sqrt n = n$
Implies n>n which is a contradiction.
Hence our assumption is wrong.
Thus a positive integer n is prime, if no prime p less than or equal to $\sqrt n $ divides n.
Hence proved.
Note: Students may get confused with the inequality signs, they should keep in mind that
< denotes less than and
> denotes greater than.
Examples of prime numbers: 2,3,5,7,11,13,17,19,23,29,31,33, and so on.
Here we use the contradiction method by assuming the opposite of the given statement and proving it is wrong. Thus as we need to prove the property of a prime number n, we assume n to be a composite number with the same given property and prove our assumption is wrong.
Prime number n indicates that the only factors of n are 1 and n itself. The numbers except primes with factors other than 1 and n are called composite numbers. Elaborating the previous sentence we can say a composite number n will have a factor x in between 1 and n such that n=xy where x and y are positive integers and factors of n.
Complete step-by-step answer:
Step 1: Let us assume the contradiction of the statement which is let $n \geqslant 0$ be a composite number. Thus n has a factor x such that $1 < x < n$ .
So we can write n=xy where x and y are positive integers such that $1 < x,y < n$
Let us assume $y \leqslant x$ (can be assumed either way)
As we are assuming the contradiction, let $y > \sqrt n $ … (1)
Thus $\sqrt n < y < x$ implies $\sqrt n < x$ or $x > \sqrt n $ … (2)
From formula (1) and formula (2) , $n = xy > \sqrt n \times \sqrt n = n$
Implies n>n which is a contradiction.
Hence our assumption is wrong.
Thus a positive integer n is prime, if no prime p less than or equal to $\sqrt n $ divides n.
Hence proved.
Note: Students may get confused with the inequality signs, they should keep in mind that
< denotes less than and
> denotes greater than.
Examples of prime numbers: 2,3,5,7,11,13,17,19,23,29,31,33, and so on.
Recently Updated Pages
Questions & Answers - Ask your doubts

Master Class 11 Accountancy: Engaging Questions & Answers for Success

Master Class 11 Science: Engaging Questions & Answers for Success

Master Class 12 Economics: Engaging Questions & Answers for Success

Master Class 12 Maths: Engaging Questions & Answers for Success

Master Class 12 Biology: Engaging Questions & Answers for Success

Trending doubts
When people say No pun intended what does that mea class 8 english CBSE

In Indian rupees 1 trillion is equal to how many c class 8 maths CBSE

Write a book review which you have recently read in class 8 english CBSE

How many ounces are in 500 mL class 8 maths CBSE

Which king started the organization of the Kumbh fair class 8 social science CBSE

Advantages and disadvantages of science
