wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Polynomials semi-good prime generators?  Not!
        
(Message started by: ecoist on Nov 8^th, 2007, 2:12pm)

Title: Polynomials semi-good prime generators? Not!
Post by ecoist on Nov 8^th, 2007, 2:12pm

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.

x²-x+41 is a prime for x=1,...,40 (Euler, 1772)
x²+x+41 is a prime for x=0,...,39 (Legendre, 1798 )
2x²+29 is a prime for x=0,...,28 (Legendre, 1798 )
3n²+3n+1 is a prime for many small values of n (Chabert, 1884)
Source: Dickson's History of the Theory of Numbers, Vol. 1

Title: Re: Polynomials semi-good prime generators? Not!
Post by ecoist on Nov 8^th, 2007, 7:53pm

~~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!

Title: Re: Polynomials semi-good prime generators? Not!
Post by Aryabhatta on Nov 11^th, 2007, 1:01pm

That is a nice result ecoist!

Looks like a toughie...

Title: Re: Polynomials semi-good prime generators? Not!
Post by ecoist on Nov 11^th, 2007, 3:02pm

Thanks, Aryabhatta! Was beginning to think I had posted yet another puzzle that bombed.

Title: Re: Polynomials semi-good prime generators? Not!
Post by Barukh on Nov 15^th, 2007, 3:51am

Here’s one possible approach (in concise form).

[hideb]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+M²) = M’ is divisible by M, but M’/M = 1 mod M. Therefore, P(n+M²) has more prime divisors than P(n).[/hideb]

The same approach can be used to prove the following :

on 11/08/07 at 14:12:09, ecoist wrote:

It was known since forever that no integer polynomial is a prime generator

on 11/08/07 at 14:12:09, ecoist wrote:

x²-x+41 is a prime for x=1,...,40 (Euler, 1772)
x²+x+41 is a prime for x=0,...,39 (Legendre, 1798 )
2x²+29 is a prime for x=0,...,28 (Legendre, 1798 )
3n²+3n+1 is a prime for many small values of n (Chabert, 1884)

x²-79x+1601 is a prime for x=0,...,79.

Title: Re: Polynomials semi-good prime generators? Not!
Post by ecoist on Nov 15^th, 2007, 11:23am

I detect a minor oversight, Barukh. Shouldn't you mention what to do if M'/M equals 1?

Title: Re: Polynomials semi-good prime generators?
Post by towr on Nov 15^th, 2007, 11:35am

on 11/15/07 at 11:23:28, 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?

Title: Re: Polynomials semi-good prime generators? Not!
Post by ecoist on Nov 15^th, 2007, 3:27pm

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.

Title: Re: Polynomials semi-good prime generators? Not!
Post by Barukh on Nov 16^th, 2007, 1:44am

on 11/15/07 at 11:23:28, 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+M²), P(n+2M²), ..., P(n+2dM²). At least one of them is different from both 0 and M.

Nice problem! :D

Title: Re: Polynomials semi-good prime generators? Not!
Post by ecoist on Nov 16^th, 2007, 9:33am

Thanks, Barukh. M<0 is ok too with your approach, and addendum.

Title: Re: Polynomials semi-good prime generators? Not!
Post by Aryabhatta on Nov 17^th, 2007, 3:22pm

Nice proof Barukh!