Characterization of primes

**EinStone** · May 20th 2010, 03:39 AM

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.)

**Bacterius** · May 20th 2010, 04:40 AM

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.

**Laurent** · May 20th 2010, 05:28 AM

Originally Posted by EinStone

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.

Thread: Characterization of primes

LinkBack

Thread Tools

Display

Characterization of primes

Similar Math Help Forum Discussions

A characterization of an almost everywhere constant variable

Characterization of linear dependence.

Pointwise Characterization of Angle Bisector

Topological characterization of Continuity

Continuity characterization help

Search Tags