Let $p$ and $q$ be two odd primes. Note that $pq|P\left(2^{pq}\right)\implies p|P\left(2^{pq}\right)\implies P\left(2^{pq}\right)\equiv 0\pmod{p}.$ Now we have by Fermat's little theorem $2^{pq}\equiv \left(2^q\right)^p\equiv 2^q\pmod{p}$, so using a well-known property of integer polynomials, we have $$0\equiv P\left(2^{pq}\right)\equiv P\left( 2^q\right)\pmod{p}\implies p|P\left(2^q\right).$$Now in the last divisibility relation, taking $p$ large enough forces $P\left(2^q\right)=0$. But this is true for arbitrary odd prime $q$, so $P(x)=0$ for infinitely many $x$. This forces that $P$ is identically zero, as desired. $\blacksquare$

Cute problem. It took me 5 minutes to solve

My solution is a bit long. Let $P(x)=a_kx^k+a_{k-1}x^{k-1}+ \cdots +a_1x+a_0$ with $k \ge 0$. Pick $n=2^l \; (l \in \mathbb{N})$ such that $2^l>|a_0|$ and $2^l>l$ then we have $2^l \mid P(2^{2^l})= 2^{2^l} \cdot K+a_0$ implies $2^l \mid a_0$. Since $2^l>|a_0|$ so $a_0=0$ or $P(0)=0$. Pick $n=p \ne 2$ then we have $p \mid P(2^p)=a_k2^{pk}+a_{k-1}2^{p(k-1)}+ \cdots +a_12^p$ or $p \mid a_k2^k+a_{k-1}2^{k-1}+ \cdots +2a_1$ or $p \mid P(2)$ since $2^p \equiv 2 \pmod{p}$ according to Fermat Littles's Theorem. $p \mid P(2)$ is true for all $p \ne 2$ so we pick large enough number of $p$ to that at some point, their product will be greater than $\left| P(2) \right|$. We follow that $P(2)=0$. We do the similar thing, pick $n=q(q+i-1)=qh \; (q \ne 2,q>i)$ with $q$ is a prime, for a certain positive integer $i$ so that $0 \le i \le k$. We obtain $q \mid 2^{h-i}-1$. We can see that there are infinite number of such prime $q>i$. We have $2^{qh} \equiv 2^h \equiv 2^i \pmod{q}$. Therefore $q \mid qh \mid P(2^{qh})$ and $$P(2^{qh}) \equiv a_k2^{ik}+a_{k-1}2^{i(k-1)}+ \cdots + a_12^i=P(2^i) \pmod{q}$$so $q \mid P(2^i)$. Since there are infinite such prime $q$ so we pick large enough number of $q$ so that $\prod q> \left| P(2^i) \right|$ and $\prod q \mid P(2^i)$ so $P(2^i)=0$ for all $0 \le i \le k$. Thus, we have $P(2^i)=0$ for all $0 \le i \le k$. Therefore, according to Lagrange's interpolation formula we have $$P(x)=\sum_{i=0}^kP(2^i) \cdot \prod_{j=0,j \ne i}^{k} \frac{x-2^j}{2^i-2^j}=0.$$

Let us assume that the maximal root of $P$ is $\alpha$. Fix an integer $r \ge 0$ such that $2^r$ is larger than the absolute value of $\alpha$. Thus, $P(2^r) \not= 0$. Now, let $p$ be a prime number such that $p>|P(2^r)|$. Now, consider the following system of congruences \begin{align*} n \equiv r (\bmod (p-1)) \end{align*}\begin{align*} n \equiv 0 (\bmod p) \end{align*} By the hypothesis $n \mid P(2^n)$ we have $p \mid P(2^n)$ and clearly, $2^n \equiv 2^r (\bmod p)$ by Fermat's Little Theorem, therefore, $p \mid P(2^r)$. This is a contradiction by our choice of $p$. Therefore, $P(2^r)=0$ for all $r$ large enough and since $P$ vanishes infinitely often, it is the zero polynomial.

