Prove that a positive integer ^@n^@ is a prime number if no prime number less than or equal to ^@\sqrt{n}^@ divides ^@n^@.


  1. Home
  2. Math
  3. All Questions
Answer:


Step by Step Explanation:
  1. Let ^@n^@ be a positive integer such that any prime number less than or equal to ^@\sqrt{n}^@ does not divide ^@n^@.
    Now, we have to prove that ^@n^@ is prime.
  2. Let us assume ^@n^@ is not a prime integer, then ^@n^@ can be written as
    ^@n = yz^@ where ^@1 < y \le z^@
    ^@\implies y \le \sqrt{n}^@ and ^@z \ge \sqrt{n}^@
  3. Let ^@p^@ be a prime factor of ^@y^@, then, ^@p \le y \le \sqrt{n}^@ and ^@p^@ divides ^@y^@.
    ^@\begin{align} \implies & p | yz \\ \implies & p | n && .....(1) \end{align}^@
  4. By eq(1), we get a prime number less than or equal to ^@\sqrt{ n }^@ that divides ^@n^@. This contradicts the given fact that any prime number less than or equal to ^@\sqrt{n} ^@ does not divide ^@n^@, therefore, our assumption that ^@n^@ is not a prime integer was wrong.
  5. Hence, if no prime number less than or equal to ^@\sqrt{n}^@ divides ^@n^@, then ^@n^@ is a prime integer.

You can reuse this answer
Creative Commons License