We will show $f\equiv 1$ and $f\equiv -1$ work. Lemma : $f(2^k)=1$ or $-1$ each $k$. Proof : Suppose not. Then take a prime $p$ dividing $f(2^k)$ for some $k$. Now see that $p\mid f(s_r)$ where $s_r=2^k+rp$ for any integer $r$. Now, consider $f(2^{s_r})$. We try to find an $r$ such that $p\mid 2^{s_r}-2^k$. Then we would have $p\mid 2^{s_r}-2^k\mid f(2^{s_r})-f(2^k)\implies p\mid f(2^{s_r})$ hence $\gcd(f(s_r),f(2^{s_r}))>1$ which serves our contradiction. It remains to find such an $r$. If $p=2$ then it is trivial. Suppose $p>2$. We need to find $r$ such that \[ 2^{s_r}\equiv 2^k\pmod p\implies 2^{2^k-k+rp}\equiv 1\pmod p\] but since $p$ is odd hence $\{2^n\mod p\}$ is periodic. Hence such an $r$ exists. Hence we are done. Now we have that for each $n,\; f(2^n)$ is $1$ or $-1$. Suppose there exist $k,\ell$ with $f(2^k)=1,f(2^\ell)=-1$. But then \[ 2^k-2^\ell \mid 2 \] which is a contradiction for sufficiently large $k,\ell$. Then for big $k$ we have $f(2^k)=1$ or $-1$ throughout. Then $f(x)=1$ has infinitely many solutions, and similarly for $f(x)=-1$ and hence $f$ is identically equal to $1$ or $-1$. Hence our claim follows. In the end, our solutions are : \[ \boxed{f\equiv 1,f\equiv -1}\]

Alternative finish (I believe this is how XmL did it too): The lemma in the post above shows that at least one of the polynomials $f(x)-1$ and $f(x)+1$ has infinitely many roots, so one of them must be identically equal to zero, so $f(x)$ is either always 1 or always -1.

I am posting in a hurry so if there is anything wrong please inform me. Thank you. Here: Let us observe that $f \equiv 1$ and $f\equiv -1$ are solutions and no other constant polynomial works. Now assume that $degP \ge 1$. Now let $k_0$ be a natural number such that $\forall k \ge k_0$, $f(k)$ has absolute value greater than $1$. Let $p$ be a prime such that $p \mid f(2^k)$ and let $p>2$ (Such a prime $p$ exists by taking $k$ to be larger than $v_2(f(0))$ or in other words $k$ to be sufficiently large.) . Then set $n= 2^k +p(l(p-1)+k-2^k)$ for sufficiently large $l,k \in \mathbb{N}$. Now, $f(n) \equiv f(2^k) \equiv 0 \bmod p$ and $f(2^n) \equiv f(2^k) \equiv 0 \bmod p$ because of our choice of $n$. This clearly leads to a contradiction to our hypothesis.

Assume that $f$ is nonconstant . Consider $(f(2^i))_{i \geq 1}$ . For sufficiently large $k$ , by our assumption that $f$ is nonconstant , we may choose a prime divisor $p$ so that $p|f(2^k)$ and $p \geq 2$ . Choose $n \equiv 2^k \text{( mod p )}$ and $n \equiv k \text{( mod (p-1) )}$. Then , $f(2^n) \equiv f(n) \equiv 0 \text{( mod p )}$ . This is a contradiction , so $f$ is constant and it is easy to conclude that $f \equiv +1 $ or $f \equiv -1$ .

Indian TST Day 1 Problem 1 wrote: Find all polynomials $f(x)$ with integer coefficients such that $f(n)$ and $f(2^{n})$ are co-prime for all natural numbers $n$.

Very nice solution @aops29 but in this part: aops29 wrote: Take \(l\) to be an integer such that \(l\equiv m - 2^m \pmod{p}\). I think it should be $\pmod{p-1}$

how did he prove it

Suppose there exists $p$ odd prime with $p\mid f(2^{n_0})$. Then, using the chinese remainder theorem, take \[n \equiv n_0 \pmod{p-1}\]\[n\equiv 2^{n_0} \pmod p.\]Since if $a\equiv b \pmod n$, $f(a)\equiv f(b) \pmod n$, \[f(n) \equiv f(2^{n_0}) \equiv f(2^n) \pmod p,\]a contradiction. Hence, for each $n,$ $\pm f(2^n)$ is a power of two. Then, if it is even for some $n, \ f(0)$ is even, so $2\mid \gcd (f(2),f(4))$. Therefore, $f(2^n) = \pm 1$ for all $n$, so either $f+1$ or $f-1$ has infinitely many zeros. This implies that $f\equiv 1$ or $f\equiv -1$, which both work.

Olympikus wrote: Suppose there exists $p$ odd prime with $p\mid f(2^{n_0})$. Then, using the chinese remainder theorem, take \[n \equiv n_0 \pmod{p-1}\]\[n\equiv 2^{n_0} \pmod p.\]Since if $a\equiv b \pmod n$, $f(a)\equiv f(b) \pmod n$, \[f(n) \equiv f(2^{n_0}) \equiv f(2^n) \pmod p,\]a contradiction. Hence, for each $n,$ $\pm f(2^n)$ is a power of two. Then, if it is even for some $n, \ f(0)$ is even, so $2\mid \gcd (f(2),f(4))$. Therefore, $f(2^n) = \pm 1$ for all $n$, so either $f+1$ or $f-1$ has infinitely many zeros. This implies that $f\equiv 1$ or $f\equiv -1$, which both work. In chinese remainder u can choose whatever you want ? Ur choice for $n_0$ and $2^n_0$

TFIRSTMGMEDALIST wrote: how did he prove it Help please

If $f$ is constant, then the only solutions are clearly $f\equiv -1$ and $f\equiv 1$. Assume $f$ is nonconstant. Let $p$ be a prime dividing $f(2^k)$ for some positive integer $k$. Then $f(n)$ and $f(2^n)$ are both divisible by $p$ for any $n\equiv kp - 2^k(p-1)\pmod{p^2 - p}$ so we have a contradiction, as desired.

Standard

let $p$ be a prime such that $p \mid f(2^k)$ .Then we have that $p \mid f(2^k+ cp)$, since $ 2^k \equiv2^k + cp$$ (mod p)$ We can choose $c$ such that $2^{2^k + cp} \equiv 2^ k$, $c \equiv k - 2^k$$ (mod p-1)$ Then we have $p \mid f(2^{2^k + cp} ) - f(2^k) \implies f \mid f(2^{2^k + cp} )$ . A contradiction. Which implies $f(2^k) = \pm 1$ for every $k$ which is clearly not possible. So $f$ is a constant polynomial and the solutions are $\boxed{f\equiv \pm 1}$.

If it isn't $1$ or $-1$, consider a prime $p$ such that $p \mid f(2^x)$, for some $x$. Then, take $n \equiv 2^x \mod{p}$, $n \equiv k \mod{p - 1}$, which exists by CRT, a contradiction.