I have trouble in understanding the proof of this primality criterion:
$n$ is prime if and only if the congruence $(x+b)^n \equiv x^n+b \,\,\,\text{mod} \,n$ holds for every $b\in \mathbb{Z}$.
In particular my problem is to understand the proof of the implication $(x+b)^n \equiv x^n+b \,\,\, \text{mod} \,n$ holds for every $b\in \mathbb{Z} \implies n $ is prime.
One assumes by contradiction $n$ composite, takes a prime factor $p$ of $n$, and then shows that $p^\alpha$, which is by definition the highest power of $p$ which divides $n$, does not divide the binomial coefficient $n\choose p$, and so a fortiori $n$ cannot divide $n\choose p$. But why this conclusion leads to the negation of the congruence? And I have also another question: how do I have to interpret a polynomial congruence with a "free" indeterminate $x$ like that? Is it simply a numerical congruence which holds for all $x\in \mathbb{Z}$ or does it have to be regarded in a different way?
Thanks for your help!
Let's begin with
That is to be interpreted as congruence of all corresponding coefficients, or equivalently as equality in the polynomial ring $(\mathbb{Z}/n\mathbb{Z})[x]$.
And from that immediately follows the first point, the coefficient of $x^p$ in $(x+b)^n$ is $\binom{n}{p}b^{n-p}$, and if $b$ is not divisible by $p$, the coefficient is not divisible by $p^\alpha$, hence not by $n$, so then $(x+b)^n \not\equiv x^n+b^n \pmod{n}$.