

Title: f(n)  2^n  1 Post by Eigenray on Mar 15^{th}, 2008, 2:36pm Determine all integer polynomials f such that f(n)  2^{n}  1 for all n > 0. 

Title: Re: f(n)  2^n  1 Post by Obob on Mar 15^{th}, 2008, 4:49pm If there are infinitely many Mersenne primes, then [hide] either f(n) = 1 or f(n) = 1 for all n [/hide] . Since we don't know if there are infinitely many Mersenne primes or not, if the problem has an answer then this is it. 

Title: Re: f(n)  2^n  1 Post by Eigenray on Mar 20^{th}, 2008, 5:07pm Yes, that is the answer. Hint: What do you know about f(p) when p is prime? 

Title: Re: f(n)  2^n  1 Post by Eigenray on Jul 16^{th}, 2008, 3:01pm Looks like I forgot about this one. I guess that was a bad hint. I should have said: what do you know about the prime factors of f(p) when p is prime? 

Title: Re: f(n)  2^n  1 Post by Aryabhatta on Mar 14^{th}, 2009, 1:08pm Almost a year! 

Title: Re: f(n)  2^n  1 Post by Eigenray on Mar 14^{th}, 2009, 2:45pm Well, what do you know about the prime factors of f(p) when p is prime? Further hint: [hide]Dirichlet[/hide] 

Title: Re: f(n)  2^n  1 Post by Obob on Mar 14^{th}, 2009, 4:15pm If q is a prime divisor of 2^p1, for p prime, then 2^p = 1 (mod q). Hence p is a multiple of the order of 2 in (Z/qZ)*, and since p is prime actually p is the order of 2 in (Z/qZ)*. This implies p  q1, so kp = q1 for some k, and q = kp+1 for some k. I'm not sure where this is going. 

Title: Re: f(n)  2^n  1 Post by Eigenray on Mar 14^{th}, 2009, 6:51pm So q can't divide very many values f(p), can it? 

Title: Re: f(n)  2^n  1 Post by Obob on Mar 15^{th}, 2009, 4:47pm Ah. Suppose the prime q other than p divides f(p) for some prime p, so that f(p) = 0 (mod q). In Z/qZ, we have the identity f(p+kq) = f(p); see this at the level of monomials by applying the binomial theorem. Letting k vary, the expression u = p+kq is prime infinitely often by Dirichlet's theorem since p != q, so q divides f(u) for infinitely many primes u. But q > u for all such primes u by my previous post, a contradiction. This forces the only prime factor of f(p) to be p for each prime p. But again by my previous post p never divides 2^p1. Thus in fact f(p) = + 1 for each p, from which we easily conclude that either f(n) = 1 for all n or f(n)= 1 for all n. That was a nice problem. Number theory isn't really my thing, but this was fun to think about. (I do algebraic geometry, preferably in characteristic 0) 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 