Could someone direct me to some info on formulas of the form x^2 + x + n, (such as Euler’s famous formula with n=41)? Is it known whether there are an infinite number of n such that 0<=x<n will always give a prime #?
-Ben
If you found a way to generate primes as high as you wanted, you’d be a rich, rich (well, famous anyway) man. There isn’t a way; that’s why we have to find them, rather than generate them.
This is what you’re asking, right?
For the RSA encryption algorythm (what you browers uses for secure web pages) you need really big prime numbers. They choose a random number and test it to see if it is prime. They then choose another random number less than the first and see if it has a commond devide withthe first one if it does the first one is not prime and they choose another. If it is not they calculate the jacobi symbol of the two numbers (read the book). if it equals a^(p-1)/2 then it is not prime choose another number otherwise there is a 50% change it is prime. Keep choosing the second number until you have a good confidence that the first number is prime.
I had always wondered how they got these big prime numbers for these public key encyption schemes. When I found out the answer I was just amazed at the idea that math people would choose a number and say yah that one is probably good enough.
The book is Applied Cruptography second edition by Bruce Schnier page 258.
I don’t think thats what Ben is getting at.
If it is, here is a formula for generating SOME primes, which can be as large as you want. The key is this will not generate ALL primes, consequently it will not get you rich nor famous (plus the formula is well known):
Find the product of all primes up to some number and add one. That number is a prime. for example:
235*7+1=211 Ten bucks says there are no prime roots of 211.
A little modular algebra and this is not a difficult theorem to prove.
Evidentally, the OP refers to another such formula (I’m not sure of this, I’ve never seen this before and the proof is not obvious):
X^2+X+41=a prime number for all x between 0 and 41. I belive Ben’s question is asking weather there are numbers other than 41 that make this formula true. Specifically, is there an inifinite set of numbers that could go in place of the 41. Is that right Ben?
Couldn’t this formula generate some really enormous prime numbers?
Huge prime equals large number plus or minus one.
I don’t know if I can prove mathematically that that’s a prime, but it seems pretty obvious that it must be one. Someone must already have thought of this though.
2000! - 1 = ?
I had a formula for finding primes when I was about 14 or 15 I figured out on my own, I never tested it very high so it may have failed further up. I wish I could remember it.
Sorry for the length, this does not answer the OP.
Unfortunatley, 2000!-1 is probably not prime. The trick is
(2000!-1)/k=(2000!)/k+1/k
Each of the terms on the right side can be thought of as having an interger component and remainder.
(2000!)/k+1/k = (A+y)+(B+z)
where A and B are both intergers (in fact, B is zero in this case)
The catch is there is likley to be a k such that adding the two remainders together will give you a interger, hence there is likley a k that evenly divides into (2000!-1) (since all you’d be left with is the sum of three intergers, A, B and y+z).
y+z=I for some k implies
(2000!-1)/k=C where C is an interger,
I actually don’t have the means to check if (2000!-1) is prime (it might be), but is no more likely to be so than any other large odd number (and remember, the larger the number, the less likley it is that number is prime).
Another way to look at this is all large numbers, prime or not, are a large even number plus or minus 1.
When I was younger I also came up with a simple formula for finding primes (maybe it is the same one): multiple all the primes up to a number and add another prime less than the product of the primes times the next prime. For example:
235+13=43. 13 being less than 235*7
Unfortunatly, this fails at 77
235+43=77. 43 is less than 235*7, but 77 is not prime.
As I recal it produces every prime or square of a prime less than 77, though (it also fails to predict 79).
I really doubt that’s true. The standard proof of the infinitude of the primes would be to say that number has a new prime divisor (distinct from the primes in the product), but not that it, itself, is prime.
As for the OP, it’s definitely known that no polynomial can produce only primes. There’s no limit to how many primes a polynomial can give–In principal, it would be trivial to construct a polynomial that gives the first, second, third,…,nth primes when you plug in 1,2,3,…,n, but it can’t do it for infinitely many values.
About x[sup]2[/sup] + x + 41, from this page:
So I have my doubts you’ll find any n that gives that polynomial any nicer properties than 41.
:eek: Damn, you right.
Guess that’s why they pay you the big bucks
I seem to remember reading years ago in the Guinness Book of World Records that the formula 2[sup]n[/sup]-1 where n was a prime number would yield another prime; they’d used it to determine the primeness of some monster huge number and declared it the largest known prime number at the time.
What say you, mathematicians? This formula get disproven?
Olentzero: If 2[sup]n[/sup] - 1 is prime so is n, but the reverse is not true.
See Mersenne primes.
I think that you are remembering Fermat’s little theorem incorrectly. This can be used as a test for the primeness of other numbers.
Fermat’s Little Theorem states that if p is a prime which does not divide the integer a, then a^(p-1) = 1 (mod p).
Therefore if a^(p-1) <> 1 (mod p), p isn’t prime.
Unfortunately there are non-primes which fit this test (one version of a pseudoprime), so it isn’t an ‘if and only if’ test.
pan
Actually jcgmoi is more on the nose with what you are likely to be thinking of (I forgot about Mersenne primes). My info is still correct though!
pan
Just to re-emphasise - I too am almost certain that knowing how to manufacture new primes at will is one of the great unsolved problems in mathematics.
pan
So what’s the largest known prime number?
After scanning jcgmoi’s link, it appears to me like that number is
2[sup]6972593[/sup]-1
which is a number with almost 2.1 million digits.
Am I interpreting that page correctly?
Back to Ben’s OP. I recall reading that Euler’s formula was evaluated ‘best’ in the sense that it yielded a greater percentage of primes than any similar polynomial (for reasons Cabbage alluded to), but I’m damned if I can find the reference.
You might investigate n[sup]2[/sup] - 79 n + 1601 which is prime for 0<= n <= 79, and for many other values as well.
Then there’s Matijasevic’s (or Matyasevich’s) polynomial in 26 variables whose positive values are the set of prime numbers. See.
Thanks guys! I’ve found that X^2 + X + 17 works for all 0<=X<17. This, like Euler’s formula, generates 100% primes for its working range. I’m afraid I don’t know ring theory, so I don’t understand the bit about 163.
To phrase my question more specifically, is it known whether there are a finite number of n for which x^2 + x + n gives primes for all integer x such that 0<=x<n? Clearly we don’t know whether there are an infinite number, because the n that work are a subset of the set of twin primes. However, this leaves open the possibility that the number of n that work perfectly (ie no composite numbers in the appropriate range of x values) might have been proven to be finite.
I have also heard of a proof that for some a, a^(3^n) gives prime numbers for all n. Unfortunately, the value of a isn’t known. Am I missing something here? I don’t see how this equation can work- the value for n=2 can’t be prime, because it’s the square of the n=1 value. Is “a” complex or something?
-Ben
Is this really an issue in the case of testing Mersenne primes? If you combine Fermat’s little theorem with Euler’s phi function, you get a formula whose name I have forgotten, but which can be used to factor large numbers of the form x^y - 1 very easily. If the potential Mersenne passes FLT, then you could try factoring it, right?
To be precise, I’m asking whether it is the case that pseudoprimes will also foul up the factoring process which uses FLT and the phi function.
-Ben
ben said:
This formula was first investigated by Legendre. You’ll find some other formulae there.
You’re omitting the floor function. This is way beyond my ken but see Mills’ theorem.
I’ve found a remarkable formula that generates only primes. However, there is not enough space in this reply frame to write out the proof.
