6 is a composite number, because it can be composed of other numbers besides 1.
1 itself is neither prime nor composite.
Divisors
We can always find the divisors of a number in pairs. One member of the pair will be less than the square root of the number, and the other will be more. (If the number is a square number, then its square root will be its own partner.)
For example, here are the pairs of divisors of 24:
1 and 24. (Because 1 × 24 = 24.)
2 and 12. (Because 2 × 12 = 24.)
3 and 8. (Because 3 × 8 = 24.)
4 and 6. (Because 4 × 6 = 24.)
Each number on the left is less than the square root of 24, and each number on the right is more.
The point is:
When we look for divisors of a number,
it is necessary to look only up to its square root.
Because for each divisor we find less than the square root, we will have found its partner, which is more.
Problem 5. If we are looking for the divisors of 157, up to what number must we look?
12. Because 13 is more than the square root of 157.
In this Lesson we will be looking for the prime divisors of a number, and to that we now turn.
Prime divisors
Every number except 1 is either prime or composite. And if a number is composite, it will have a prime divisor.
(Euclid, VII. 31)
28 is composite. It has a prime divisor 2 and a prime divisor 7.
Example 1. What are the prime divisors of 63?
Answer. Here again are the first few prime numbers:
2, 3, 5, 7, 11, 13, 17.
We must test whether 2 is a divisor, or 3, or 5, and so on. But we need test only up to 7, because 11 is more than the square root of 63.
Is 2 a divisor of 63? No, it is not. How do we know? Because 63 is not an even number. And how do we know that? Because even numbers end in 0, 2, 4, 6, or 8.
Next, is 3 a divisor of 63? There is a test for divisibility by 3, and it is as follows:
A number is divisible by 3 if the sum of the digits is divisible by 3.
The sum of the digits of 63 is 6 + 3 = 9. 9 is divisible by 3. That tells us that 63 is divisible by 3. 3 is a prime divisor of 63.
Next, is 63 divisible by 5? There is a simple test for divisibility by 5,
namely, the number ends in either 0 or 5. 63 does not end in 0 or 5. Therefore, 63 is not divisible by 5.
Finally, is 63 divisible by 7? Yes, it is: 63 = 7 × 9.
63, then, has two prime divisors: 3 and 7.
Example 2. What are the prime divisors of 78?
Answer. 2 is a prime divisor, and
78 = 2 × 39.
Now, 39 is composite. Therefore it has a prime divisor:
39 = 3 × 13.
And since 39 is made up of 13's, and 78 is made up of 39's, then 78 is made up of 13's. That is, 13 is a divisor of 78.
That is called the transitive property of " is made up of" or, equivalently, "is a divisor of;" namely:
If a is a divisor of b, and b is a divisor of c, then a is a divisor of c.
78 therefore has three prime divisors: 2, 3, and 13.
Problem 6. What is the smallest prime that is a divisor of the following?
a) 231. 3. The sum of the digits is divisible by 3.
b) 3,165. 3.
c) 3,265. 5.
d) 91. 7.
e) 121. 11.
Prime factorization
When numbers are multiplied, they are called factors. Since
30 = 2 × 15,
we say that 2 and 15 are factors of 30. Now, 2 is a prime factor -- but 15 is not. However, 15 = 3 × 5. Therefore we can express 30 as a product of prime factors only:
30 = 2 × 3 × 5.
"2 × 3 × 5" is called the prime factorization of 30. And it is unique. That is, apart from the order of the factors:
Every composite number can be uniquely factored
as a product of prime numbers only.
Note: We could have found those same factors by factoring 30 in any way. For example,
30 = 5 × 6.
And since 6 = 2 × 3,
30 = 5 × 2 × 3.
Apart from the order, we have found the same prime factors.
Example 3. Find the prime factorization of 102.
Solution. 2 is obviously a prime factor. Its partner will be half of 102
-- 51 (Lesson 16):
102 = 2 × 51.
Because the sum of the digits is divisible by 3, we know that 51 has a prime factor 3. Now, 3 times what is equal to 51? On mentally decomposing 51 into 30 + 21,
51
3 |
= |
30 + 21
3 |
= 10 + 7 = 17. |
51 = 3 × 17.
And 17 is a prime number. Therefore,
102 = 2 × 3 × 17.
That is the prime factorization of 102.
Problem 7. Which of these numbers is prime and which is composite? If a number is composite, write its prime factorization.
a) 29. Prime.
b) 50. 2 × 5 × 5.
c) 73. Prime.
d) 32. 2 × 2 × 2 × 2 × 2.
e) 60. 2 × 2 × 3 × 5.
f) 135. 3 × 3 × 3 × 5.
g) 137. Prime.
h) 143. 11 × 13.
i) 169. 13 × 13.
j) 360. 2 × 2 × 2 × 3 × 3 × 5.
k) 450. 2 × 5 × 5 × 3 × 3.
When a prime appears twice, that product is a square number. 60, then, has one square factor, namely 2 × 2 = 4. 60 = 4 × 15.
180, then, has two square factors: 2 × 2 = 4, and 3 × 3 = 9.
But 4 × 9 is itself a square number -- 36. For,
A product of square numbers is itself a square number.
Is there a last prime?
As the numbers get larger, the greater the possibility that they will have a divisor, so that there might in fact be a last prime.
Now, if there were a last prime, then we could imagine a list that contains every prime up to and including the last one. We will now prove that there is no such list, which is to say, There is no last prime.
Here is the theorem:
Given any list of prime numbers, there will always be a prime number
that is not on the list.
(Euclid, IX. 20.)
Let the following, then, be any list of prime numbers:
2, 3, 5, 7, 11, . . . , P.
Now construct the number N which will be the product of every prime on that list:
N = 2 × 3 × 5 × 7 × 11 × . . . × P.
Every prime on the list is thus a divisor of N.
Add 1 to N:
N + 1 = (2 × 3 × 5 ×
7 × 11 × . . . × P) + 1.
Now, N + 1 a number that is not on the list, because it is greater than every number on the list. And N + 1 is either prime or composite. If it is prime, then we have found a prime that is not on the list, and the theorem is proved.
If N + 1 is composite, then it has a prime factor p. But p is not one of the primes on the list
For if it were, then p would be a divisor of both N and N + 1. But that would imply that p divides their difference (Lesson 11), namely 1 -- which is absurd.
Therefore p is not one of the primes of N, which is to say, p is not a prime on the list.
Therefore, given any list of primes, there will always be a prime that is not on the list. Which is what we wanted to prove.
*
A modern enunciation of this theorem is: The number of primes is infinite. Euclid thus teaches us what we mean, or rather what we should mean, when we say that a collection of numbers is "infinite." It means: "No list of them is complete. There will always be more." That meaning of "infinite" refers to something that exists and that we could witness, namely an actual list. It does not refer to something that we cannot witness, namely a list that has no end.
Thus if we say that the number of primes is infinite, we mean they are potentially infinite, not actually infinite.
*
A famous problem in mathematics is the twin prime conjecture. It states that there are infinitely many pairs of primes that differ only by 2. For example, 5 and 7, 17 and 19, 41 and 43. The conjecture has never been proved.
What about prime triples, which are three primes that differ only by 2? For example, 3, 5, 7. What do you think? Are there many -- perhaps even an infinite number -- of such triples? Or is 3, 5, 7 the only one?
3, 5, 7 is the only such triple. Because in every sequence of three odd numbers, at least one of them is a multiple of 3. For if the first is a multiple of 3, then the proposition is proved; for example, 21, 23, 25. If the first is 1 more than a multiple of 3, then, on adding 2, the next will be a multiple of 3; for example, 25, 27, 29. Finally, if the first is 1 less than a multiple of 3, then the next will be 1 more, and the third will be a multiple of 3; for example, 35, 37, 39. In the sequence, 3, 5, 7, 3 is the only multiple of 3 that is a prime.
Next Lesson:
Greatest common divisor. Lowest common multiple.
Introduction | Home | Table of Contents
Please make a donation to keep TheMathPage online.
Even $1 will help.
Copyright © 2012 Lawrence Spector
E-mail: themathpage@nyc.rr.com
