Results 1 to 3 of 3

Thread: Characterization of primes

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    169

    Characterization of primes

    Show that $\displaystyle (x+1)^n \equiv x^n + 1^n \mod n$ in $\displaystyle \mathbb{Z}[x]$ if and only if n is a prime.
    (In other words,all coefficients in the difference polynomial $\displaystyle (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 $\displaystyle (x+1)^n \equiv x^n + 1^n \mod n$ in $\displaystyle \mathbb{Z}[x]$ if and only if n is a prime.
    (In other words,all coefficients in the difference polynomial $\displaystyle (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 $\displaystyle n$ is prime if and only if $\displaystyle n$ divides $\displaystyle {n\choose k}$ for all $\displaystyle 1\leq k\leq n-1$.

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

    Assume $\displaystyle 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 $\displaystyle n$ is composite. Let $\displaystyle p$ be any prime factor of $\displaystyle n$. Of course, $\displaystyle 2\leq p\leq n-1$. It divides both the largest terms of the numerator and of the denominator of $\displaystyle {n\choose p}$, and it doesn't divide any other factor since there are $\displaystyle p$ of them, and only 1 number among $\displaystyle p$ consecutive ones is divisible by $\displaystyle p$. Thus, after simplification by $\displaystyle p$, the numerator is not divisible by $\displaystyle 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: Mar 7th 2011, 11:12 PM
  2. Characterization of linear dependence.
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Dec 15th 2010, 02:22 AM
  3. Pointwise Characterization of Angle Bisector
    Posted in the Geometry Forum
    Replies: 1
    Last Post: Sep 5th 2010, 02:32 PM
  4. Topological characterization of Continuity
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: Nov 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