What the dilio with prime, anyway?

[Ensign Steve]

I wanted to get married on July 10, because 10 is such a nice round, even number. I mean, we count in base fickin' ten. What an awesome number to multiply by, divide by, add, subtract. Logs, scientific notation, and the metric system rule! Our choices were the 10th or the 11th, and I argued for the 10th for those reasons. My husband retorted with, "Yeah, but 11 is prime."

Huh? So what? What is so special about prime? All I know is that it can't be evenly divided by anything (except for blah blah) and you can't make a proper die with that number of sides (unless you count a coin), thank you very much, AD&D! And mathy-type people like to see how large of a number of them they can come up with. I don't remember if its been determined if there's an infinite number of them yet. At any rate...

Why? Who cares? Except for not making a die, what can you do with prime numbers? Make it interesting, but not too technical, and if you have time, funny.

Thanks!

(edit: ps, we got married on the 10th. duh ;) )

[seebs]

Yes, there are an infinite number of them. The proof is about half a paragraph.

They're useful because if you multiply two very large primes together, you get a number with only two factors, where finding either factor can be fairly hard, and this can be used in cryptography.

[Godless Wonder]

because 10 is such a nice round, even number. I mean, we count in base fickin' ten. What an awesome number to multiply by, divide by, add, subtract. Logs, scientific notation, and the metric system rule! Our choices were the 10th or the 11th, and I argued for the 10th for those reasons.

My husband retorted with, "Yeah, but 11 is prime."

Huh? So what?

Maybe "Yeah, but 11 is prime" is your husband's way of saying... "Huh? So what?"

[Goliath]

I don't remember if its been determined if there's an infinite number of them yet.

Indeedely-do there are! This was proven by Euclid in The Elements about 2500 years ago.

Theorem: There are infinitely many primes.

Proof: Suppose that there are only finitely many primes. Let's call them p_1, p_2, ..., p_n (remember: we're assuming that these are all of the primes).

