Need a proof of the polynomial generalization of fermat's little theorem

**Bakuriu** · September 7th 2012, 12:34 AM

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 $a \in \mathbb{Z}$ and $n (\geq 2) \in \mathbb{N}$ such that $a$ and $n$ are coprimes.
Then $n$ is prime if and only if $(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 $(x + a)^n - (x^n + a)$ of the $x^i$ term, for $0 < i < n$ is ${n \choose i} a^{n-i}$ , and if $n$ is prime
then ${n \choose i} \equiv 0 \mod n$ . Thus, for Fermat's little theorem, the (eq) holds(*).
Let us suppose $n$ is a composite number and let $q$ be one of the prime factors of $n$ . Let $\alpha$ be the maximum integer such that $q^\alpha \mid n$ ,
then $q^\alpha \nmid {n \choose q}$ (**) and it is relatively prime with $a^{n-q}$ .
Thus the coefficient of $x^q$ is non-zero modulo $n$ , therefore $(x+a)^n - (x^n + a)$ is not the null-polynomial in $\mathbb{Z}_n[x]$ ,
or, in other words, (eq) does not hold.

(*) Not complete, but It's trivial to prove. Obviously ${n \choose i} \equiv 0 \mod n$ because the $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.

**Bakuriu** · September 7th 2012, 06:08 AM

Okay, I think I came up with a proof.

Suppose $q^\alpha \mid {n \choose q}$ , then it means that ${n \choose q} = kq^\alpha$ .
This means that:
$\frac{n(n-1)(n-2)\cdots(n-q+1)}{q!} = kq^\alpha$
Or, written in an other way:
$n = \frac{kq^{\alpha + 1}(q-1)!}{(n-1)(n-2)\cdots(n-q+1)}$

Now, for $1 \leq i \leq q-1$ , since $q$ is prime, $q$ and $(n-i)$ are coprimes if and only if $q \nmid (n-i)$ .
And that's true because, we supposed that $n \equiv 0 \mod q$ , so if $(n-i) \equiv 0 \mod q$ we would have $(n-i) \equiv 0 - i \equiv 0 \mod q$ , but $i < q$ , so that's absurd.
This imply that in the previous equation, the right hand side is an integer $n$ , but the denominator does not divide $q^{\alpha+1}$ ,
which means that the denominator must divide the rest of the numerator, but this imply that $q^{\alpha+1} \mid n$ , which is absurd because we supposed $\alpha$
to be the biggest exponent such that $q^\alpha \mid n$ .

Thus $q^{k} \nmid {n \choose q}$

Thread: Need a proof of the polynomial generalization of fermat's little theorem

LinkBack

Thread Tools

Display

[solved]Need a proof of the polynomial generalization of fermat's little theorem

Re: Need a proof of the polynomial generalization of fermat's little theorem

Similar Math Help Forum Discussions

Proving a generalization of Fermat's Little Theorem, involving the Euler phi function

Please critique possible proof of Fermat's Last Theorem

Congruence Proof (Application of Fermat's Theorem I believe)

Fermat's Last Theorem: an amateur proof

Can anyone show me the proof for Fermat Last Theorem for n=3

Search Tags