Why is this polynomial irreducible at mostly prime exponents I'm trying to determine when this polynomial is reducible and irreducible over $\Bbb Q$ :
$$x^n+(1-x)^n.$$
I checked up to $n=100.$ This polynomial is irreducible for: 
$$n=2,3,4,5,7,8,11,13,16,17,19,23,29,31,32,37,41,43,47,53,59,61,64,67,71,73,79,83,89,97.  $$
I immediately noticed that all of the values are prime except $4,8,16,32,64.$
What is the reason for this?
 A: If $m$ is odd, we can factor $a^m+b^m$ over $\mathbb{Q}$ as $$a^m+b^m=(a+b)(a^{m-1}-a^{m-2}b+\dots+b^{m-1})$$ (good exercise: figure out why this works when $m$ is odd but not when $m$ is even).  In particular, if $m$ is an odd factor of $n$ with $n=md$, then we have $$x^n+(1-x)^n=(x^d)^m+((1-x)^d)^m=(x^d+(1-x)^d)((x^d)^{m-1}-\dots+((1-x)^d)^{m-1}).$$ As long as $d>1$ and $m>1$, this gives a nontrivial factorization of $x^n+(1-x)^n$ over $\mathbb{Q}$ (we need $d>1$ and $m>1$ to be sure neither factor is a constant; the first factor is nonconstant as long as $d>1$ and the second factor is nonconstant as long as $m>1$ since you can calculate that its leading term is an odd multiple of $x^{d(m-1)}$).
This means that if $n$ has any odd proper factor greater than $1$, then $x^n+(1-x)^n$ is reducible over $\mathbb{Q}$.  The only positive integers with no odd proper factors greater than $1$ are primes and powers of $2$.

On the other hand, the polynomial $f(x)=x^n+(1-x)^n$ is always irreducible over $\mathbb{Q}$ when $n$ is prime or a power of $2$ greater than $1$.  To prove this, let $g$ be the polynomial of the same degree as $f$ but with the order of its coefficients reversed.  It suffices to show $g$ is irreducible, since any factorization of $f$ would give a factorization of $f$ by reversing the coefficients of the factors.
But $g$ satisfies Eisenstein's criterion and thus is irreducible.  Indeed, if $n$ is an odd prime the $x^n$ terms in $f$ cancel out and so $$g(x)=x^{n-1}-\binom{n}{1}x^{n-2}+\dots+\binom{n}{n-1}$$ satisfies Eisenstein's criterion for the prime $n$ (all the binomial coefficients are divisible by $n$ and the last one $\binom{n}{n-1}=n$ is not divisible by $n^2$).
If $n$ is a power of $2$ greater than $1$, we instead have $$g(x)=x^n-\binom{n}{1}x^{n-1}+\dots-\binom{n}{n-1}x+2.$$  This satisfies Eisenstein's criterion for the prime $2$, since $n$ is a power of $2$ so all these binomial coefficients are even.
