mersenneforum.org > Math What is the significance of prime numbers?
 Register FAQ Search Today's Posts Mark Forums Read

 2005-08-20, 12:52 #1 Unregistered   22×23×41 Posts What is the significance of prime numbers? Serious question, I'm just wondering what the big deal is with prime numbers... so they can't be divided.. is there something significant with that? Also am I correct in the assumption that there is no real formula which can be used to find out all the prime numbers? other than using some math program which simply just attempts to divide the number to figure out if it's prime or not.. and also other than that 2n-1 which only finds primes here and there...... is there a formula out there which will find each and every prime?
 2005-08-20, 14:56 #2 lycorn     "GIMFS" Sep 2002 Oeiras, Portugal 11·137 Posts If there were such formula, the search for Prime Numbers would be meaningless, don´t you think?...
 2005-08-20, 15:14 #3 Numbers     Jun 2005 Near Beetlegeuse 38810 Posts There is not a formula that will find every prime number, but there is a method. It’s called division. You simply divide your number by every prime lower than it, and if it divides your number is not prime. The trouble with this approach is that for huge numbers it would take years – even with computers - to prove whether a number is prime or not. Mathematicians have therefore developed a lot of clever techniques for determining whether or not a number MIGHT be prime. They then concentrate their efforts – computer time costs money, after all - on those that might be prime. Numbers of the form (2^n)-1 are called Mersenne numbers, and it can be shown that they MIGHT be prime if, and only if, n is prime. That n is prime does not, however, guarantee that (2^n)-1 will be prime. (2^5)-1 is prime, but (2^11)-1 is not. There are other forms of numbers for which similar rules apply. As for the usefulness of prime numbers; do you have a mobile phone, or cash point card, or credit card, or have you ever bought anything over the internet? All of these transactions, and many other things you do every day, rely for their security on the simple fact that it is so hard to find prime numbers in a reasonable amount of time. In very simple terms, take any two prime numbers and multiply them together, and you have a security code that can only be broken with those same two original prime numbers. No other combination will work, ever. In part, that is why prime numbers are so useful, so important, and yet so tantalisingly elusive that searching for them would be interesting and satisfying even if they had no use at all.
 2005-08-21, 00:33 #4 99.94     Dec 2004 The Land of Lost Content 1000100012 Posts If it is a serious question and if you would like to read further on the subject, try Marcus du Sautoy's book: The Music of the Primes.
 2005-08-21, 00:48 #5 Zeta-Flux     May 2003 154710 Posts There are plenty of formulas for giving us each and every prime. They are just usually very complicated, and require the computation of all previous primes. As for the usefulness of prime numbers, one word: cryptography.
 2005-08-21, 10:05 #6 cheesehead     "Richard B. Woods" Aug 2002 Wisconsin USA 22·3·641 Posts (For the sake of newbies) Regarding an apparent contradiction: When some folks say there's no formula for finding every prime number, while other folks say there are formulas for every prime number ... they're both right ... sort of. What's happening is that there are different unstated assumptions in each case. As simple examples, let me offer these slightly-expanded versions: There's no formula for finding every prime number that requires less work than what we usually think of as the standard nonformulaic methods for finding primes. There are formulas for computing every prime number but they require that previous primes have already been found and/or offer no overall shortcut in the amount of work required. Each of those could be stated more rigorously, and there are even more unstated conditions and assumptions that could be added to each. I'll stop here.
 2005-08-21, 12:27 #7 Wacky     Jun 2003 The Texas Hill Country 32×112 Posts Do you mean "formula" or "algorithm" ? They are not the same.
 2005-08-21, 13:08 #8 Peter Nelson     Oct 2004 232 Posts A "formula"? "If there were such formula, the search for Prime Numbers would be meaningless, don´t you think?... " NO, I dont think so (and suspect your wink is made knowingly) As for the suggestion to read "Music of the primes" More specifically see p199/p200 where there is an explicit formula presented which will generate all primes without missing any at all. I agree with Wacky that you might also call it an "algorithm" or means for finding primes, as it also generates 0 or negative values which are answers to be ignored. Any positive result is prime. I quote from du Sautoy: "But could mathematicians find such a formula? In 1971, Matijasevich devised an explicit method for arriving at such a formula, but he did not follow it through to produce an answer. The first explicit formular to be written out in detail used 26 variables A to Z and was discovered in 1976:" It is reproduced and I did type it for you but lost the post :-( However as has been pointed out, to use it would be a lot of work! So, it may not be of practical use, but I found it interesting to read that such a formula did indeed exist! As for significance, being prime tells us that a number can't be divided without a remainder. Thus if I had a prime number of (whatever) I could not share them fairly among members of my family or friends (assuming number of people < the prime). eg if I have 13 footballs, unless there are 1 or 13 people, I will have to start disecting footballs with a knife to share them, and that does tend to ruin them :-)
