<s>[INST] $f(n)$ and $f(2^n)$ are co prime for all natural numbers $n$. Find all such polynomials. Find all polynomials $f(x)$ with integer coefficients such that $f(n)$ and $f(2^n)$ are co prime for all natural numbers $n$.
 [/INST] Here is a proof of non-existence of non-constant polynomials of this type: Suppose $f(x) = a_0 + a_1x + a_2x^2 + … + a_mx^m$ is such a polynomial (where $m>0$). We reach a contradiction. 
If $a_0$ is even then $f(2)$ and $f(2^2)$ share a common factor of $2$. So $a_0$ must be odd. Thus, for every positive integer $k$, the number $f(2^k)$ must be odd.  Since $f(2^k)$ is odd and diverges to $\infty$ or $-\infty$ as $k$ gets large, there must be a positive integer $K$ such that $f(2^K)$ is divisible by some odd prime $p$.  That is, $f(2^K) \equiv 0$ (mod $p$).   
Claim: We can construct an integer $Z$ such that $f(Z)$ and $f(2^Z)$ are both divisible by $p$ (which yields the contradiction). 
Proof:  Since $p$ is an odd prime, the sequence $\{mod(2^i,  p)\}_{i=1}^{\infty}$ is never $0$, and periodically cycles over a subset of integers in $\{1, \ldots, p-1\}$.  Let $n$ be a positive integer that satisfies $2^{n+2^K} \equiv 2^K$ (mod $p$).  Define $Z = np+2^K$.  By Fermat's Little Theorem we have $2^{np+2^K} \equiv 2^{n+2^K}$ (mod $p$).  Thus:
$2^Z = 2^{np+2^K} \equiv 2^{n+2^K} \equiv 2^K$ (mod $p$).  
Hence, $f(2^Z) \equiv f(2^K) \equiv 0$ (mod $p$).  
However, $Z = np + 2^K \equiv 2^K$ (mod $p$), and so $f(Z) \equiv f(2^K) \equiv 0$ (mod $p$). 
Thus, $f(Z)$ and $f(2^Z)$ are both divisible by $p$.  
</s>