Finding all such polynomials under a gcd condition Find all such polynomial $f(x)\in \mathbb{Z}[x]$ such that 
$$ \forall n\in \mathbb{N} \quad \gcd(f(n),f(2^n))=1$$
This is a problem from the Indian Team Selection Test. Can someone give me a solution to it? Thanks a lot. I have not a single idea about it.
 A: This proof is obtained by "working backwards" and picking the most reasonable breadcrumb that can lead us along the backtracked way. As I champion the approach of "working from the front and the back and figuring out what the middle is" as a way of solving problems, let me  walk you through how this is done in this scenario. There is a lot to learn, so bear with this (really long) backward presentation. In particular, it shows you how to generate ideas from what is given, and piece it together to get a proof.
Note: Given that you are working on India TST problems, several (minor) parts of this problem are left "for you to do". It should not affect the overview.
We will use the well known results that
1) For any $ f \in \mathbb{Z} [x]$, $ a-b \mid f(a) - f(b)$.
2) Fermat's Little Theorem (Euler's Theorem)
For you to do: Prove these results.
Claim: The only solutions are $ f(x) = 1$ and $ f(x) = -1$. Clearly, these functions satisfy the conditions.
Breadcrumb 1: We want to show that $ f( 2^n) = 1$ or $-1$ for all integers $n$.
 For you to do: Show that this easily results in the above claim.
Breadcrumb 2: We want to show that $ f( 2^n) \mid f ( k)$ and $ f(2^n) \mid f(2^k)$ for some $k$.
For you to do: Show that this easily results breadcrumb 1.
(Rambling / side detour) The above breadcrumb is unnecessarily strong, and we might not be able to prove it. Let's soldier on.
Breadcrumb 3: (The only sane path that we could backtrack on) Let's classify (possible) candidates for $k$. From the 1st well known result, $k = 2^n + Lf(2^n)$, where $L$ is any integer, work.
For you to do: Prove that this family of $k$ work.   
Breadcrumb 4: We want to show that there is some $L$ such that $ f(2^n)  \mid f(2^{ 2^n + L f(2^n)})$.
For you to do: Prove that Breadcrumb 3 and 4 give 2.  
Breadcrumb 5: We want to show that there is some $L$ such that $ f(2^n) \mid 2^{ 2^n + L f(2^n)} -2^n = 2^n ( 2^{ Lf(2^n) + 2^n - n } -1)$.
For you to do: Prove that Breadcrumb 5 gives Breadcrumb 4.
How can we possibly show this? We have such little control over anything. Wait, 
Does showing that $ 2^{ L f( 2^n)} \equiv 2^{ n - 2^n} \pmod { f(2^n)}$ remind us of anything? It so looks like Fermat's Little Theorem. Oh, dang! If only $f(2^n)$ was a prime ... 
Such wishful thinking. How do we "make" it a prime? Well, if it isn't a prime, let's take any prime factor $p$. Now, we backtrack our breadcrumbs to fix it. Remember when I said that breadcrumb 2 is too strong?
Breadcrumb 2B: For all $n$, for any $ p \mid f(2^n)$, then there exists a $k$ such that $ p \mid f(k)$ and $ p \mid f(2^k)$.
For you to do: Show that this also results in Breadcrumb 1.
Breadcrumb 3B: Let's classify (possible) candidates for $k$. From the 1st well known result, $k = 2^n + Lp$, where $L$ is any integer, work.
For you to do: Show that this family works.   
Breadcrumb 4B: We want to show that there is some $L$ such that $ p  \mid f(2^{ 2^n + L p})$.
For you to do: Show that 4B+3B implies 2B.   
Breadcrumb 5B: We want to show that there is some $L$ such that $ p \mid 2^{ 2^n + Lp} -2^n = 2^n ( 2^{ Lp + 2^n - n } -1)$.
For you to do: Show that breadcrumbs 5B gives us 2B.
Breadcrumb 6B: Take $ L = n - 2^n$. If we can apply Fermat's Little Theorem, then we are done, since $ 2^{Lp} \equiv 2^{L} \equiv 2^{n - 2^n}  \pmod{p}$.
Oh wait, in order to apply Fermat's Little Theorem, we need $ p \neq 2$.
For you to do : Deal with the case when $p=2$ (which means that $ 2 \mid f(2^n)$). This is a one-liner.   

 Hint: Show that $ 2 \mid f(2^{2^n} ) $.

For you to do: Now that I've walked you through how to figure out this proof, write it in the (much shorter) forward manner.
Note: I do not know if breadcrumb 2 is true. I suspect that there are scenarios where it is not, but I have not bothered to investigate.
