Results 1 to 3 of 3

Math Help - Characterization of primes

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    169

    Characterization of primes

    Show that (x+1)^n \equiv x^n + 1^n \mod n in \mathbb{Z}[x] if and only if n is a prime.
    (In other words,all coefficients in the difference polynomial (x + 1)^n - (x^n + 1^n) are divisible by n. This is a relation in the polynomial ring, not for individual integers x.)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Hello,
    I haven't thought about the proof yet but are you sure it is a IFF statement ? If it was, primality testing would be trivial, which is not the case. Unless I'm misunderstanding the statement which is quite probable.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by EinStone View Post
    Show that (x+1)^n \equiv x^n + 1^n \mod n in \mathbb{Z}[x] if and only if n is a prime.
    (In other words,all coefficients in the difference polynomial (x + 1)^n - (x^n + 1^n) are divisible by n. This is a relation in the polynomial ring, not for individual integers x.)
    By the binomial formula, you question boils down to: show that n is prime if and only if n divides {n\choose k} for all 1\leq k\leq n-1.

    Remember {n\choose k}=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1}.

    Assume n is prime. Then it divides the numerator but not the denominator. Since it is prime, we conclude it divides the binomial coefficient. (justify that properly)

    Assume n is composite. Let p be any prime factor of n. Of course, 2\leq p\leq n-1. It divides both the largest terms of the numerator and of the denominator of {n\choose p}, and it doesn't divide any other factor since there are p of them, and only 1 number among p consecutive ones is divisible by p. Thus, after simplification by p, the numerator is not divisible by p, so that the binomial coefficient isn't either.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A characterization of an almost everywhere constant variable
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: March 7th 2011, 11:12 PM
  2. Characterization of linear dependence.
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 15th 2010, 02:22 AM
  3. Pointwise Characterization of Angle Bisector
    Posted in the Geometry Forum
    Replies: 1
    Last Post: September 5th 2010, 02:32 PM
  4. Topological characterization of Continuity
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: November 10th 2009, 04:36 AM
  5. Continuity characterization help
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: May 30th 2009, 06:48 PM

Search Tags


/mathhelpforum @mathhelpforum