Number Theory
4.2 Prime and Composite Numbers
Prime Numbers and Composite Numbers
Prime numbers are the "atoms" of whole-number multiplication: every whole number greater than 1 is built from them.
Consider a concrete representation of the number 12. We can rearrange it into 3 groups of 4 or 4 groups of 3. Thats because $12=3\times 4=4\times 3$.
$$\square \square\square\square|\square\square\square\square|\square\square\square\square $$
$$\square\square\square|\square\square\square|\square\square\square|\square\square\square $$
These numbers are factors of 12 that when multiplied together give 12. There is also 2 groups of 6 and 6 groups of 2.
$$\square\square\square\square\square\square|\square\square\square\square\square\square $$
$$\square\square|\square\square|\square\square|\square\square|\square\square|\square\square $$
And trivially, 1 group of 12 or 12 groups of 1.
$$\square\square\square\square\square\square\square\square\square\square\square\square $$
$$\square|\square|\square|\square|\square|\square|\square|\square|\square|\square|\square|\square $$
Numbers that cannot be divided up into groups like the previous and only into singletons like the latter are called primes. For example, try to break up 7 in groups other than 1. It can't be done.
Definition: Prime and Composite Numbers
A whole number $n>1$ is prime if its only positive factors are $1$ and $n$.
A whole number $n>1$ is composite if it has a factor other than $1$ and itself.
One of the most fundamental results in number theory is that every whole number greater than one is either prime or composite, and it is possible to write every composite number as a unique product of its factors.
Example: Prime or composite?
Classify each number: $1564$, $1001$, $2781$, $1$.
Show Solution
We'll use fast divisibility checks and targeted factoring.
- $1564$ is even, so composite. We don't need to find all of the factors to see it is composite. Just one is enough.
- The divisibility rule for 11 tells us that $1001$ as at least an $11$ in it. $1001=7\cdot 11\cdot 13$, so composite.
- $2781$ has digit sum $2+7+8+1=18$, divisible by 3, so composite.
- $1$ is neither. Our definitions above only consider numbers greater than 1.
Quick filters first, then only the necessary tests.
MyOpenMath: Prime and Composite classification
Divisors Come in Pairs and the Square-Root Test
As you might have noticed before, divisors always come in pairs. From our first example of the section, $12=4\cdot 3 = 3 \cdot 4$. It is also the case, that as one factor gets larger, its pair grows smaller.
Check out the factors of $24=a\cdot b$
| a | b |
|---|---|
| 1 | 24 |
| 2 | 12 |
| 3 | 8 |
| 4 | 6 |
| 6 | 4 |
| 8 | 3 |
| 12 | 2 |
| 24 | 1 |
Theorem: Divisors Come in Pairs
If $d\mid n$ and $d\ne 0$, then $\dfrac{n}{d}\mid n$.
To show this theorem is relatively straight forward. If $d|n$, then by definition $n=d(k)$ for some natural number $k$. Using our commutative property shows that $n=k(d)$ which means $k|n$. And because we know that devision would be defined here, we can find the value of $k$ directly, $k=\frac{n}{d}$.
You'll notice that we did alot of extra work here. We started repeating ourselves after we found $4\cdot 6 = 24$. If we start from the smallest factors in the left column and start checking for factors of increasing size, once the smaller factor becomes larger than its pair we could have stopped checking.
Check out factors of $36=a\cdot b$ for a finer point on this idea.
| a | b |
|---|---|
| 1 | 36 |
| 2 | 18 |
| 3 | 12 |
| 4 | 9 |
| 6 | 6 |
Once we get to $6\cdot 6 = 36$ is the exact position where we start repeating. The next entry in the table would be $9\cdot 4 = 36$, which we've already captured in $4\cdot 9 = 36$. This lets us know that we can stop once our smaller factor becomes equal to the larger factor. When those factors are equal, when $a=b$, we have $a^2=36$. This implies that $a$ is the square root of the dividend. We'll do more work on this later. For now...
Theorem: Prime-Check Bound
If $n>1$ is composite, then it has a factor $d$ with
$$1<d\le\sqrt{n}.$$
So to test primality, check possible prime divisors only up to $\sqrt n$.
This can save us a huge amount of time and effort in checking for divisiors.
Example: Using the square-root bound efficiently
Check whether $397$ is prime.
Show Solution
Since $\sqrt{397}\approx 19.9$, we only test prime divisors $2,3,5,7,11,13,17,19$.
- Not by 2 (odd)
- Not by 3 (digit sum $=19$)
- Not by 5 (last digit not 0 or 5)
- $397\div 7$ not integer
- $397\div 11=36$ remainder 1
- We didn't develop any divison rules for these larger factors. We'll have to do them by hand. But luckily they're relatively short. $397\div 13=30$ remainder 7
- $397\div 17=23$ remainder 6
- $397\div 19=20$ remainder 17
No prime divisor up to $\sqrt{397}$, so $397$ is prime.
Fundamental Theorem of Arithmetic
Theorem: Fundamental Theorem of Arithmetic
Every whole number greater than 1 can be written as a product of prime numbers, and this factorization is unique up to order.
Example: Prime factorization and divisor listing
Find all positive divisors of $120$, then write $120$ as a prime product.
Show Solution
First, lets find some divisors. $120$ is even so we can divide a $2$ out.
$$120=2\cdot 60$$
Other factors would be hiding away in the $60$, which is also even. So lets take another $2$ out again.
$$120=2\cdot 2\cdot 30$$
$30$ is again divisble by $2$.
$$120=2\cdot 2\cdot 2\cdot 15$$
And finally, $3$ and $5$ are hiding in that $15$.
$$120=2\cdot 2\cdot 2\cdot 3\cdot 5=2^3\cdot 3\cdot5$$
MyOpenMath: Prime factorizations
Another convinient way to do this type of factoring is using a factor tree. Lets try factoring $2310$. We can split this number with any factor that you can find. For example, we can quickly see that the number is divisible by $10$.
The new numbers are leaves of the factor tree. We'll continue to split the numbers until they're prime, then they can be split no more. Lets split that $10$ up.
We also know that $231$ isn't done, its divisible by $3$.
And finally we can split that $77$.
And the leaves of this tree are the prime factors of our number and we can write it in its prime factorized form using them.
MyOpenMath: Factor tree
Counting Divisors from Prime Exponents
We've been focusing on the prime factors of numbers. But, any number that can divide another is known as a divisor. The prime factoriziation of a number gives us a set of numbers to pick from to build all of the divisors of a number. For example, lets take the prime factorization of $$24=2\cdot 2\cdot 2\cdot 3$$
We can build a divisor of $24$ by picking any combination of factors. We could take a $2$ and a $3$ and get $2\cdot 3 = 6$ which is a divisor of $24$. We could also have taken two $2$'s when building our divisor. $2\cdot 2\cdot 3 = 12$ which also divides $24$. We can use our counting principle to count all the possible factors of $24$.
When picking, we have $4$ choices when picking $2$. We can have one $2$, we can have two $2$'s, we can have three $2$'s, or we can choose no $2$'s. Similarly, we have $2$ choices when picking $3$'s. You can take one or none. Putting it together:
$$4 \text{ choices }\cdot 2 \text { choices }=8 \text{ divisors}$$
The number $24$ has $8$ unique divisors.
Check:
| a | b |
|---|---|
| 1 | 24 |
| 2 | 12 |
| 3 | 8 |
| 4 | 6 |
Theorem: Counting Divisors
If
$$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$$
is the prime factorization of $n$, then the number of positive divisors is
$$(a_1+1)(a_2+1)\cdots(a_k+1).$$
Revisiting that example, the exponents from $24=2^3\cdot 3^1$ we'd have
$$(3+1)(1+1)=4\cdot 2 = 8$$
The $+1$ comes from having the option to not choose that prime factor.
Example: How many divisors?
Find the number of positive divisors of $360$ and $1{,}000{,}000$.
Show Solution
For $360$:
$$360=36\cdot 10=(2^2\cdot 3^2)(2\cdot 5)=2^3\cdot 3^2\cdot 5^1.$$
Divisor count:
$$(3+1)(2+1)(1+1)=4\cdot 3\cdot 2=24.$$
For $1{,}000{,}000$:
$$1{,}000{,}000=10^6=(2\cdot 5)^6=2^6\cdot 5^6.$$
Divisor count:
$$(6+1)(6+1)=49.$$
So $360$ has 24 positive divisors, and $1{,}000{,}000$ has 49.
MyOpenMath: Counting divisors
The Sieve of Eratosthenes
With all of this talk of prime numbers, you might be wondering if we know all of the prime numbers. There are, in fact, infinitely many of them and a subsantial amount of effort has been made throughout history to find them.
Eratosthenes was a Greek philosopher known for many things. He was one of the first people to calculate the circumference of the Earth! He also developed a process of discovering primes.
The sieve is a systematic process for listing primes up to a cutoff $N$:
- Start with all numbers from $2$ to $N$.
- Circle 2, cross out its multiples.
- Move to the next uncrossed number, circle it, cross out its multiples.
- Stop once your current prime exceeds $\sqrt{N}$.
Everything still uncrossed is prime.
Example: Sieve up to 30
Use the sieve idea to list all primes less than or equal to 30.
Show Solution
Start with 2 through 30.
- Circle 2, cross out multiples: 4,6,8,...,30.
- Next uncrossed is 3, cross out 6,9,12,...,30 (some already crossed).
- Next uncrossed is 5, cross out 10,15,20,25,30.
Now $\sqrt{30}\approx 5.47$, so we can stop after processing 5.
Uncrossed numbers are:
$$2,3,5,7,11,13,17,19,23,29.$$
Those are exactly the primes up to 30.