HSME |
Content |
---|
Primes |
Modular Arithmetic |
Problems & Projects |
Problem Set |
Project |
Solutions |
Exercise Solutions |
Problem Set Solutions |
Misc. |
Definition Sheet |
Full Version |
PDF Version |
Contents |
IntroductionEdit
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 arithmetics.
Geometric meaning of primesEdit
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 ArithmeticEdit
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?
FactorizationEdit
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.
ExerciseEdit
Fun Fact — Is this prime?Edit
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 3Edit
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 3Edit
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 — RecursionEdit
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^{n} 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^{n}, we write:
- if n equals 0.
- if n > 0
What is 9^{9}? It is 9 times 9 ^{8}. But, 9^{8} is 9 times 9^{7}. Repeating this way is an example of recursion.
ExercisesEdit
Finding primesEdit
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
ExerciseEdit
- Find all primes below 200.
- Find the numbers which are divisible by 3 below 200. Did you change the width of your grid?
Infinitely many primesEdit
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 primesEdit
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 2^{43,112,609}-1. It has a whopping 12,978,189 digits! Primes of the form 2^{n}-1 are called Mersenne primes named after the French monk/amateur mathematician.