# Prime numbers

• Nov 22nd 2007, 09:57 AM
Joel24
Prime numbers
Let \$\displaystyle n \ge 2\$ be a number that is not a prime.
Show that there is a divisor \$\displaystyle p\$ of \$\displaystyle n\$, with \$\displaystyle p \ge 2\$, so that \$\displaystyle n \ge p^2\$

On my paper, I've written down n=rs where n and s are any natural numbers >1. Not sure if that's needed, though.
• Nov 22nd 2007, 10:22 AM
CaptainBlack
Quote:

Originally Posted by Joel24
Let \$\displaystyle n \ge 2\$ be a number that is not a prime.
Show that there is a divisor \$\displaystyle p\$ of \$\displaystyle n\$, with \$\displaystyle p \ge 2\$, so that \$\displaystyle n \ge p^2\$

On my paper, I've written down n=rs where n and s are any natural numbers >1. Not sure if that's needed, though.

If n>2 is not prime, then it has a factor p>=2, so there also exists a q>=2 such that pq=n. Now if both n<p^2 and n<q^2, then pq<n a contradiction.

Hence every composite number >2 has a factor whose square is less than or equal to the number.

RonL
• Nov 22nd 2007, 10:29 AM
Joel24
Ah, a proof (or sorts) by contradiction. I would've never have thought of that.

Excellent. Thank you so much!