Author |
Topic: Polynomials semi-good prime generators? Not! (Read 640 times) |
|
ecoist
Senior Riddler
Gender: 
Posts: 405
|
 |
Polynomials semi-good prime generators? Not!
« on: Nov 8th, 2007, 2:12pm » |
 Quote  Modify
|
Let p(x) be a polynomial with integer coefficients of degree at least 1. Show that there exists an integer k such that p(k) is divisible by at least 2008 distinct primes.
It was known since forever that no integer polynomial is a prime generator, but many polynomials have been shown to generate a lot of primes.
x2-x+41 is a prime for x=1,...,40 (Euler, 1772)
x2+x+41 is a prime for x=0,...,39 (Legendre, 1798 )
2x2+29 is a prime for x=0,...,28 (Legendre, 1798 )
3n2+3n+1 is a prime for many small values of n (Chabert, 1884)
Source: Dickson's History of the Theory of Numbers, Vol. 1
|
| « Last Edit: Nov 9th, 2007, 4:40pm by ecoist » |
 IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Polynomials semi-good prime generators? Not!
« Reply #1 on: Nov 8th, 2007, 7:53pm » |
Quote Modify
|
I just shocked myself! It seems that an immediate consequence of this little puzzle is a much more serious result: there are infinitely many primes congruent to 1 modulo m, for each integer m>1!
Correction! The proof is simpler without the puzzle!
|
| « Last Edit: Nov 9th, 2007, 6:47pm by ecoist » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Polynomials semi-good prime generators? Not!
« Reply #2 on: Nov 11th, 2007, 1:01pm » |
Quote Modify
|
That is a nice result ecoist!
Looks like a toughie...
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Polynomials semi-good prime generators? Not!
« Reply #3 on: Nov 11th, 2007, 3:02pm » |
Quote Modify
|
Thanks, Aryabhatta! Was beginning to think I had posted yet another puzzle that bombed.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Polynomials semi-good prime generators? Not!
« Reply #4 on: Nov 15th, 2007, 3:51am » |
Quote Modify
|
Here’s one possible approach (in concise form).
| hidden: | | Let n be an integer, and P(n) = M. Then, for every integer k, P(n+kM) is divisible by M (why?). In particular, P(n+M2) = M’ is divisible by M, but M’/M = 1 mod M. Therefore, P(n+M2) has more prime divisors than P(n). |
The same approach can be used to prove the following :
on Nov 8th, 2007, 2:12pm, ecoist wrote:| It was known since forever that no integer polynomial is a prime generator |
|
on Nov 8th, 2007, 2:12pm, ecoist wrote:
x2-x+41 is a prime for x=1,...,40 (Euler, 1772)
x2+x+41 is a prime for x=0,...,39 (Legendre, 1798 )
2x2+29 is a prime for x=0,...,28 (Legendre, 1798 )
3n2+3n+1 is a prime for many small values of n (Chabert, 1884)
|
|
x2-79x+1601 is a prime for x=0,...,79.
|
| « Last Edit: Nov 15th, 2007, 4:27am by Barukh » |
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Polynomials semi-good prime generators? Not!
« Reply #5 on: Nov 15th, 2007, 11:23am » |
Quote Modify
|
I detect a minor oversight, Barukh. Shouldn't you mention what to do if M'/M equals 1?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Polynomials semi-good prime generators?
« Reply #6 on: Nov 15th, 2007, 11:35am » |
Quote Modify
|
on Nov 15th, 2007, 11:23am, ecoist wrote:| I detect a minor oversight, Barukh. Shouldn't you mention what to do if M'/M equals 1? |
|
You can just repeat the step, and if M' perpetually remains M, then P(n) would have to be constant and so doesn't have degree at least 1. Right?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Polynomials semi-good prime generators? Not!
« Reply #7 on: Nov 15th, 2007, 3:27pm » |
Quote Modify
|
Well, towr, there are other irritants as well. What if, during repeats of Barukh's procedure, some successive M's turn out to be 0?. All this can be avoided by choosing the n so that |M|>1 and, for all x>n, p(x) is monotone increasing or decreasing and never zero. Then, Barukh's successive choices for n are strictly increasing and corresponding M's are different from all previous M's.
|
| « Last Edit: Nov 15th, 2007, 4:22pm by ecoist » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Polynomials semi-good prime generators? Not!
« Reply #8 on: Nov 16th, 2007, 1:44am » |
Quote Modify
|
on Nov 15th, 2007, 11:23am, ecoist wrote:| I detect a minor oversight, Barukh. Shouldn't you mention what to do if M'/M equals 1? |
|
Good point, ecoist!
Of course, n should be chosen so that M > 0. But M = 1 will also do: if P(x) has degree d, consider 2d numbers P(n+M2), P(n+2M2), ..., P(n+2dM2). At least one of them is different from both 0 and M.
Nice problem! 
|
| « Last Edit: Nov 16th, 2007, 1:48am by Barukh » |
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Polynomials semi-good prime generators? Not!
« Reply #9 on: Nov 16th, 2007, 9:33am » |
Quote Modify
|
Thanks, Barukh. M<0 is ok too with your approach, and addendum.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Polynomials semi-good prime generators? Not!
« Reply #10 on: Nov 17th, 2007, 3:22pm » |
Quote Modify
|
Nice proof Barukh!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print