High School Mathematics Extensions/Primes/text

Introduction

A prime number (or prime for short) is a natural number that can only be wholly divided by 1 and itself. For theoretical reasons, the number 1 is not considered a prime (we shall see why later on in this chapter). For example, 2 is a prime, 3 is prime, and 5 is prime, but 4 is not a prime because 4 divided by 2 equals 2 without a remainder.

The first 20 primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71.

Primes are an endless source of fascination for mathematicians. Some of the problems concerning primes are so difficult that even decades of work by some of the most brilliant mathematicians have failed to solve them. One such problem is Goldbach's conjecture, which proposes that all even numbers greater than 3 can be expressed as the sum of two primes. No one has been able to prove it true or false.

This chapter will introduce some of the elementary properties of primes and their connection to an area of mathematics called modular arithmetics.

Geometric meaning of primes

Given 12 pieces of square floor tiles, can we assemble them into a rectangular shape in more than one way? Of course we can, this is due to the fact that

$\begin{array}{ccc}12& =& 12\times 1\\ & =& 6\times 2\\ & =& 4\times 3\end{array}$

We do not distinguish between 2×6 and 6×2 because they are essentially equivalent arrangements.

But what about the number 7? Can you arrange 7 square floor tiles into rectangular shapes in more than one way? The answer is no, because 7 is a prime number.

Fundamental Theorem of Arithmetic

A theorem is a non-obvious mathematical fact. A theorem must be proven; a proposition that is generally believed to be true, but without a proof, is called a conjecture.

With those definitions out of the way the fundamental theorem of arithmetic simply states that:

Any natural number (except for 1) can be expressed as the product of primes in one and only one way.

For example

$12=2\times 2\times 3$

Rearranging the multiplication order is not considered a different representation of the number, so there is no other way of expressing 12 as the product of primes.

A few more examples

$\begin{array}{ccccccc}99& =& 3& \times & 3& \times & 11\\ 52& =& 2& \times & 2& \times & 13\\ 17& =& 17& \end{array}$

A number that can be factorised into more than one prime factor is a called a composite number (or composite for short).

Why?

Bearing in mind the definition of the fundamental theorem of arithmetic, why isn't the number 1 considered a prime?

Factorization

We know from the fundamental theorem of arithmetic that any integer can be expressed as the product of primes. The million dollar question is: given a number x, is there an easy way to find all prime factors of x?

If x is a small number then it is easy. For example 90 = 2 × 3 × 3 × 5. But what if x is large? For example x = 4539? Most people can't factorize 4539 into primes in their heads. But can a computer do it? Yes, the computer can factorize 4539 fairly quickly. We have 4539 = 3 × 17 × 89.

Since computers are very good at doing arithmetic, we can work out all the factors of x by simply instructing the computer to divide x by 2 then 3 then 5 then 7 ... and so on.

So there is an easy way to factorize a number into prime factors. Just apply the method described above. However, that method is too slow for large numbers: trying to factorize a number with thousands of digits would take more time than the current age of the universe. But is there a fast way? Or more precisely, is there an efficient way? There may be, but no one has found one yet. Some of the most widely used encryption schemes today (such as RSA) make use of the fact that we can't factorize large numbers into prime factors quickly. If such a method is found, a lot of internet transactions will be rendered unsafe.

Consider the following three examples of the dividing method in action.

Example 1

$x=21$

$x/2=10.5$ not a whole number

$x/3=7$ hence 3 and 7 are the factors of 21.

Example 2

x = 153

x / 2 = 76.5 hence 2 is not a factor of 153

x / 3 = 51 hence 3 and 51 are factors of 153

51 / 3 = 17 hence 3 and 17 are factors of 153

It is clear that 3, 9, 17 and 51 are the factors of 153. The prime factors of 153 are 3, 3 and 17 (3×3×17 = 153)

Example 3

2057 / 2 = 1028.5

...

2057 / 11 = 187

187 / 11 = 17

hence 11, 11 and 17 are the prime factors of 2057.

Exercise

Factor the following numbers:

1. 13
2. 26
3. 59
4. 82
5. 101
6. 121
7. 2187 Give up if it takes too long. There is a quick way.

Fun Fact -- Is this prime?

Interestingly, there is an efficient way of determining whether a number is prime with 100% accuracy with the help of a computer.

2, 5 and 3

The primes 2, 5, and 3 hold a special place in factorization. Firstly, all even numbers have 2 as one of their prime factors. Secondly, all numbers whose last digit is 0 or 5 can be divided wholly by 5.

The third case, where 3 is a prime factor, is the focus of this section. The underlying question is: is there a simple way to decide whether a number has 3 as one of its prime factors?

Theorem - Divisibility by 3

A number is divisible by 3 if and only if the sum of its digits is divisible by 3

For example, 272 is not divisible by 3, because 2 + 7 + 2 = 11, which is not divisible by 3.

945 is divisible by 3, because 9 + 4 + 5 = 18. And 18 is divisible by 3. In fact 945 / 3 = 315

Is 123456789 divisible by 3?

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = (1 + 9) × 9 / 2 = 45

4 + 5 = 9

Nine is divisible by 3, therefore 45 is divisible by 3, therefore 123456789 is divisible by 3!

The beauty of the theorem lies in its recursive nature. A number is divisible by 3 if and only if the sum of its digits is divisible by 3. How do we know whether the sum of its digits is divisible by 3? Apply the theorem again!

