×

# 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
3 years, 11 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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}.$

- 3 years, 11 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 - 3 years, 11 months ago

Minor typo: this gives $$f(1)=0.$$

- 3 years, 11 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 - 3 years, 11 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.

- 3 years, 11 months ago