wu :: forums « wu :: forums - f(n) | 2^n - 1 » Welcome, Guest. Please Login or Register. Jun 8th, 2023, 11:35am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: Icarus, Eigenray, william wu, towr, Grimbal, SMQ)    f(n) | 2^n - 1 « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: f(n) | 2^n - 1  (Read 1396 times)
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 f(n) | 2^n - 1   « on: Mar 15th, 2008, 2:36pm » Quote Modify

Determine all integer polynomials f such that f(n) | 2n - 1 for all n > 0.
 IP Logged
Obob
Senior Riddler

Gender:
Posts: 489
 Re: f(n) | 2^n - 1   « Reply #1 on: Mar 15th, 2008, 4:49pm » Quote Modify

If there are infinitely many Mersenne primes, then either f(n) = 1 or f(n) = -1 for all n .  Since we don't know if there are infinitely many Mersenne primes or not, if the problem has an answer then this is it.
 IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: f(n) | 2^n - 1   « Reply #2 on: Mar 20th, 2008, 5:07pm » Quote Modify

Yes, that is the answer.  Hint: What do you know about f(p) when p is prime?
 IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: f(n) | 2^n - 1   « Reply #3 on: Jul 16th, 2008, 3:01pm » Quote Modify

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?
 IP Logged
Aryabhatta
Uberpuzzler

Gender:
Posts: 1321
 Re: f(n) | 2^n - 1   « Reply #4 on: Mar 14th, 2009, 1:08pm » Quote Modify

Almost a year!
 IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: f(n) | 2^n - 1   « Reply #5 on: Mar 14th, 2009, 2:45pm » Quote Modify

Well, what do you know about the prime factors of f(p) when p is prime?

Further hint: Dirichlet
 IP Logged
Obob
Senior Riddler

Gender:
Posts: 489
 Re: f(n) | 2^n - 1   « Reply #6 on: Mar 14th, 2009, 4:15pm » Quote Modify

If q is a prime divisor of 2^p-1, 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 | q-1, so kp = q-1 for some k, and q = kp+1 for some k.

I'm not sure where this is going.
 IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 1948
 Re: f(n) | 2^n - 1   « Reply #7 on: Mar 14th, 2009, 6:51pm » Quote Modify

So q can't divide very many values f(p), can it?
 IP Logged
Obob
Senior Riddler

Gender:
Posts: 489
 Re: f(n) | 2^n - 1   « Reply #8 on: Mar 15th, 2009, 4:47pm » Quote Modify

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^p-1.  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)
 « Last Edit: Mar 15th, 2009, 4:50pm by Obob » IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

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