info -- Recursion

A prominent computer scientist once said "To iterate is human, to recurse, divine." But what does it mean to recurse? Before that, what is to iterate?

"To iterate" simply means doing the same thing over and over again, and computers are very good at that. An example of iteration in mathematics is the exponential operation, e.g. xⁿ means doing x times x times x times x...n times. That is an example of iteration.

Thinking about iteration economically (in terms of mental resources), by defining a problem in terms of itself, is "to recurse". To recursively represent xⁿ, we write:

$x^n=1$ if n equals 0.

$x^n=x\times x^{n-1}$ if n > 0

What is 9⁹? That is 9 times 9 ⁸. But what is 9⁸, it is 9 times 9⁷. Repeating this way is an example of recursion.

Exercises

1. Factorize

1. 45
2. 4050
3. 2187

2. Show that the divisible-by-3 theorem works for any 3 digits numbers (Hint: Express a 3 digit number as 100a + 10b + c, where 0 ≤ a, b and c ≤ 9)

3. "A number is divisible by 9 if and only if the sum of its digits is divisible by 9." True or false? Determine whether 89, 558, 51858, and 41857 are divisible by 9. Check your answers.

Finding primes

The prime sieve is a relatively efficient method for finding all primes less than or equal to a specified number. To find all primes less than or equal to 50, we do the following:

First, we write out the numbers 1 to 50 in a table as below

$\begin{array}{cccccccccc}1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ 11& 12& 13& 14& 15& 16& 17& 18& 19& 20\\ 21& 22& 23& 24& 25& 26& 27& 28& 29& 30\\ 31& 32& 33& 34& 35& 36& 37& 38& 39& 40\\ 41& 42& 43& 44& 45& 46& 47& 48& 49& 50\end{array}$

Cross out 1, because it's not a prime.

$\begin{array}{cccccccccc}X& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ 11& 12& 13& 14& 15& 16& 17& 18& 19& 20\\ 21& 22& 23& 24& 25& 26& 27& 28& 29& 30\\ 31& 32& 33& 34& 35& 36& 37& 38& 39& 40\\ 41& 42& 43& 44& 45& 46& 47& 48& 49& 50\end{array}$

Now 2 is the smallest number not crossed out in the table. We mark 2 as a prime and cross out all multiples of 2 i.e. 4, 6, 8, 10 ...

$\begin{array}{cccccccccc}X& 2_p& 3& X& 5& X& 7& X& 9& X\\ 11& X& 13& X& 15& X& 17& X& 19& X\\ 21& X& 23& X& 25& X& 27& X& 29& X\\ 31& X& 33& X& 35& X& 37& X& 39& X\\ 41& X& 43& X& 45& X& 47& X& 49& X\end{array}$

Now 3 is the smallest number not marked in anyway. We mark 3 as a prime and cross out all multiples of 3 i.e. 6, 9, 12, 15 ...

$\begin{array}{cccccccccc}X& 2_p& 3_p& X& 5& X& 7& X& X& X\\ 11& X& 13& X& X& X& 17& X& 19& X\\ X& X& 23& X& 25& X& X& X& 29& X\\ 31& X& X& X& 35& X& 37& X& X& X\\ 41& X& 43& X& X& X& 47& X& 49& X\end{array}$

Continue this way to find all the primes. When do you know you have found all the primes under 50?

Exercise

1.

$\begin{array}{cccccccccc}X& 2& 3& X& 5& X& 7& X& X& X\\ 11& X& 13& X& X& X& 17& X& 19& X\\ X& X& 23& X& X& X& X& X& 29& X\\ 31& X& X& X& X& X& 37& X& X& X\\ 41& X& 43& X& X& X& 47& X& X& X\end{array}$

The prime sieve has been applied to the table above. Notice that every number situated directly below 2 and 5 are crossed out. Construct a rectangular grid of numbers running from 1 to 60 so that after the prime sieve has been performed on it, all numbers situated directly below 2 and 5 are crossed out. What is the width of the grid?

2. Find all primes below 200

Infinitely many primes

One of the most beautiful elementary results in the whole of mathematics is the proof that there are infinitely many primes. The great (but eccentric) mathematician, Erdos, was hooked on mathematics for life when he was told the proof by his father at a young age.

The ancient Greek mathematician Euclid, had the following proof of the infinitude of primes.

Proof of infinitude of primes

Let us first assume that

there are a finite number of primes

therefore

there must be one prime that is greater than all others,

let this prime be referred to as n. We now proceed to show the two assumptions made above will lead to a contradiction, and thus there are infinitely many primes.

Take the product of all prime numbers to yield a number x. Thus:

$x=2\times 3\times 5\times \dots \times n$

Then, let y equal one more than x:

$y=x+1$

One may now conclude that y is not divisible by any of the primes up to n, since y differs from a multiple of each such prime by exactly 1. Since y is not divisible by any prime number, y must either be prime, or its prime factors must all be greater than n, a contradiction of the original assumption that n is the largest prime! Therefore, one must declare the original assumption incorrect, and that there exists an infinite number of primes.

Fun Fact -- Largest known prime

The largest known prime is 2^32,582,657-1. It has a whopping 9,808,358 digits! Primes of the form 2ⁿ-1 are called Mersenne primes named after the French monk/amateur mathematician.