Proof of prime numbers

Question

Prove that for every integer $m geq 2$, if there is no prime number $p$ such that $p leq sqrt{m}$ and $p mid m$ (evenly divides), then $m$ must be prime.
Don't even know where to start with this one.
*Edit: In class we covered the Fundamental Theorem of Arithmetic, but again I'm not sure how to start applying it.

Chris Custer · Answer

This is basically the Sieve of Eratosthenes.  The point is that once you pass $sqrt m$, you have already exhausted the possibilities.  Take $11$.  Then you only need to check up to $sqrt{11}$ for factors, because anything bigger than $sqrt{11}$ would need to be paired with something less than $sqrt{11}$.  None of $2,3$ is a factor, so we have proved that $11$ is prime.

Proof of prime numbers

One Answer

Add your own answers!

Ask a Question