Let x=p_1*p_2*...*p_n+1 (that is, x is one more than the product of all the p_i's). Since x>1, x can be factored (uniquely) into prime integers. However, our only primes are p_1, p_2, ..., p_n.

However, p_1 doesn't divide x, because if we try to divide p_1 into x using long-division, we end up with a remainder of 1. Similarly, x isn't divisible by any of p_2, ..., p_n, either. So, since x isn't divisible by any of p_1,..., p_n, it must follow that x is primes. But then x isn't in our list of primes that we started with. That is a contradiction. Therefore our initial assumption (namely that there are only finitely many primes) was wrong, whence there are infinitely many primes. QED

Now, here's a brainteaser for ya: If p and q are prime integers with p<q, we call (p,q) a pair of twin primes if q-p=2 (examples of pairs of twin primes include (5,7), (11,13), (17,19), and (29,31)). So, are there infinitely many pairs of twin primes?

The Twin Primes Conjecture states that there are infinitely many pairs of twin primes, but the Twin Primes Conjecture has yet to be proven (or disproven) and it's stood open for...oh...probably a couple hundred years, now.

[seebs]

To be very picky, it is dimly possible that x is in fact, not prime, but rather, the product of p_y and p_z, where both y and z are greater than n.

In short, someone might notice that there exist sets of primes p_1...p_n such that their product, plus one, is not actually prime, and think this is a hole in the proof, but it's not; the factors are still larger than any prime on the list.

[Goliath]

Oh, and as for uses, seebs hit on one of the biggies: encryption. It turns out that factoring integers is a computationally tough thing to do. Feed really large integers into a computer (I'm not talking about paltry 7 or 8 digit numbers...we're talking thousands of digits or more) and it takes a lot of time for computers to factor them.

Many of the most difficult open problems in Number Theory have to do with prime numbers. For example, when you reach a prime number (say 31), how do you know when you'll get to the next one? The Riemann Hypothesis (arguably the most difficult and most notorious open problem in Mathematics today) consists of a function that gives the distribution of the primes.

Also, in a more abstract sense, prime elements play a very important part in Factorization Theory (which happens to be one of the nooks of Mathematics that I do work in).

And besides, 8,675,309 is a prime number. How cool is that?! :cool:

[JoeP]

July is the 7th month and 7 is prime, so you get the best of both.

None of this was any influence in me getting married on July 10th as well (7-10). Nor on my daughter being born on October 7th (10-7).

[Goliath]

To be very picky, it is dimly possible that x is in fact, not prime, but rather, the product of p_y and p_z, where both y and z are greater than n.

Ah, but in the proof there were no indices larger than n.


In short, someone might notice that there exist sets of primes p_1...p_n such that their product, plus one, is not actually prime, and think this is a hole in the proof, but it's not; the factors are still larger than any prime on the list.

Yep...given the first n primes, you can always multiply them together, then add 1 and get another prime. However, not all primes are produced this way. For example, if we only take 2, 3, and 5 (the first three primes), then 2*3*5+1=31, but there are primes between 5 and 31 (namely 7, 11, 13, 17, 19, 23, and 29).

[livius drusus]

Three things:
Y'all are way smart.
This thread is cool.
I keep seeing "dildo" in the title.

:cheerful:

[JoeP]

Back to the op, the dildo with primes is that they're just cool.

This bears no relation to the aforementioned statement, but I recall - when I was at IBM for a temporary job (9 months before university) being trained in APL and the guru getting all excited (OK, I got excited too) about writing a one-line program to enumerate all primes up to a given integer. I can't type it here due to the special characters, but by curious chance the wikipedia entry (http://en.wikipedia.org/wiki/APL_programming_language) has an example as a graphic.

[ceptimus]

Actually, 10 only seems like a nice number because we use it as our number base, presumably because of our 10 fingers (including thumbs). Whatever number we choose as our base would have the same properties for multiplying and dividing, logarithms, scientific notation and so on.

12 would have been a much better choice than 10, as 12 is divisible by 2, 3, 4, and 6, whereas 10 only divides by 2 and 5. If evolution had given us a couple of extra fingers, we would be able to divide dollars exactly into thirds and sixths.

If we did have a number base of 12, it would actually still be written as 10, and 100 would be one gross (144). We'd need a couple of extra symbols to represent the numbers 10 and 11 in a single character, and then we'd be laughing.

The advantages of base 12 are actually used now in some areas. Clocks go up to 12, eggs and other consumable items are often packed in dozens, there are 12 members on a jury, and so on.

The old British money system had 12 pennies in a shilling and 20 shillings in a pound. This was discarded in favour of a decimal system in 1971, so it couldn't have been all that good, but it did have the advantage of allowing a pound to be split into many fractions evenly. A third of a pound was 'six and eightpence' then. We can't do that anymore. :(

[seebs]

Yep...given the first n primes, you can always multiply them together, then add 1 and get another prime.

Really? It's never the product of two numbers larger than p_n?

[ceptimus]

2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 + 1 = 9699691

9699691 = 347 x 27953

[Goliath]

Three things:
1. Y'all are way smart.
2. This thread is cool.


:blush:


3. I keep seeing "dildo" in the title.[/list]

:cheerful:

LOL...I did, too. :lecher: :D

[Goliath]

Yep...given the first n primes, you can always multiply them together, then add 1 and get another prime.

Really? It's never the product of two numbers larger than p_n?

Whoops! Nevermind! I tried to sit down to prove this, but then I started tinkering around with Mathematica and found out that 2*3*5*7*11*13+1=59*509.

:doh:

[Goliath]

2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 + 1 = 9699691

9699691 = 347 x 27953

Yep, there's another counterexample.

Okay, I feel like a complete doofus, now.

[xouper]

Many of the most difficult open problems in Number Theory have to do with prime numbers. For example, when you reach a prime number (say 31), how do you know when you'll get to the next one? The Riemann Hypothesis (arguably the most difficult and most notorious open problem in Mathematics today) consists of a function that gives the distribution of the primes.
I see that phrase often, "distribution of the primes". Is it just me or is the word "distribution" somewhat misleading in that context? Likely it's just me. :)

For example, does the Riemann Hypothesis help us find a Prime Counting Function (http://mathworld.wolfram.com/PrimeCountingFunction.html) f(n) that returns exactly the number the primes less than or equal to n? Would that not be useful as a simple test for the primeness of n?

In other words, if and only if f(n) = k and f(n-1) = k-1

where n and k are both positive integers, then n is prime.

Pardon my use of f as the function name instead of the more traditional Pi, but I do it for the non-math people here. I blame Landau [1909] for overloading the greek letter Pi, and making us explain that Pi(x) has nothing to do with circles. :)

Does the Riemann Hypothesis give us such a function? What am I missing here?

That's what comes to mind when I see the phrase "distribution of primes", in that such a function tells us exactly where every prime is. And that's why I feel disappointed that the Prime Number Theorem (http://mathworld.wolfram.com/PrimeNumberTheorem.html) (PNT) gives only an approximation of the distribution of the primes.

PNT says: f(n) is approximated by n / ln(n)

Using that approximation, if f(n) = x and f(n-1) < x

that still doesn't tell us if n is prime.

As I understand it, the Riemann Hypothesis does not give an exact error term to the PNT, and thus does not lead to an exact distribution of the primes. Am I misunderstanding something here?

[xouper]

2*3*5*7*11*13+1=59*509
Whenever I see this example, or something simlar, I get a nagging suspicion that it contains a heretofore undiscovered and hugely important insight into the nature of prime numbers. Can't think what that might be, though. Perhaps something to do with a relationship between primes and addition (as opposed to the traditional relationship between primes and multiplication).

I get the same nagging suspicion with Fermat's factorization method (http://mathworld.wolfram.com/FermatsFactorizationMethod.html).

[seebs]

2 x 3 x 5 x 7 x 11 x 13 x 17 x 19 + 1 = 9699691

9699691 = 347 x 27953

Yep, there's another counterexample.

Okay, I feel like a complete doofus, now.

Heh. Don't feel too bad, I make the same mistake about every five years. :P

I still remember my parents spending about 20 minutes trying to explain the idea of factors not on the list.

[JoeP]

Actually, 10 only seems like a nice number because we use it as our number base, presumably because of our 10 fingers (including thumbs). Whatever number we choose as our base would have the same properties for multiplying and dividing, logarithms, scientific notation and so on.

12 would have been a much better choice than 10, as 12 is divisible by 2, 3, 4, and 6, whereas 10 only divides by 2 and 5. If evolution had given us a couple of extra fingers, we would be able to divide dollars exactly into thirds and sixths.

If we did have a number base of 12, it would actually still be written as 10, and 100 would be one gross (144). We'd need a couple of extra symbols to represent the numbers 10 and 11 in a single character, and then we'd be laughing.

The advantages of base 12 are actually used now in some areas. Clocks go up to 12, eggs and other consumable items are often packed in dozens, there are 12 members on a jury, and so on.

The old British money system had 12 pennies in a shilling and 20 shillings in a pound. This was discarded in favour of a decimal system in 1971, so it couldn't have been all that good, but it did have the advantage of allowing a pound to be split into many fractions evenly. A third of a pound was 'six and eightpence' then. We can't do that anymore. :(
www.dozenalsociety.org.uk
Dozenal Society of America (www.dozens.org)
http://www.google.com/search?q=dozenal

[ceptimus]

Write consecutive integers in a square spiral (starting with any number you like) and the primes tend to fall on straight lines.

http://www.sciencenews.org/articles/20020504/f1643_1130.gif

(image linked from this Prime Spirals (http://www.sciencenews.org/articles/20020504/mathtrek.asp) page.)

How much of this is just an artifact of diagonal lines consisting of odd or even numbers I'm not sure.

[Dingfod]

Aw, just get married on 7/11 or at 7-Eleven on 7/11, it's a prime location.

[JoeP]

:faint:

[Ensign Steve]

They're useful because if you multiply two very large primes together, you get a number with only two factors, where finding either factor can be fairly hard, and this can be used in cryptography.

Oh, and as for uses, seebs hit on one of the biggies: encryption. It turns out that factoring integers is a computationally tough thing to do. Feed really large integers into a computer (I'm not talking about paltry 7 or 8 digit numbers...we're talking thousands of digits or more) and it takes a lot of time for computers to factor them.

Oooooohhh... encryption! That's cool and definitely useful. That more than answers my "so what" question, but outside of encryption and not making dice, is there anything else they can do? Cryptography is enough, I swear, but now my interest is piqued!

Many of the most difficult open problems in Number Theory have to do with prime numbers. For example, when you reach a prime number (say 31), how do you know when you'll get to the next one? The Riemann Hypothesis (arguably the most difficult and most notorious open problem in Mathematics today) consists of a function that gives the distribution of the primes.

Yeah, but this again falls under my original "who cares" issue. You have to care about primes in the first place before you can even begin to care how they're distributed.

And besides, 8,675,309 is a prime number. How cool is that?! :cool:

Oh yeah! I knew that, too. I heard it on the radio. Cool, indeed! :cool:

[xouper]

(image linked from this Prime Spirals (http://www.sciencenews.org/articles/20020504/mathtrek.asp) page.)
On that page you linked to, is this question:

What happens with other algorithms for numbering the squares? On hexagonal and other types of grids?

Here's one such answer, wrap the primes (and the squares of primes) around a 24 hour clock:

http://www.xoup.net/img/156a.jpg

Image pilfered from page 156 of Peter Plichta's crackpot book God's Secret Formula (http://www.plichta.de/english/english.php?b_5).

For each prime p greater than 3, there exists an integer k, such that

p2 = 24k + 1

Or to say it another way:

p2 is congruent to 1 (modulo 24)

Or to say it yet another way:

p2 / 24 always gives a remainder of 1.

The proof of that is short and straightforward, although Plichta never gives the proof in his book.

In the above diagram, you can also see that all primes greater than 3 are on just eight radials (resembling a cross), but contrary to what Dr. Plichta seems to think, this is a rather trivial result, since all the other radials are divisible by either two or three. In fact, Plichta's entire "Secret Formula" is a trivial result.

Forget Plichta, I only mention him because I pilfered the diagram from his book. :innocent:

[livius drusus]

Wow. That is just plain beautiful. :bow:

[ceptimus]

Why is 25^2 on the diagram? :eh?:

[xouper]

Why is 25^2 on the diagram? :eh?:
Good question. I had to go back and read that section again in his book. Plichta was actually using that particular diagram to make some point about the following sequence of pairs of numbers (not necessarily prime) of the form 6n-1 and 6n+1 for n = 1,2,3,4,5:

(5,7) (11,13) (17,19) (23,25) (29,31)

Sorry about that. It's the only diagram in the book that shows the squares of primes on a single radial. Perhaps I should edit the diagram to remove the 252, or just create my own diagram from scratch and then I won't have to credit Plichta as the source.

[xouper]

I edited the image, and now it only goes up to 192, which still gets the point across but wthout taking up so much screen space.

[Ensign Steve]

This is belated, as I meant to quote this in my first response, but I forgot. Still, it bears posting now that I have remembered to do so. Long story short...

Actually, 10 only seems like a nice number because we use it as our number base, presumably because of our 10 fingers (including thumbs). Whatever number we choose as our base would have the same properties for multiplying and dividing, logarithms, scientific notation and so on.

Good point! ;)

[Crumb]

Nor on my daughter being born on October 7th (10-7).

Hmm, I and your daughter share a birthday...for whatever that's worth. :P