The Cali Garmo Does Math

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 17^th century. They are primes of the form where is the m^th Mersenne number. It turns out that this is a good way to find other primes. If the m^th 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

Modulo! Mod you who? Modulo: A complicated way to say the remainder when you divide two numbers!

So what is modulo exactly and how does it work? The easiest way to break it down is to look at an equation:

What this means is that basically if you take a and divide m then you get a remainder of b. Let’s try a few examples to understand it better. Say and . Then So . Therefore we have the modulo equation: We can do the same with negative numbers! Let and let again. So now we have: . So we have and

Well, that was simple you may be thinking, but when would I use stuff like this in real life?! We actually use it DAILY without even knowing it! Want a quick example? Just look at a clock. What happens after you hit 12:59 (or 23:59 for some of you)? It goes straight to 1:00 (or 0:00). We use modulo to keep track of time! If its 3:00 right now and we go 30 hours in the future, then what time is it? Well we have and Then [or] and we have that the time is b which is 9!

What else can we do with modulo in the world of mathematics? Well it turns out that with such a simple concept we can actually compose a whole lot of theorems! Here are some theorems to keep you entertained. If you dare, try and prove them! (Note for those who try and attempt these, proofs require additional knowledge in division and how certain numbers divide other numbers.)

Theorem 1:
Let a, b, l and m be integers and let l and m be greater than 0. Now let . With this information we can show that

Theorem 2 (By John Wilson):
Let p be prime. Then

Theorem 3 (By Fermat):
Let p be prime and a be a whole number that is not divisible by p. Then

These theorems go on and on and there are hundreds that span from the concept of modulo. In the real world we also use modulo when it comes to creating/breaking codes, ISBN numbers, computer programming languages, and a ton of other places you probably never thought of!

For a good introduction to these types of numbers look to the following book: Elementary Number Theory and its applications by Kenneth H. Rosen (AT&T, 2005)