Results 1 to 2 of 2

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

  1. #1
    Sep 2012

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

    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.
    Last edited by Bakuriu; Sep 7th 2012 at 06:12 AM. Reason: Add the solved tag
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Sep 2012

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

    Okay, I think I came up with a proof.

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

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

    Thus $\displaystyle q^{k} \nmid {n \choose q}$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Mar 14th 2012, 08:18 PM
  2. Replies: 2
    Last Post: Oct 30th 2010, 02:04 PM
  3. Replies: 1
    Last Post: Mar 9th 2009, 12:51 PM
  4. Fermat's Last Theorem: an amateur proof
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Dec 19th 2008, 06:43 AM
  5. Replies: 3
    Last Post: Nov 13th 2006, 10:17 AM

Search Tags

/mathhelpforum @mathhelpforum