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 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.
    Last edited by Bakuriu; Sep 7th 2012 at 07: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 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}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

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

Search Tags

/mathhelpforum @mathhelpforum