My solution We need to prove that $deg(P)=0$.If it isn't true we let $deg(P)=n$ where $n$ is a positive integer,which is just $n\ge 1$. So we can rewrite $P(x)$ as $a_{n}x^n+a_{n-1}x^{n-1}+\ldots+a_{1}x+a_{0}$ where $a_{n} \neq 0$ The problem says $x$ divides $P(2^x)$ for every positive integer $x$ which means $\frac{x}{P(2^x)}$ is a non-zero integer for every positive integer $x$. But $\lim_{x\to \infty} \frac{x}{P(2^x)}=\lim_{x\to \infty} \frac{x}{a_{n}(2^x)^n+a_{n-1}(2^x)^{n-1}+\ldots+a_{1}2^x+a_{0}}=\lim_{x\to \infty} \frac{1}{a_{n}\frac{2^{nx}}{x}+a_{n-1}\frac{2^{(n-1)x}}{x}+\ldots+a_{1}\frac{2^x}{x}+\frac{a_{0}}{x}}=0$ which leads to contradiction for $n\ge 1$. Your sincerely CeuAzul

CeuAzul wrote: My solution We need to prove that $deg(P)=0$.If it isn't true we let $deg(P)=n$ where $n$ is a positive integer,which is just $n\ge 1$. So we can rewrite $P(x)$ as $a_{n}x^n+a_{n-1}x^{n-1}+\ldots+a_{1}x+a_{0}$ where $a_{n} \neq 0$ The problem says $x$ divides $P(2^x)$ for every positive integer $x$ which means $\frac{x}{P(2^x)}$ is a non-zero integer for every positive integer $x$. But $\lim_{x\to \infty} \frac{x}{P(2^x)}=\lim_{x\to \infty} \frac{x}{a_{n}(2^x)^n+a_{n-1}(2^x)^{n-1}+\ldots+a_{1}2^x+a_{0}}=\lim_{x\to \infty} \frac{1}{a_{n}\frac{2^{nx}}{x}+a_{n-1}\frac{2^{(n-1)x}}{x}+\ldots+a_{1}\frac{2^x}{x}+\frac{a_{0}}{x}}=0$ which leads to contradiction for $n\ge 1$. Your sincerely CeuAzul The problem states that $x\mid P(2^x)$, so $\frac{P(2^x)}{x}\in\mathbb{Z}$. You said in your solution that $\frac{x}{P(2x)}\in\mathbb{Z}$, which is not necessarily true. As a counterexample consider $x=5$ and $P(2^x)=10$ then $\frac{x}{P(2^x)}=\frac{5}{10}=\frac{1}{2}\notin\mathbb{Z}$

Ooh,sorry,I just misunderstood,as I'm bad at English Aaaargh!Another zero in the test Your sincerely CeuAzul

Assume, there was one such polynomial $P(x)$ that has the desired property, then we can write one such $P$ as \[ P(x) = a_nx^n+a_{n-1}x^{x-1}+\dots+a_1x+a_0 \]with real numbers $a_0,a_1,\dots,a_n$ and $a_n \neq 0$. Now let $p \neq 2$ be a prime. Then by the given conditions we can conclude \[ p \mid P \left(2^p \right)=a_{n} \cdot \left(2^p \right)^n+ \dots+a_1 \cdot2^p+a_0 \equiv a_n \cdot 2^n+a_{n-1} \cdot 2^{n-1}\dots+a_1 \cdot 2 + a_0 \pmod{p} \]by Fermat's Little Theorem. By choosing $p$ sufficiently large, in particular $p> \sum_{k=1}^{n} a_k \cdot 2^k$ we can imply $p \nmid P(2^p)$ as \[ 0 < a_n \cdot 2^n+a_{n-1} \cdot 2^{n-1}\dots+a_1 \cdot 2 + a_0 < p \]but $P \left(2^p \right) \equiv a_n \cdot 2^n+a_{n-1} \cdot 2^{n-1}\dots+a_1 \cdot 2 + a_0 \pmod{p}$. But we can do that for all such polynomials as we've defined in the beginning. Thus, we've reached the desired contradiction so that we may conclude $P(x) = 0$. Done. $\hfill \square$

