Skip to content

Mathematics

The Cali Garmo does Math

Archive

Category: Prime Numbers

When we last left off I had finished talking partially about prime numbers and how to find them. But some of you may have been wondering, how many primes there are in total? Is there some way to maybe find a formula to find a prime number?

If you look at the primes, they seem to go on forever! And thanks to amazing mathematicians from the past we know that they do! But HOW do we know that they actually do? How can you be sure there is a number after 97 that is prime? Some will just point to their computer and say, “Computers can prove that!” and they would be partially right. Computers have helped us find extraordinarily HUGE prime numbers. For example, remember those special prime numbers called Mersenne primes which are primes of the form where p is also prime? Well, a worldwide collaboration was started in order to find the largest prime known to man and they called themselves GIMPS.

The organization is called GIMPS or Great Internet Mersenne Prime Search. You can find their website here: [GIMPS] Quite recently they found the largest prime ever known to man. What is the prime number you may be wondering? It is: . You might be thinking that this looks like a small number, but it really isn’t. This prime is 17,425,170 digits long. That is HUGE! It is so big that if you were to print out the number on paper (without commas) it would be 4,283 pages long!

It took years for the computers to calculate that prime number, so as we questioned earlier, how do we know if there is a prime number greater than this or not? It is so large we can barely use computers to go any higher, and we can forget about writing the number down (you try writing out 4,283 pages of numbers!). So then how can we KNOW if there are infinite number of primes or not? Well this is exactly what a guy named Euclid was pondering over 2,000 years ago.  Euclid was able to prove that there are an infinite number of primes! So no matter how big of a prime number we find, there will always be a bigger one. So cool! But how did Euclid come up with this?

Below is a rough transcript of how Euclid created his proof, but before we go over the proof here a lemma that Euclid uses in order to prove it that you should know:
Lemma 1: Every number greater than 1 can be broken down into multiples of prime numbers. e.g: . Notice that prime numbers just equal themselves, and composite numbers are multiples of primes!

Euclid’s Proof: Suppose that there are only a finite number of primes. This means that there is a number x such that any number greater than x is not prime. All these numbers greater than x thus must be composite and by the lemma we just discussed must be a combination of prime numbers. So if we take every prime number less than x and multiply them together we get a number n. Now if we add 1 to n we get a prime number! (Notice that since 2 is a prime, thus multiplying all the primes together would get us an even number, which would automatically not be prime. So we add 1 to make it an odd number.) Why/how is n+1 prime?! Because no matter which prime number we select and we divide n + 1 by it we will get a remainder of 1. And since we have used every prime number less than x, and every number between x and n are composite, there are no other prime numbers that (n+1) can divide into. So (n+1) must be prime! But, we had stated earlier that x is the greatest prime and since (n+1)>x we see that our earlier thought was wrong (that there are a finite number of primes) and so there must be an infinite number of primes!

[Note: This type of proof is called proof by contradiction. I’ll eventually lay the groundwork for how this works, but for now you can look it up in google if you’d like.]

Wow, that was complex, but so rewarding! We can now for sure state that there are an infinite number of primes! Fun part is, that this was only 1 of many proofs that there are infinite primes! Any questions? Leave a comment!

Questionably yours,
The Cali Garmo

Last week we talked about what a prime number is, but we didn’t talk about a good way of finding what number is prime and what is not [other than checking if any number less than p divides that number]. This area of finding out what number is prime has been a big problem for many mathematicians and still has a lot of unanswered questions. The world of mathematics is still looking for an easy way to calculate whether a number is prime or not with a simple formula.

There are a few ways of finding primes, but the simplest (and one of the oldest) ways to finding a prime is by using a process called ‘the sieve of Eratosthenes’. Take out a piece of paper and make 10 rows and 10 columns and number them in order from 1 to 100. Row 1 should have the numbers 1-10 in order, row 2 should have 11-20 in order, etc. Then, starting from 2, cross out all the numbers that 2 divides without crossing out 2 (e.g. 4, 6, 8, 44, 96). Then go to the next number and cross out all the number that it divides without crossing that number out. (The next number is three so cross out 9, 15, 21, etc.) Then go to the next number not crossed out and cross out all the numbers that it divides without crossing that number out. (5 is the next number so we cross out 25, 35, 55, etc.) We keep going until we find all the primes less than 100. Write down all the numbers in order, and you’ll notice you have the same list that I listed last week! Cool! And that is basically the whole concept behind the sieve of Eratosthenes. You write down all the numbers and you go prime by prime removing all the ones that are not prime by going number by number. So if you wanted to find all the numbers less than 1,000 you would draw a 100 x 100 table of numbers and cross out each one as it came. This can be very time consuming! That’s why mathematicians, didn’t stop there.

