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}$

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.