Disclaimer: I'm not a mathematician, nor a student of math. So my knowledge isn't really good and I'm not accustomed at proving theorems.

I need a short and simple proof of this generalization of Fermat's littel theorem:

Theorem: Let $\displaystyle a \in \mathbb{Z}$ and $\displaystyle n (\geq 2) \in \mathbb{N}$ such that $\displaystyle a$ and $\displaystyle n$ are coprimes.

Then $\displaystyle n$ is prime if and only if $\displaystyle (x + a)^n \equiv x^n + a \mod n$(eq).

I found a partial proof in one of my books, but there is some part left "as an exercise" which I don't understand how to prove.

The partial proof looks like this:

The coefficient in $\displaystyle (x + a)^n - (x^n + a)$ of the $\displaystyle x^i$ term, for $\displaystyle 0 < i < n$ is $\displaystyle {n \choose i} a^{n-i}$, and if $\displaystyle n$ is prime

then $\displaystyle {n \choose i} \equiv 0 \mod n$. Thus, for Fermat's little theorem, the (eq) holds(*).

Let us suppose $\displaystyle n$ is a composite number and let $\displaystyle q$ be one of the prime factors of $\displaystyle n$. Let $\displaystyle \alpha$ be the maximum integer such that $\displaystyle q^\alpha \mid n$,

then $\displaystyle q^\alpha \nmid {n \choose q}$(**) and it is relatively prime with $\displaystyle a^{n-q}$.

Thus the coefficient of $\displaystyle x^q$ is non-zero modulo $\displaystyle n$, therefore $\displaystyle (x+a)^n - (x^n + a)$ is not the null-polynomial in $\displaystyle \mathbb{Z}_n[x]$,

or, in other words, (eq) does not hold.

(*) Not complete, but It's trivial to prove. Obviously $\displaystyle {n \choose i} \equiv 0 \mod n$ because the $\displaystyle n$ at the numerator is not simplified. Applying the fermat's little theorem to the remaining terms(=first and last) yields the result.

(**) This is the statement left as an exercise, and which I want to prove.

I know that the proof of that little statement must be simple, but I can't find a way of proving it. I'd like to find some very small and simple proof using combinatorics.

Anyone can help me in this task?

By the way: before posting this thread I've searched in this forum, on google, on mathoverflow, but I couldn't find a proof.

I found some references of books containing the proof, but, by what I understood, they prove a more general theorem for

finite fields, so probably the proof requires a deeper knowledge of field theory, and also I haven't got these books at hand.

If anyone knows also the finite-field version, it's welcome to post it.