Author |
Topic: f(n) | 2^n - 1 (Read 1407 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print