2005-08-22, 08:48   #9
lycorn

"GIMFS"
Sep 2002
Oeiras, Portugal

11·137 Posts

Quote:
 Originally Posted by Unregistered Also am I correct in the assumption that there is no real formula which can be used to find out all the prime numbers? other than using some math program which simply just attempts to divide the number to figure out if it's prime or not..
The underlined part was the one I was actually answering to. Meaning that if there was a formula (or algorithm) to generate all prime numbers in a comparatively easier way, people wouldn´t be investing time and computer resources in a search activity like GIMPS.

 2005-08-22, 15:23 #10 cheesehead     "Richard B. Woods" Aug 2002 Wisconsin USA 11110000011002 Posts From the MathWorld page for Formula: "In mathematics, a formula is a fact, rule, or principle that is expressed in terms of mathematical symbols. Examples of formulas include equations, equalities, identities, inequalities, and asymptotic expressions." What I had in mind when I wrote "formula" was the sort of equation y = f(x) which gives prime values of y for some range of integer values of x. But the originator's question also makes sense when algorithm is substituted for formula. From the MathWorld page for Algorithm: "A specific set of instructions for carrying out a procedure or solving a problem, usually with the requirement that the procedure terminate at some point. Specific algorithms sometimes also go by the name method, procedure, or technique." Last fiddled with by cheesehead on 2005-08-22 at 15:24
2005-08-22, 16:41   #11
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by cheesehead From the MathWorld page for Formula: "In mathematics, a formula is a fact, rule, or principle that is expressed in terms of mathematical symbols. Examples of formulas include equations, equalities, identities, inequalities, and asymptotic expressions." What I had in mind when I wrote "formula" was the sort of equation y = f(x) which gives prime values of y for some range of integer values of x. But the originator's question also makes sense when algorithm is substituted for formula. From the MathWorld page for Algorithm: "A specific set of instructions for carrying out a procedure or solving a problem, usually with the requirement that the procedure terminate at some point. Specific algorithms sometimes also go by the name method, procedure, or technique."
I have, so far, stayed out of this conversation, because it is generally
lacking in rigor. However, I hope I can clarify and correct some of
the incorrect claims that have been made.

Formulae do exist that will give the n'th prime. However, such formulae
are usually given as summations which require prohibitive calculation.
See, for example, Paulo Ribenboim's "Book of Prime Number Records"

Algorithms do exist for finding the
n'th prime that are much better than finding them all. One applies a
prime *counting* algorithm and then uses binary search.

As for the "algorithm vs. formula" debate, allow me to say that
the difference is often a matter of how much math you know.
Suppose, for example, I state that the answer to some problem is
"y = sin(x)". Most would accept this as a formula because they
*recognize* what sin(x) is, even though to COMPUTE sin(x) requires
an *algorithm*. However, if I said the answer is "y = H(a;b;x)/G(x)"
where H is a hypergeometric function, and G is the gozinta function,
many would not accept this as a "formula" because they do not recognize
the functions. Especially if computing the functions requires a complicated
and expensive algorithm. Both "formula" and "algorithm" are fuzzy
concepts. However, under any reasonable interpretation, expressions
that give the n'th prime as summations involving trig functions and the
(say) factorial function ARE formula.

Furthermore, closed form formulae exist for pi(n), but they are not
elementary; they can be given in terms of contour integrals involving the
zeta function. The most efficient to calculate was given by Odlyzko,
Lagarias et.al. and requires good knowledge of complex function theory.
But the formula itself is simple.

Much of this is hard to explain to newbies because they lack the required
background.

 Similar Threads Thread Thread Starter Forum Replies Last Post VicDiesel Programming 12 2017-04-20 21:16 Arxenar Miscellaneous Math 38 2013-06-28 23:26 Citrix Lounge 5 2010-04-05 21:34 spkarra Miscellaneous Math 3 2009-12-29 00:23 Unregistered Miscellaneous Math 8 2008-11-09 07:45

All times are UTC. The time now is 21:48.

Sun Nov 28 21:48:38 UTC 2021 up 128 days, 16:17, 0 users, load averages: 1.41, 1.48, 1.45