Prove that the polynomial identity $(x+1)^n \equiv x^n +1 \mod n$ holds iff $n$ is prime.
One direction is easy: Assume that $n$ is prime. By the binomial theorem we have $(x+1)^n = \sum^{n}_{k=0} {n\choose k} x^k$, and since $n$ is prime, for every $1\leq k\leq n-1$ we have ${n\choose k} = 0 \mod n$.
I'm not sure about the other direction- we know that
$(x+1)^n - (x^n +1) \equiv \sum^{n-1}_{k=1} {n\choose k} x^k \equiv 0 \mod n$,
and it seems to me that I need to show that if $n$ is not prime then there is some non-zero coefficient for the above polynomial, but I am not sure how to do this, or how exactly this contradicts the above (for example $x^2 -x$ is always zero over the binary field, but has non-zero coefficients).
Suppose $p$ is prime dividing $n$; let $p^k$ be the largest power of $p$ dividing $n$. Then $p^k$ does not divide $\binom{n}{p}$ (hint: consider the number of times $p$ appears on the numerator and on the denominator of $\frac{n \times (n-1) \times \dots \times (n-p+1)}{p!}$), and so the coefficient of $x^p$ is not zero in $(x+1)^n$.
You may be interested in the AKS primality test, by the way, of which this is a specific instance. See https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf for the paper, in which Lemma 2.1 is a generalisation of what you want to prove.