Edugain

Login/Register Edugain for School

• Philippines

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.

Practice online or create unlimited worksheets on similar questions.

You can reuse this answer
Creative Commons License