# Thread: Characterization of primes

1. ## Characterization of primes

Show that $(x+1)^n \equiv x^n + 1^n \mod n$ in $\mathbb{Z}[x]$ if and only if n is a prime.
(In other words,all coefficients in the difference polynomial $(x + 1)^n - (x^n + 1^n)$ are divisible by n. This is a relation in the polynomial ring, not for individual integers x.)

2. Hello,
I haven't thought about the proof yet but are you sure it is a IFF statement ? If it was, primality testing would be trivial, which is not the case. Unless I'm misunderstanding the statement which is quite probable.

3. Originally Posted by EinStone
Show that $(x+1)^n \equiv x^n + 1^n \mod n$ in $\mathbb{Z}[x]$ if and only if n is a prime.
(In other words,all coefficients in the difference polynomial $(x + 1)^n - (x^n + 1^n)$ are divisible by n. This is a relation in the polynomial ring, not for individual integers x.)
By the binomial formula, you question boils down to: show that $n$ is prime if and only if $n$ divides ${n\choose k}$ for all $1\leq k\leq n-1$.

Remember ${n\choose k}=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1}$.

Assume $n$ is prime. Then it divides the numerator but not the denominator. Since it is prime, we conclude it divides the binomial coefficient. (justify that properly)

Assume $n$ is composite. Let $p$ be any prime factor of $n$. Of course, $2\leq p\leq n-1$. It divides both the largest terms of the numerator and of the denominator of ${n\choose p}$, and it doesn't divide any other factor since there are $p$ of them, and only 1 number among $p$ consecutive ones is divisible by $p$. Thus, after simplification by $p$, the numerator is not divisible by $p$, so that the binomial coefficient isn't either.