Quote: Pick large enough prime number $p$, we get $P(2^{k}) = 0$, Sorry i haven't understood why does choosing a large $p$ implies $P(2^{k}) = 0$ ??

trungnghia215 wrote: Pick large enough prime number $p$, we get $P(2^{k}) = 0$, in other words, $2^{k}$ is a zero of $P(x)$. It means $P(x)$ has infinite zeros, or $P(x) = 0$. We're done Sorry i haven't understood why does choosing a large $p$ implies $P(2^{k}) = 0$ ??

Can someone please confirm if my solution is right? It looks too easy... Let $p$ be any odd prime and consider a fixed positive integer $k$. By CRT we can find a positive integer $n$ such that $n=k \mod (p-1)$ and $n=0 \mod p$. Then $p-1 | n-k$, so by FLT $2^{n-k}=1 \mod p$, or equivalently $2^n=2^k \mod p$. But also, $p|n|P(2^n)$. Since $P(2^n)=P(2^k) \mod p$, we get $p|P(2^k)$. This holds for any odd prime $p$, so clearly $P(2^k)=0$. This is true for every positive integer $k$, so $P$ has infinitley many roots, so it's the zero polynomial. Edit: I skimmed through the above posts too quickly and didn't realize my solution is nearly the same as anantmudgal's.

AE-TheRocket wrote: Sorry i haven't understood why does choosing a large $p$ implies $P(2^{k}) = 0$ ?? We got $p\mid P(2^k)$ for every prime $p$. But if $P(2^k)$ was a nonzero number, this wouldn't be possible because a prime greater than $|P(2^k)|$ wouldn't divide $P(2^k)$. So $P(2^k)$ must be equal to $0$.

I feel like I messed up somewhere... Proof: For any odd prime $p$, by Fermat's Little Theorem $$0\equiv P(2^{ap})\equiv P(2^a) \pmod p$$for all postive integers $a$. Thus $p|P(2^a)$ for all positive integers $a$. But this is true for all odd primes $p$, so $P(2^a)=0$ for all positive integers $a$. However, this mean $P$ has infinitely many roots, which means it's the zero polynomial. Q.E.D.

Here is my "solution".

I didn't realize that this could be fixed by taking $p$ to be any prime, then $P\left(2^k\right)=0$ then done. Unfortunately, this is what happens after I spend 4 hours on #6...

Let $p,q$ be prime number By Fermat's little theorem $2^{qp}\equiv (2^q)^p\equiv 2^q\pmod p$ Since$P$ is a polynomial so $p|P(2^{pq})-P(2^q)$ Since$pq|P(2^{pq})$ and $p|P(2^{pq})-P(2^q)$. So $p|P(2^q)$ for all prime number$p$ Then$P(2^q)=0$$\implies$$P(x)$ has infinite root And we will get $P(x)=0$

Ankoganit wrote: Let $p$ and $q$ be two odd primes. Note that $pq|P\left(2^{pq}\right)\implies p|P\left(2^{pq}\right)\implies P\left(2^{pq}\right)\equiv 0\pmod{p}.$ Now we have by Fermat's little theorem $2^{pq}\equiv \left(2^q\right)^p\equiv 2^q\pmod{p}$, so using a well-known property of integer polynomials, we have $$0\equiv P\left(2^{pq}\right)\equiv P\left( 2^q\right)\pmod{p}\implies p|P\left(2^q\right).$$Now in the last divisibility relation, taking $p$ large enough forces $P\left(2^q\right)=0$. But this is true for arbitrary odd prime $q$, so $P(x)=0$ for infinitely many $x$. This forces that $P$ is identically zero, as desired. $\blacksquare$ Hello , What is that "well-known property of integer polynomial"?

