Find all polynomials $f(x)$ with integer coefficients such that $f(n)$ and $f(2^{n})$ are co-prime for all natural numbers $n$.
1. **Identify the problem and initial conditions:**
   We need to find all polynomials \( f(x) \) with integer coefficients such that \( f(n) \) and \( f(2^n) \) are co-prime for all natural numbers \( n \). 

2. **Consider the case when \( f(x) \) is a constant polynomial:**
   - If \( f(x) \) is a constant polynomial, say \( f(x) = c \), then \( f(n) = c \) and \( f(2^n) = c \) for all \( n \).
   - For \( f(n) \) and \( f(2^n) \) to be co-prime, \( c \) must be co-prime with itself, which is only possible if \( c = \pm 1 \).
   - Therefore, the constant solutions are \( f(x) \equiv 1 \) and \( f(x) \equiv -1 \).

3. **Assume \( f(x) \) is non-constant:**
   - Let \( f(x) \) be a non-constant polynomial with integer coefficients.
   - Consider an odd prime \( p \) and a positive integer \( k_0 \) such that \( p \mid f(2^{k_0}) \). This is possible because \( f(x) \) is non-constant and will take on multiple values, some of which will be divisible by some prime \( p \).

4. **Construct a specific \( n \) to derive a contradiction:**
   - Let \( k \in \mathbb{N} \) be such that \( k \equiv k_0 - 2^{k_0} \pmod{p-1} \).
   - Define \( n = pk + 2^{k_0} \).
   - Observe that:
     \[
     f(n) = f(pk + 2^{k_0}) \equiv f(2^{k_0}) \pmod{p} \equiv 0 \pmod{p}
     \]
     Hence, \( p \mid f(n) \).

5. **Analyze \( 2^n - n \) modulo \( p \):**
   - Consider \( 2^n - n \):
     \[
     2^n - n = 2^{pk + 2^{k_0}} - pk - 2^{k_0}
     \]
   - Using Fermat's Little Theorem (FLT), \( 2^p \equiv 2 \pmod{p} \):
     \[
     2^n - n \equiv 2^{k + 2^{k_0}} - 2^{k_0} \pmod{p}
     \]
   - Since \( k \equiv k_0 - 2^{k_0} \pmod{p-1} \):
     \[
     2^{k + 2^{k_0}} \equiv 2^{(k_0 - 2^{k_0}) + 2^{k_0}} \equiv 2^{k_0} \pmod{p}
     \]
   - Therefore:
     \[
     2^n - n \equiv 2^{k_0} - 2^{k_0} \equiv 0 \pmod{p}
     \]
     Thus, \( p \mid (2^n - n) \).

6. **Derive the contradiction:**
   - Since \( p \mid f(n) \) and \( p \mid (2^n - n) \), we have:
     \[
     p \mid \gcd(f(n), 2^n - n)
     \]
   - Given that \( 2^n - n \mid f(2^n) - f(n) \), it follows that:
     \[
     \gcd(f(n), f(2^n)) \geq \gcd(f(n), 2^n - n) \geq p > 1
     \]
   - This contradicts the assumption that \( f(n) \) and \( f(2^n) \) are co-prime for all \( n \).

7. **Conclusion:**
   - The only polynomials \( f(x) \) that satisfy the given condition are the constant polynomials \( f(x) \equiv 1 \) and \( f(x) \equiv -1 \).

\(\blacksquare\)

The final answer is \( \boxed{ f(x) \equiv 1 } \) or \( f(x) \equiv -1 \).