# Thread: Characterization of primes

1. ## Characterization of primes

Show that $\displaystyle (x+1)^n \equiv x^n + 1^n \mod n$ in $\displaystyle \mathbb{Z}[x]$ if and only if n is a prime.
(In other words,all coefficients in the difference polynomial $\displaystyle (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 $\displaystyle (x+1)^n \equiv x^n + 1^n \mod n$ in $\displaystyle \mathbb{Z}[x]$ if and only if n is a prime.
(In other words,all coefficients in the difference polynomial $\displaystyle (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 $\displaystyle n$ is prime if and only if $\displaystyle n$ divides $\displaystyle {n\choose k}$ for all $\displaystyle 1\leq k\leq n-1$.

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

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