×

# Divisibility for the Win - Problem 3

A polynomial $$f(x)\in\mathbb{Z}[x]$$ has the property that $$2^{n-1}-1\mid f\left(2^{n}-1\right)$$ for all integers $$n>1$$. Show that $$f(x)=0$$ has an integer root.

Note by Cody Johnson
2 years, 9 months ago

Sort by:

We have the condition $$A\mid f(2A+1)$$ where $$A$$ is a power of two minus one. Assuming that $$n$$ is big enough, let $$p$$ be the biggest prime number dividing $$A$$: we have $$p\mid f(2A+1)$$, or just $$p\mid f(1)$$. Since the set of prime numbers dividing a number of the form $$2^m-1$$ is infinite (*), we have that $$f(1)$$ is divisible by an infinite number of primes - this gives $$f(1)=0$$.

(*) Assuming that every $$2^n-1$$ can be factored in terms of $$p_1,\ldots,p_k$$, we have a contradiction, since: $\forall i\in[1,k],\qquad 2^{1+\prod_{j=1}^k(p_j-1)}-1\equiv 2-1\equiv 1\not\equiv 0\pmod{p_i}.$ · 2 years, 9 months ago

Nice way to show that the set of primes which divide $$2^n -1$$ is infinite.

Note that $$p$$ doesn't need to be the biggest prime number that divides $$A$$. (doesn't impact your proof) Staff · 2 years, 9 months ago

Minor typo: this gives $$f(1)=0.$$ · 2 years, 9 months ago

Is there a more general statement that can be made here?

On a related note, show that if $$n \mid f(n)$$ for infinitely many integers $$n$$, then $$f(0) = 0$$. Staff · 2 years, 9 months ago

The general statement, I believe, would be that if $$f(m) \mid f(g(m))$$ for infinitely many $$m \in \mathbb{Z}$$ for some $$f, g \in \mathbb{Z}[x],$$ then $$f(g(0))=0,$$ although there are probably other ways generalize this.

Note that $$f(n) \equiv f(0) \pmod{n},$$ so $$n \mid f(0)$$ for infinitely many $$n \in \mathbb{Z},$$ which is possible if and only if $$f(0)=0,$$ since $$0$$ is the only integer with infinitely many divisors. · 2 years, 9 months ago