## Friday, April 20, 2007

### How do we know there are infinitely many primes?

So, while on the EL last night and this morning I thought about why there are infinitely many prime numbers. Why is this true? I’m trying to figure it out on my own first before I read the answer.

I have a lot of questions about primes now to explore:

1. Is there a relationship between one prime and the next prime? If there were this relationship, then we could create an algorithm that will generate new ones from the last one. However, I think there is not a relationship like this. I also think this relates to cryptography algorithms.

2. How do we generate large prime numbers? How do we find them? I wonder if we have to use a large super computer and I bet we do. How do we know a large number is prime?

3. I wonder what kind of program I could write to generate primes and how many I could find and how long it would take. I will try to write one and see what happens. The only idea I have is the brute force method. I’ll write that and then see if I can find tricks others have found on the internet.

4. Finding primes and taking an integer and decomposing it into prime numbers are related. If we could write a computer program to quickly factor integers into prime numbers then we would quickly know if that number was prime or not. Again, I bet we can’t do this.

Some sites I want to read and digest:
http://en.wikipedia.org/wiki/Integer_factorization
http://en.wikipedia.org/wiki/Factorization#Prime_factorization_of_an_integer
http://en.wikipedia.org/wiki/Prime_number

5. Is there a pattern between primes or is it totally randomly dispersed? I think there is no pattern.

6. I have some questions about odd and even numbers to explore. Like if you multiply two odds what happens, two evens, and odd and an even? Are there patterns here like there are with adding?

All of this is a lot of interesting stuff, but I’m still at a loss for why it is true that there are an infinite number of primes! I am very curious now to see the proof but I’ll try to figure it out on my own for longer as it will make reading the proof even more enjoyable. I’m in such awe for these proofs! How did these people come up with these proofs? Amazing stuff.