# proof that $n$ is prime or has prime factor $\leq \sqrt{n}$

apparently my attempt proof is wrong says the chat person will, so can you guys tell me how to fix please :)

Show that any integer $n \gt 1$ is either a prime or has as a factor a prime $\leq \sqrt{n}$

if $n$ is prime that is that.

if $n$ isn't prime it has prime factors $n=p_1 p_2 \dots p_i$

assume $p_1,p_2,\dots,p_i\gt \sqrt{n}$

then $n=\sqrt{n}$ or $n\lt p_1 p_2 \dots p_i$, contradiction!

so $n$ has a prime factor $\leq \sqrt{n}$

• You need to mention that $i>1$, and omit that silly sentence that $n=\sqrt{n}$, but otherwise this is OK. – Adam Hughes Dec 2 '14 at 7:10
• You are assuming ALL of the $p>\sqrt{n}$, that's the problem. – Angelo Rendina Dec 2 '14 at 7:10
• @AngeloRendina but the problem is 'a' prime factor, so for contradiction i need all to be bigger than $\sqrt{n}$? – beginner Dec 2 '14 at 7:11
• That's not a problem @AngeloRendina , that's how you derive the contradiction. – Adam Hughes Dec 2 '14 at 7:14
• oh i see why it is silly now, cause no prime(from my factors) could make that true, thanks @adam – beginner Dec 2 '14 at 7:27

We have two cases:

1. If $n$ is prime, then we're done

2. If $n$ is not prime, then we have two cases:

2.1. If $n$ has a prime factor $p\leq\sqrt{n}$, then we're done

2.2. If $n$ does not have a prime factor $p\leq\sqrt{n}$, then:

• $n$ has a prime factor $p>\sqrt{n}$

• $n$ has a factor $\frac{n}{p}\leq\sqrt{n}$

• If $\frac{n}{p}$ is prime, then we're done

• If $\frac{n}{p}$ is not prime, then:

• Let $q$ be a prime factor of $\frac{n}{p}$

• $q$ is also a prime factor of $n$, and $q<\frac{n}{p}\leq\sqrt{n}$