It's the deep fact that $a-b|P(a)-P(b)$ for integers $a,b$ and integer polynomial $P$.

Let $P(x) = c_0+c_1x+c_2x^2+\cdots + c_kx^k$. Let $p$ be some prime, and let $\ell \ge 1$ be some constant. Then $\ell p \mid P(2^{\ell p})$, so $2^{\ell p} \equiv 0 \pmod{p}$. So \[ P(2^{\ell p})=c_0+2^{\ell p}c_1 + 2^{2\ell p}c_2 +\cdots + 2^{\ell pk}c_k \equiv 0 \pmod{p}. \]But $2^p \equiv 2 \pmod{p}$, so $2^{\ell p} \equiv 2^{\ell+1} \pmod{p}$. Hence, the above becomes \[ c_0+2^{\ell+1} c_1 + 2^{2(\ell+1)} c_2 + \cdots + 2^{k(\ell +1)}c_k =P(2^{\ell+1}) \equiv 0 \pmod{p}. \]Therefore, $P(2^{\ell+1}) \equiv 0 \pmod{p}$ for all primes $p$. But this means that $P(2^{\ell+1}) = 0$. Therefore, $P(x)=0$ for infinitely many values of $x$, so $P(x)=0$ for all $x$.

Kezer wrote: ...as \[ 0 < a_n \cdot 2^n+a_{n-1} \cdot 2^{n-1}\dots+a_1 \cdot 2 + a_0 < p \] How that? The term in the middle is $P(2)$ which could just (and actually will) be $0$. What you have actually proved is that $P(2)=0$. No contradiction so far. Of course you can adapt that argument to show that $P(2^t)=0$ for each positive integer $t$ which will certainly be a contradiction unless $P$ is identically zero. This will give you something isomorphic to the standard solution presented now a few times in this thread.

Let $ degP=k$ and $ P=a_0x^k+a_1x^{k-1}+ \cdots +a_{k-1}x+a_{k}$ Claim: $a_k=0$ Proof. Consider $\nu_2(a_k)=q \ge 0$ Thus for $ n=2^{q+1} $ we obtain $ 2^{q+1}| a_02^{k(q+1)}+a_12^{(k-1)(q+1)}+\cdots+a_{k-1}2^{q+1}+a_{k} $.Hence $ 2^{q+1}|a_k $,which is clearly a contadiction by $ \nu_2 $ Thus $a_k=0$ and $P=a_0x^k+a_1x^{k-1}+\cdots a_{k-1}x $ Now we make the following observation ,for every positive integer $ m $ exist infinitely prime numbers (let this sequence be $ x_n$) such that $ \gcd(x_n, m)=1 $ for all positive integers $ n $ The proof is very simple since the set of prime numbers is infinite. Consider then $ n=2^t$ where $ t$ is prime $ t >2 $ . Thus $ a_02^{kt}+a_12^{(k-1)t}+\cdots+a_{k-1}2^{t} \equiv a_02^k+a_12^{k-1}+\cdots+a_{k-1}2 \pmod t $ (where the last congruence is due to Fermat Theorem ) Therefore $a_02^k+a_12^{k-1}+\cdots+a_{k-1}2 \equiv 0 \pmod t $ Since there are infinitely prime numbers with this property we obtain $a_02^k+a_12^{k-1}+\cdots+a_{k-1}2=0 $ Similarly $2$ can be changed by every positive integer number . So $ P=0 $ for every positive integer ,which leads to the conclusion.

taking $n=2^k$ , $2^k \mid P(2^{2^k}) \implies 2^k \mid P(0) \implies P(0)=0 \implies P(n)=nQ(n)$ Now,taking $n=2^a*p$ with odd prime $p$ will give $p \mid P(2^{2^a*p}) \implies p \mid P(2^{2^a})$ .But this is true for any fixed $a$ and any odd prime $p$.Hence,$2^{2^a}$ will be a root for any prime and the result is immediate.

