S k i l l
i n
A R I T H M E T I C

Lesson 32

# PRIME NUMBERS andPRIME FACTORIZATION

A natural number is a collection of indivisible ones.

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.

 1. What does it mean to say that a smaller number is a proper divisor of a larger number? It means that the larger number can be composed -- made up -- of the smaller number.

2 is a proper divisor of 10 because 10 can be additively composed of 2's:

5 and 1 are also proper divisors of 10, because 10 can be composed 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 a sum 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.

 2. What is a prime number? A prime number is a number whose only proper divisor is 1.

Thus a prime number can be composed 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 composed 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.

 3. What is a number called if it is not a prime? A composite number.

6 is a composite number, because it can be composed of other numbers besides 1; namely 2 and 3.

1 itself is neither prime nor composite. It is the measure by which we decide whether a number is prime or 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 can be composed of at least one prime number. It will have at least one prime divisor..
(Euclid, VII. 31)

28 is composite.  It is composed of fourteen 2's, and it is composed of four 7's.  2 and 7 are prime divisors of 28.

Example 1.   63 could be composed of which prime numbers?

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, which is divisible by 3.  That tells us that 63 can be composed of 3's.

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 is equal to nine 7's.

63, then, has could be composed of the prime numbers 3 and 7.

Example 2.   Which prime numbers are divisors of 78?

Answer.   2 is a prime divisor:

78 = 2 × 39.

Now, 39 is composite. Therefore it has a prime divisor:

39 = 3 × 13.

39 is thus divisible by both 3 and 13. And since 78 is divisible by 39, then 78 is also divisible by 3 and 13..

That is called the transitive property of " is divisible by."
If a is divisible by b, and b is divisible by c, then a is divisible by 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.

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:

 60 = 2 × 30 = 2 × 2 × 15 = 2 × 2 × 3 × 5.

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?

 Solution.    180 = 2 × 90 = 2 × 2 × 45 = 2 × 2 × 9 × 5 = 2 × 2 × 3 × 3 × 5

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.

 2 × 2 × 3 × 3 = 2 × 3 × 2 × 3 = 6 × 6.

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.

 e)   1225 = 25 × 49.  1225 is itself a square number.  It is the square of 5 × 7 = 35.

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.

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.

The first thing to note is that N + 1 is not on the list, because it is greater than every number on the list.

Now, 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 + 1 and N.  That would imply that p divides their difference (Lesson 11), namely 1 -- which is absurd.

Therefore, if N + 1 is composite, then there is a prime p that is a divisor of N + 1 but not a divisor 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 we could actually sense -- actually be aware of -- namely a list. It does not refer to something that we cannot be aware of: a list that has no end.

*

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.  If the first is a multiple of 3, then the proposition is proved; for example, 21, 23, 25.  21 is not a prime.  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.

Please make a donation to keep TheMathPage online.
Even \$1 will help.