A second way to see if a number is prime is to use what mathematicians like to call Wilson’s Theorem. This theorem states that if p is prime then [Remember modulo? We’re basically saying the remainder when you divide p from (p-1)! +1 is 0.] And the theorem goes vice versa, so that if a number that is not prime is placed into the equation the remainder/modulo will not be 0. Kinda handy for looking at medium size numbers!

Another way of finding primes is to find what are called Mersenne primes. These primes were talked about by a French monk Marin Mersenne from the 17th century. They are primes of the form where is the mth Mersenne number. It turns out that this is a good way to find other primes. If the mth Mersenne number is prime the m is also prime. The issue is that this is a little cumbersome and doesn’t work in reverse (If m is prime it does not mean is prime too.)

There are more complex ways of finding primes, but those are some of the most interesting and easy ones. Have a suggestion? Add a comment!

A prime number by definition is a number p>1 such that p has no positive integer divisors other than 1 and p.

Wait… What?

Confuzzling! Let’s try to figure out what that means by breaking it down into smaller parts. Let’s first look at the section ‘is a number p>1’. This part is actually saying 2 things in 1. It’s first stating: let the ‘prime number’ be represented by the symbol ‘p’. So ‘p’ is our variable. It also states that p must be greater than 1. So, so far, p can be 1.1, 2, 940,300, , etc.

The next part says ‘such that p has no positive integer divisors other than 1 and p’. First let’s look at what a ‘positive integer’ is. An integer is any whole number. Basically a number that doesn’t have any decimal part, and no fractions when simplified. So 2, 55, -7, 3.0, , etc. are all integers. A positive integer means basically that the number must be greater than 0. Next let’s see what ‘divisor’ means. A divisor is an integer that divides another number into an integer. So since 2 divides 4 into 2, then 2 is a divisor of 4. Since 3 divides 99 into 33, then 3 is a divisor of 99. So a ‘positive integer divisor of p’ is a number that divides p, is a whole number, and is greater than 0. So if we let p be 4, then 1, 2, and 4 are all positive integer divisors of p.

But, we are stating that p does NOT have any positive integer divisors except for p and 1. So 4 is not prime since 2 is also a positive integer divisor. 2 is a prime number since it is greater than 1, and it’s only positive integer divisors are 1 and 2. 9 is not prime even though it is greater than 1 since it’s positive integer divisors are 1, 3, and 9. 6.5 cannot be prime since it is not an integer.

So by going number by number we can get a huge list of prime numbers:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 …
To name the first few. You can go and look at the long list of prime numbers provided by sloane which is an online encyclopedia of integer sequences (or integer patterns). Here is a link: [Sloane]

At about this point you may want to exclaim ‘Wait a second! What about the number 1?! It can only be divided by 1 and itself too, why is 1 not classified as a prime?’ Originally the number 1 was considered a prime number, but a lot of mathematical concepts that have to deal with primes usually turned out funky when dealing with the number 1. When 1 was considered a prime, the concepts worked perfectly sometimes, but failed at other times, but they all succeeded if the number 1 was not considered a prime or a composite. So instead of keeping it as a prime number, it was eventually relegated to be just a number, neither prime nor composite (explained in a few!) That is why if you pay close attention to our definition we say our prime p has to be greater than 1.

So we mentioned that the number 1 cannot be composite either, what’s composite?! A composite number is just an integer c > 1 such that c is not prime. With all the information I gave you above, I’m sure you can figure this one out =D

So that’s the main concept behind prime numbers. Want to learn more of have any questions? Leave a comment!

Questionably yours,
The Cali Garmo