$Project Greater Ed Logo$

Prime and Composite Numbers

Discrete Mathematics Prime Numbers and the Fundamental Theorem of Arithmetic Prime and Composite Numbers

Prime and Composite Numbers

A natural number $n$ is said to be prime if the only natural numbers that divide $n$ are $1$ and $n$.

A natural number $n$ is said to be composite if there are two natural numbers $p,q$ (called factors of $n$) such that $p\cdot q=n$ and $p,q$ are not $1$ or $p$.

Special case: $1$ is neither prime nor composite.

Note that primes are only divisible by $1$ and themselves. Composite numbers are divisible by $1$ itself, and at least two other numbers.

Observation

It follows from the definitions above that every natural number is either prime or composite.

Testing a Number for Primality

Since a prime number is defined to be a number that is divisible by no number except itself and $1$, to test a given number $n$ for primality, we need to see if there is a number $1<m<n$ such that $m|n$. If no such number $m$ exists, then $n$ is prime.

That is, we need to try to divide $n$ by every natural number less than $n$ and see if we get back another natural number. If we do, then we know $n$ is composite, because we’ve found a number that divides $n$ evenly. If we DON’T find such a number, then $n$ is prime.

Testing a number $n$ for primality by checking for divisibility by every single number less than $n$ is tedious, and unnecessary. The next theorem will be helpful and reduce our work a bit.

Theorem

Every natural number has a prime divisor.

Whether $n$ is prime or composite, it will always have a prime divisor. This implies (with a small jump in logic) that one can test $n$ for primality by trying to divide $n$ by every PRIME less than $n$ (as opposed to every single natural number). This makes things a little easier. Still sucks though when $n$ is large (think trillions) because there are a lot of primes less than larger values of $n$ to try and divide $n$ by.

Thankfully, there are a few better, more efficient ways of testing for primality. The following theorem makes short(er) work of checking a number for primality and is easy to use when checking by hand.

Theorem

If $n$ is composite, then there is a prime $p\leq\sqrt{n}$ such that $p|n$.

Proof: Since $n$ is composite, there are natural numbers $a$ and $b$ such that $n=a\cdot b$ and $1<a\leq b<n$. We claim that $a\leq sqrt{n}$. If not, and $a>\sqrt{n}$ instead, squaring both sides gives us that $a^2>(\sqrt{n})^2=n$. Since $a\leq b$, it follows that $a^2\leq ab$. So our inequality implies $n<a^2\leq a\cdot b$. But we said at the beginning that $ab=n$, not $n<ab$. So, it follows that our supposition that $a>\sqrt{n}$ was wrong, implying that $a<\sqrt{n}$. Furthermore, since every number is divisible by a prime, this $a$ is prime or divisible by a prime. Therefore the theorem as stated above follows as a result.

Key Idea

To test a number $n$ for primality, try to divide $n$ by every prime less than or equal to $\sqrt{n}$. If you get back a natural number, then $n$ is composite. If you run out of primes, then $n$ is composite.

List of Primes Less than 100

$2,3,5,7,11,13,17,19$
$23,29,31,37,41,43,47$
$53,59,61,67,71,73,79$
$83,89,97$.

Prime

Note that $\sqrt{31}=5.5678$, so we need to see if the primes less than that divide $n$. The primes less than $5.5678$ are $2,3$ and $5$. None of these divide $31$.

Composite. Note that $19\cdot 3=57$

Note that $\sqrt{57}=7.55$, so we need to see if the primes less than that divide $n$. The primes less than $7.55$ are $2,3,5$ and $7$. $3$ divides $59$.

composite. $123$ is divisible by $3$.

Note that $\sqrt{123}=11.09$. The primes less than $11.09$ are $2,3,5,7,11$. $3$ divides $123$.

Alternatively, you could have noticed that the sum of the digits of $123$ is divisible by $3$.

Composite. $7\cdot 43=301$

As usual, note $\sqrt{301}=17.34$, so we check to see if $301$ is divisible by the primes less than $17.34$, namely $2,3,5,7,11,13,17$. $7$ divides $301$ evenly.

$1637$ is prime!

Note that $\sqrt{1637}=40.46$. The primes less than $40.46$ are $2,3,5,7,11,13,17,19, 23,29, 31,37$. Testing to see whether $1637$ is divisible by any of these comes up short. Not one of them divides $1637$. Sorry for the hassle! This is why we task computers with this stuff!

Previous Lesson

Back to Lesson

Next Topic