 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. 1 is the source of every natural number. Every natural number is a multiple—the repeated addition—of 1.

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

Now, many numbers are multiples of numbers other than 1.  12, for example, is a multiple of 1, 2, 3, 4, and 6.  12 is divisible—it could be divided equally—into any of those. We say that 1, 2, 3, 4, and 6 are the proper divisors of 12.

 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 is composed of—is a multiple of—the smaller number.

The proper divisors do not include the number itself.

Now, 1 is a proper divisor of every number. Certain numbers, however, have 1 as their only proper divisor. For example, 7. 7 is composed only of 1's. We say therefore that 7 is a prime number.

 2. What is a prime number? A prime number has 1 as its only proper divisor.

10 is not a prime number, because it is divisible into 2's: and into 5's: We call 10 a composite number. 10 can be composed of numbers other than 1.

Problem 1.   Is 1 itself a prime number?

No. 1 has no proper divisors. It is not composed of other numbers. 1 is the measure. It cannot be measured.

Problem 2.   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. Thus every number other than 1 is either prime or composite. What is more:

Every composite number is a multiple of some prime number.

Equivalently,

Every composite number has at least one prime number
as a divisor.

(Euclid, VII. 31.)

As we have seen, 10 has the prime divisors 2 and 5:  The composite number 12 is divisible by the prime number 3: We will now be looking for the prime divisors of a number. And we will see that it will be necessary to look only up to the square root of the number.

Square roots

When we multiply a number by itself, we say that we have "squared" the number.  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, however, is between 7 and 8. For,

7 × 7 = 49.  8 × 8 = 64.

Problem 4.   The square root of 175 falls between which two numbers?

13 and 14.  13 squared is 169. 14 squared is 196.

Divisors

We can always find the divisors of a number in pairs.  One member of the pair will be less than the square root, 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.

When we find a divisor 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 12 squared is 144. While 13 squared is 169.

Prime divisors

Example 1.   63 is a multiple 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:

If the sum of the digits is divisible by 3, then the number 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 is divisible by 3.

Next, is 63 divisible by 5?  There is a simple test for divisibility by 5: 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, is a multiple of the prime numbers 3 and 7.

Example 2.   78 is a multiple of which prime numbers?

Answer.   78 is even. Therefore, it is a multiple of 2:

78 = 39 × 2.

Now, 39 is composite. Therefore it is a multiple of some prime:

39 = 3 × 13.

39 is thus composed of 3's and 13's. And since 78 is composed of 39's, then 78 is also composed of 3's and 13's.

78 therefore has three prime divisors:  2, 3, and 13. 78 is a multiple of each one.

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.   When we write the factors of a number, then each prime divisor will be appear as a factor. 2 is obviously a prime factor.  Its partner will be half of 102, which is 51. (Lesson 16.)

102 = 2 × 51.

Now, since the sum of the digits of 51 is divisible by 3, we know that 51 has a prime factor 3.  3 times what number 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.  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 a square number as a factor.  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 and be composite. So 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.

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 is no limit to those that we can name." That meaning of infinite refers to something that we could actually be aware of—namely a list. It does not refer to something that we cannot be aware of: a list that never ends.

*

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.