From: Jonathan Michaels
Claim: Let p be a prime, and let e_k(x_1, x_2, ..., x_(p-1)) be the k-th
elementary symmetric polynomial for some k <= p-2. Then e_k(1, 2, ..., p-1) is
congruent to 0 (mod p).
Proof: Consider the following function:
(1) f(x) = (x-1)*(x-2)*...*(x-(p-1)).
It consists of the product of p-1 terms, each of which is a polynomial of
degree one, so f(x) is a polynomial of degree p-1. Hence, f(x) can also be
written in standard polynomial form as follows:
(2) f(x) = a_0*x^(p-1) + a_1*x^(p-2) + ... + a_(p-1) where all a_k are as-yet
undetermined constants.
Note that f(x) expressed as a product of p-1 single-degree polynomials as in
(1) can be expanded using repeated applications of the distributive law of
multiplication over addition, resulting in 2^(p-1) terms. This is because each
term is the product of (either x or -1)*(either x or -2)*...*(either x or
-(p-1)), that is, the product of p-1 factors, for each of which there are 2
independent choices. Thus by the Product Rule, 2^(p-1) terms result.
Lemma 0.1: In (2) above, a_0 = 1.
Only one of the abovementioned 2^(p-1) terms contributes to the x^(p-1) term
of polynomial (2), because to have a power of x to the p-1, each of the above
choices must be 'x', which can happen in only one way. Furthermore, since all
of the factors in the term that contribute to the x^(p-1) term of polynomial
(2) are x, none of the factors are constants, so the coefficient of said term,
a_0, is 1.
Lemma 0.2: In (2) above, a_(p-1) is congruent to -1 (mod p).
Again, only one of the abovementioned 2^(p-1) terms contribute to the constant
term of the polynomial (2), because each of the choices of factors must /not/
be 'x', that is, they must choose the constant. Thus, the constant term of the
polynomial (2), a_(p-1), is (-1)*(-2)*...*(-(p-1)) = (-1)^(p-1) * (p-1)!.
(-1)^(p-1) is congruent to 1 by Fermat's Little Theorem, and (p-1)! is
congruent to -1 by Wilson's Theorem (I can prove this quickly if you want.)
Thus, a_(p-1) is congruent to 1*(-1) = -1 (mod p).
Lemma 0.3: In (2) above, a_k = (-1)^k * e_k(1, 2, ..., p-1) for all k such
that 0 < k < p-1.
To see this, we must look closely at the expansion of (1) into 2^(p-1) terms.
The different terms that contribute to the x^(p-k-1) term of (2) consist of all
possible ways to multiply together p-k-1 'x's and k constants {-1, -2, ...,
-(p-1)} from the p-1 terms of (1), and these different terms are added up to
yield the coefficient a_k of the x^(p-k-1) term of (2). Put another way, a_k
is equal to the sum of all the possible products of k unique factors chosen
from {-1, -2, ..., -(-p-1)}. Note that this is precisely the definition of
e_k(-1, -2, ..., -(p-1)) where e_k is the k-th elementary symmetric
polynomial. Furthermore, from each product term of the sum that forms a_k, a
(-1)^k can be factored out (leaving all positive factors), and since this
(-1)^k is present in each term of the sum, it can be removed from the whole
thing, showing that a_k = (-1)^k * e_k(1, 2, ..., p-1).
Now we are ready to prove the main result. Note that for all x in {1, 2, ...,
p-1}, f(x) = 0 because one of the terms in (1) will be equal to zero. So,
using the form of (2):
(3) a_0*x^(p-1) + a_1*x^(p-2) + ... + a_(p-1) = 0 for all x in {1, 2, ...,
p-1}.
Now we work mod p. x^(p-1) is congruent to 1 mod p by Fermat's Little Theorem,
and a_0 = 1 by Lemma 0.1, so the first term on the left side of (3) is
congruent to 1*1 = 1. The last term, a_(p-1), is congruent to -1 mod p by
Lemma 0.2, which gives:
(4) 1 + a_1*x^(p-2) + a_2*x^(p-3) + ... + a_(p-2)*x - 1 = 0 (mod p) for all x
in {1, 2, ..., p-1}.
Cancelling the 1 and -1,
(5) a_1*x^(p-2) + a_2*x^(p-3) + ... + a_(p-2)*x = 0 (mod p) for all x in {1,
2, ..., p-1}.
Now, note that we have an unknown modular polynomial of degree p-2, and we know
its value at p-1 points. We have enough points to uniquely determine the
polynomial; that is, there exists a unique set of values a_1, a_2, ..., a_(p-2)
mod p that satisfy (5). The set of values a_1 = a_2 = ... = a_(p-2) = 0 (mod
p) satisfies (5), and by uniqueness, this is the only such set. This brings us
to our conclusion. a_k = 0 (mod p) for all k such that 0 < k < p-1, and from
Lemma 0.3, a_k = (-1)^k * e_k(1, 2, ..., p-1) for all k such that 0 < k < p-1;
thus:
(6) (-1)^k * e_k(1, 2, ..., p-1) = 0 (mod p) for all k such that 0 < k < p-1,
and since (-1)^k is never equal to 0, it must be the case that e_k(1, 2, ...,
p-1) = 0 (mod p) for all k such that 0 < k < p-1. QED.
Jonathan