High School Mathematics Extensions/Primes

High School Mathematics Extensions

---

Supplementary Chapters — Primes and Modular Arithmetic — Logic

Mathematical Proofs — Set Theory and Infinite Processes — Counting and Generating Functions — Discrete Probability

Matrices — Further Modular Arithmetic — Mathematical Programming — Markov Chains

HSME
Content
Primes
Modular Arithmetic
Problems & Projects
Problem Set
Project
Solutions
Exercise Solutions
Problem Set Solutions
Misc.
Definition Sheet
Full Version
PDF Version

Introduction

A prime number (or prime for short) is a natural number that has exactly two divisors: itself and the number 1. Since 1 has only one divisor — itself — we do not consider it to be a prime number but a unit. So, 2 is the first prime, 3 is the next prime, but 4 is not a prime because 4 divided by 2 equals 2 without a remainder. We've proved 4 has three divisors: 1, 2, and 4. Numbers with more than two divisors are called composite numbers.

The first 20 primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, and 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 arithmetic.

Geometric meaning of primes

The first three figures on top show the different ways to assemble 12 square floor tiles into a rectangle. The bottom three shows that seven cannot be fully divided by two, the image on the left, or three, the image on the right.

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{matrix}12&=&12\times 1\\&=&6\times 2\\&=&4\times 3\\\end{matrix}}$

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 or a hypothesis.

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{matrix}99&=&3&\times &3&\times &11\\52&=&2&\times &2&\times &13\\17&=&17&\end{matrix}}$

It can be easily seen that a composite number has more than one prime factor (counting recurring prime factors multiple times).

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$

${\frac {x}{2}}=10.5$ not a whole number, so 2 is not a factor of 21

${\frac {x}{3}}=7$ hence 3 and 7 are the factors of 21.

Example 2

$x=153$

${\frac {x}{2}}=76.5$ hence 2 is not a factor of 153

${\frac {x}{3}}=51$ hence 3 and 51 are factors of 153

${\frac {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

${\frac {2057}{2}}=1028.5$

$\cdots$

${\frac {2057}{11}}=187$

${\frac {187}{11}}=17$

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

Exercise

Factorise the given numbers below

1

13=

2

26=

3

59=

4

82=

5

101=

6

121=

7 Give up if it takes too long. There is a quick way.

2187=

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⁹? It is 9 times 9 ⁸. But, 9⁸ is 9 times 9⁷. Repeating this way is an example of recursion.

Exercises

For questions 1-3, factorize:

1

45=

2

4050=

3

2187=

4 Show that the divisible-by-3 theorem works for any 3 digit number.

(do it on paper)

5 A number is divisible by 9 if and only if the sum of its digits is divisible by 9.

	True
	False

Determine whether the numbers for questions 6-9 are divisible by 9.

6 89

	Yes
	No

7 558

	Yes
	No

8 51858

	Yes
	No

9 41857

	Yes
	No

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{matrix}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{matrix}}$

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

${\begin{matrix}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{matrix}}$

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{matrix}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{matrix}}$

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{matrix}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{matrix}}$

Continue this way to find all the primes. When do you know you have found all the primes under 50? Note that this algorithm is called Sieve of Eratosthenes

Exercise

1. $${\begin{matrix}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{matrix}}$$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.
3. Find the numbers which are divisible by 3 below 200. Did you change the width of your grid?

Infinitely many primes

To answer the question what is the largest prime number? let us first answer what is the largest natural number? If somebody tells you that $10^{10}$ is the largest natural number, you can immediately prove them wrong by telling them that $10^{10}+1$ is a larger natural number. You can substitute $10^{10}$ with any number other natural number $n$ and your argument will still work. This means that there is no such thing as the largest natural number. (Some of you might be tempted to say that infinity is the largest natural number. However, infinity is not a natural number but just a mathematical concept.)

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 \ldots \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^82,589,933-1. It has a whopping 24,862,048 digits! Primes of the form 2ⁿ-1 are called Mersenne primes named after the French monk/amateur mathematician.

Useful Off-site Resources

• "The Prime Pages. Prime Number Research, Records, and Resources"

>> Next section: Modular Arithmetic