let $q>2$ be a prime number. We have, $P(2^q) \equiv 0 \equiv P(2)$ (mod $q$) Thus, for all primes $q>2$, $q|P(2)$ so, $P(2)=0$ thus, $P(x)=(x-2)Q(x)$ for some integer polynomial $Q$. Consider $n=2q$, $2q|P(2^{2q}) \Rightarrow q|(4^q-2)Q(4^q)$. Note that $4^q-2 \equiv 4-2 \equiv 2$ (mod $q$), so $\gcd(p,4^q-2)=1$. Hence, $q|Q(4^q)$. Doing the same process infinitely many times yields $P(x)=(x-2)(x-4)(x-8)...$ so $P$ has infinitely many roots. Finally, giving $P(x)=0$

Overcomplicated this for a while. Write $P(x) = a_k x^k + \cdots + a_1 x^1 + a_0$. Consider any odd primes $p,q$. Let $n=pq$, thus by Fermat's Little Theorem and the condition \[ 0 \equiv P(2^{pq}) \equiv \sum_{i=0}^k a_i (2^{pq})^i \equiv \sum_{i=0}^k a_i (2^q)^i \equiv P(2^q) \pmod{p} \implies p|P(2^q) \]Consider any odd prime $q$ and let $p$ vary over all odd primes. It follows that $p|P(2^q)$ for all such $p$, so $P(2^q)$ has infinitely many divisors. But $P(2^q)$ is finite, so $P(2^q) = 0$. This holds for all odd primes $q$, so $P$ has infinitely many roots. So $P$ is the zero polynomial.

Consider $n=kp$, where $k$ is a positive integer and $p$ is a prime. Then by the condition and FLT we have $$p \mid kp \mid P(2^{kp}) \implies p \mid P(2^k),$$but since this is true for all $p$ we can just take $p>|P(2^k)|$ and obtain a contradiction unless $P(2^k)=0$. Hence $P(2^k)=0$ for all $k \geq 1$, which means that $P$ has infinite roots and is therefore the zero polynomial.

We prove that $P(2^a)=0$,for all positive integer $a$. Let $p$ be a prime greater than $|P(2^a)|$.Then we have that $p|pa|P(2^{pa})$.However $P(2^{pa})=P(2^a)$ mod $p$. Hence ,$p$ divides $P(2^a)$,which is a contradiction.So $P(2^a)=0$,for all positive integer $a$. This gives $P$ is identically zero.

lol Replace $P$ with $f$. Let $n=kp$ where $p$ is a odd prime prime and $k \in \mathbb{N}$. We have $$p \mid kp \mid f(2^{kp})$$. Also, $$2^{kp} \equiv{(2^p)^k} \equiv{2^k} \pmod{p}$$Therefore, $$f(2^k) \equiv{0} \pmod{p}$$which is a contradiction for large enough $p$ unless $f(2^k)=0$. Now $f$ has infinite zeroes and it follows that $f$ is the zero polynomial $\blacksquare$

$2^{2^{n-1}}(2^{2^{n-1}}-1) | P(2^{2^n}) - P(2^{2^{n-1}}) \implies P(2^{2^n}) \equiv P(2^{2^{n-1}}) \pmod {2^{2^{n-1}}}$. Notice that $2^n | P(2^{2^n})$, so therefore $2^n | P(2^{2^{n-1}})$. Keep repeating this algorithm to receive $P(2^{2^n}) = 0$. Therefore $P(x) = 0$. $\blacksquare$

