High School Mathematics Extensions/Primes

From Wikibooks, open books for an open world
Jump to navigation Jump to search
HSME
Content
100% developed Primes
100% developed Modular Arithmetic
Problems & Projects
100% developed Problem Set
100% developed Project
Solutions
100% developed Exercise Solutions
50% developed Problem Set Solutions
Misc.
100% developed Definition Sheet
100% developed Full Version
25% developed PDF Version

Introduction[edit | edit source]

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[edit | edit source]

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

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[edit | edit source]

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

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

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[edit | edit source]

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

not a whole number, so 2 is not a factor of 21
hence 3 and 7 are the factors of 21.

Example 2

hence 2 is not a factor of 153
hence 3 and 51 are factors of 153
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

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

Exercise[edit | edit source]

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?[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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. xn 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 xn, we write:

if n equals 0.
if n > 0

What is 99? It is 9 times 9 8. But, 98 is 9 times 97. Repeating this way is an example of recursion.

Exercises[edit | edit source]

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[edit | edit source]

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

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

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

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

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[edit | edit source]

  1. 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[edit | edit source]

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 is the largest natural number, you can immediately prove them wrong by telling them that is a larger natural number. You can substitute with any number other natural number 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[edit | edit source]

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:

Then, let y equal one more than x:

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

Useful Off-site Resources[edit | edit source]

>> Next section: Modular Arithmetic