Lesson 32

PRIME NUMBERS
and
PRIME FACTORIZATION

A natural number is a collection of indivisible ones.

1, 2, 3, 4, and so on. Although we often represent a natural number by a line,

the student should keep in mind that a natural number is not like a line.

A prime number is a special kind of natural number. In order to define a prime number, we must first define a proper divisor of a number.

By a "number" in what follows, we will mean a natural number.

2 is a proper divisor of 10, because 10 can be composed -- made up -- of 2's.   5 and 1 are also proper divisors of 10, because 10 can be made up

of 5's and 1's.  As for 10 itself, we are not interested that 10 is equal to one 10; we want to know what other numbers will compose it.

Nevertheless, 10 is called a divisor of itself, but not a proper divisor.

The proper divisors do not include the number itself.

It is important to note that 1 is a proper divisor of every natural number (except itself), because every natural number is made up of 1's. That is what a natural number is

5 = 1 + 1 + 1 + 1 + 1.

Problem 1.

a)  Which numbers are the divisors of 12?

To see the answer, pass your mouse over the colored area.
To cover the answer again, click "Refresh" ("Reload").
Do the problem yourself first!

1, 2, 3, 4, 6, 12.

a)  Which are the proper divisors of 12?

1, 2, 3, 4, 6.

b)  16 can be composed of which other numbers?

1, 2, 4, 8.

Those are the proper divisors of 16.

c)  17 can be composed of which other numbers.

1.

1 is its only proper divisor.

d)  Write all the proper divisors of 29.

1.

Thus a prime number can be made up only of 1's.  17 and 29 are prime numbers.

Again, 1 is a proper divisor of every number (except itself), but a prime number has 1 as its only proper divisor.

Problem 2.   Is 1 itself a prime number?

No. 1 has no proper divisors. 1 cannot be made up of other numbers.
1 in this case is the measure. It cannot be measured.

Problem 3.   Write the first ten prime numbers.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

With the exception of 2, then, -- which is the only even prime -- a prime number is a kind of odd number.

6 is a composite number, because it can be composed of other numbers besides 1.

1 itself is neither prime nor composite.

Square roots

When we multiply a number by itself, we say that we have "squared" the number.  Thus the square of 5 is 5 × 5 = 25.  We then say that 5 is the square root of 25.  The square numbers are the numbers we get by squaring a number:  1, 4, 9, 16, 25, and so on.

50, for example, is not a square number, therefore it does not have an exact square root.  Its square root is closest to 7, however, because

7 × 7 = 49.

Problem 4.   The square root of 175 is closest to what number?

13.  13 × 13= 169.

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 × 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.

Square factors

We sometimes want to know whether a number has square factors.  50 for example has the square factor 25.  50 = 25 × 2. But for a less familiar number, such as 60, we can discover whether or not it has square factors by writing its prime factorization.

We could proceed as follows:

When a prime appears twice, that product is a square number.  60, then, has one square factor, namely  2 × 2 = 4.   60 = 4 × 15.

Example 4.   Does 180 have any square factors?

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.

Problem 8.   Find the square factors of each number by writing its prime factorization.

a)   112 = 2 × 2 × 2 × 2 × 7 = 16 × 7.

b)   450 = 3 × 3 × 5 × 5 × 2 = 3 × 5 × 3 × 5 = 225 × 2.

c)   153 = 3 × 51 = 3 × 3 × 17 = 9 × 17.

d)   294 = 2 × 147 = 2 × 3 × 49 = 49 × 6.

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.