We use the fact that $P\left(2^n\right)\equiv P\left(2^{n-\phi(n)}\right)\pmod{n}$. As a corollary, $P\left(2^n\right)\equiv P\left(2^{n-k\phi(n)}\right)\pmod{n}$ as long as $n\geq k\cdot\phi(n)$. Let $p_1\ne p_2\ne \dots\ne p_r$ be primes, then $P\left(2^{p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r}}\right)\overset{p_1-1=\phi(p_1)}{\equiv}P\left(2^{p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r}-(p_1-1)(p_1^{\alpha_1-1}+p_1^{\alpha_1-2}+\dots+p_1+1)p_2^{\alpha_2}p_3^{\alpha_3}\dots p_r^{\alpha_r}}\right)\equiv P\left(2^{p_2^{\alpha_2}p_3^{\alpha_3}\dots p_r^{\alpha_r}}\right)\equiv0\pmod{p_1}$ where $\alpha_i\in\mathbb{N}$. But that means that $P\left(2^{p_2^{\alpha_2}p_3^{\alpha_3}\dots p_r^{\alpha_r}}\right)$ has infinitely many prime divisors; this leads to $P(2^n)=0\ \forall\ n\in\mathbb{N}$. But if a polynomial vanishes for infinitely many inputs, it vanishes at all inputs; else its degree is infinite which is impossible. So, the polynomial must be the zero polynomial. $\blacksquare$

Note that $pq \mid f(2^{pq})$ for distinct odd primes $p, q$, but $2^ {pq} \equiv 2^q \pmod p$, hence $2^q \equiv 0 \pmod p$. As we have now isolated $p, q$, this implies that $f(2^q) = 0$ for all primes $q$ and thus $f \equiv 0$.

Let $p,q$ be distinct odd primes. We have $pq \mid P(2^{pq})$, so $p\mid P(2^{pq})$ and $q\mid P(2^{pq} )$. Since $2^{pq}$ is $2^q $ modulo $p$ we get $p\mid P(2^q)$, so $P(2^q)$ has infinitely many prime divisors, and thus must be equal to $0$. Hence $P$ has infinitely many zeroes, so it must be the zero polynomial.

Is this a good proof? Suppose P isn't constant. Let ord_p(2) denote the smallest number 0<k such that 2^k==1 mod p. Let P be of degree k and leading coefficient A. Take p>A and P > 2^k. Then p|P(2^(tp)) for every t, meaning that 2^(tp) is a root of P mod p for every t. As 2^x==2^(x mod ord_p(2)), there is ord_p(2) unique roots of P mod p, all of which can be written as 2^(tp). But as 2^ord_p(2)>p>2^k then ord_p(2)>k, but this is a contradiction as P can have at most k roots mod p (because p does not divide A, as p>A).

For each positive integer $k$, we show $P(2^k) = 0$ which solves the problem. Let $p$ be a prime greater than $| P(2^k) |$; then, we have \[ P(2^{pk}) \equiv 0 \pmod{p} \implies P(2^k) \equiv 0 \pmod{p} \implies P(2^k) = 0. \qquad \square\]

consider p infinitely large, xp | P(2^xp) ==> p | P(2^xp). note that 2^xp = 2^x mod p, so P(2^x) = 0 mod p ===> P(2^x) = 0

Notice that $p \mid P(2^{xp}), P(2^{yp})$ so $p \mid P(2^{xp}) - P(2^{yp})$. Now let $P(x) = \sum_{k = 0}^{n} a_k x^k$. notice that \begin{align*} P(2^{xp}) &= \sum_{k = 0}^{n} a_k \left( 2^{xp} \right)^k \\ &\equiv \sum_{k = 0}^{n} a_k \left( 2^x \right)^k \\ &\equiv P(2^x) \pmod p. \end{align*} This means that $p \mid P(2^x) - P(2^y)$ for all prime numbers. Since arbitrarily large primes exist, $P(2^x) - P(2^y) = 0$. Therefore $P(2) = P(2^2) = P(2^3) = \cdots$ and $j \mid P(2^j) = P(2)$ for arbitrarily large integers $j$ so $P(2) = P(2^j) = 0$, so $P$ has infinitely many zeroes. Therefore it is the zero polynomial. remark: flt was a lot more effective than i thought it would be