7
$\begingroup$

$(p-1)! = -1 \bmod p$ where $p$ is prime.

I know that there are a lot of ways to prove it with all beauty of different sides of math:

1) Elementary way (to divide in pairs where $x_1 x_2 = \pm 1$)

2) To use Fermat's little theorem and Lagrange theorem with try to prove $x^{p-1} - 1 = (x-1)\dots(x-(p-1)))$

But my teacher wants me to prove it using theory of the finite Galois Fields. He wants me to use material which we study now.

We studied on our last lectures:

  • A set of residue classes
  • The decomposition field of the polynomial $x^{p^m} - x$
  • Cyclicity of the multiplicative group of the field
  • Giving the field by the root of an irreducible polynomial
  • Structure of finite fields
  • Isomorphism of the Galois fields
  • Automorphism of the Galois field
  • Representation of the Galois field by matrices

Maybe this proof is on this site, but I can't find it. And I can't think of proof based on things that I mentioned.

Sorry if it is some kind off-topic.

But does anybody know other proof based on mentioned material?

Hint from teacher: consider constant term of $x^{p-1} - 1 $, but it can't be the second proof, because it is based on theory of groups at all, the previous chapter of our lectures, not the theory of the finite Galois field, current chapter of our lectures.

$\endgroup$
  • 4
    $\begingroup$ Well I must say $x^{p-1}-1$ is awfully similar to $x^{p^m}-x$ with $m=1$. And with the "consider the constant term"-hint, I can't help but think they do mean the second proof $\endgroup$ – vrugtehagel Mar 6 '17 at 21:03
  • 2
    $\begingroup$ Here is a cool fact you might like to prove using results about splitting fields: If $p$ is an odd prime and $m $ is positive, then the product of all non-zero elements in $\mathbb F_{p^m}$ is $-1$. Wilson's theorem is the special case $m = 1$. $\endgroup$ – Kenny Wong Mar 6 '17 at 21:07
  • 1
    $\begingroup$ Well, really a lot of ideas :) $\endgroup$ – Lust_For_Love Mar 6 '17 at 21:41
6
$\begingroup$

By Vieta's Formulas we know that the constant term of a polynomial is equal to the product of the roots of the polynomial when the degree is even, and the negative of that when the degree is odd. Since $\mathbb{F}_p^\times$ is cyclic of order $p-1$, any non-zero element of $\mathbb{F}_p$ satisfies $x^{p-1}-1=0$. Handling the $p=2$ case separately, we see that $p$ is odd so $p-1$ is even, so $-1$ is the product of all the roots of $x^{p-1}-1$. We have already observed $p-1$ unique roots to this equation, and since $\mathbb{F}_p$ is a field, it has exactly $p-1$ roots and so the roots are precisely the the non-zero elements with no repeats and we are done.

In the comments, it is mentioned that this holds not just in $\mathbb{F}_p$ but generally in $\mathbb{F}_q$. This proof generalizes because, by construction, the elements of $\mathbb{F}_q$ satisfy $x^q-x=0$. Dividing both sides by $x$ and continuing as stated in the above proof yields the result. In the general theorem, the $p=2$ case still needs to be handled separately and is less trivial.

NB: This is the same concept as your proof 2, but justified using language of Field Theory. In general, the boundary between "Galois Theory Concepts" and "number theory concepts" is pretty loose when it comes to Modular Arithmetic.

$\endgroup$
  • $\begingroup$ Well, interesting idea. But I have some doubts. Is it correct to give field by reducible polynomial? We always did it with irreducible things... Sorry, I don't see all picture of the Galois field, but I try to understand them. $\endgroup$ – Lust_For_Love Mar 6 '17 at 21:29
  • $\begingroup$ @Dida sorry, I was confusing two related concepts. I changed my answer slightly to work. $\endgroup$ – Stella Biderman Mar 6 '17 at 21:36
  • $\begingroup$ @Dida added the generalization to $\mathbb{F}_q$. $\endgroup$ – Stella Biderman Mar 6 '17 at 21:49
5
$\begingroup$

My guess is that you may be expected to use cyclicity of $\Bbb{F}_p^*$. Let $g$ be a generator of this cyclic group of order $p-1$. Then there are two ways of listing the elements of the multiplicative group (in different orders): $$ \Bbb{F}_p^*=\{1,2,3,\ldots,p-1\}=\{1,g,g^2,\cdots,g^{p-2}\}. $$ This implies that in $\Bbb{F}_p$ we have $$ \begin{aligned} (p-1)!&=1\cdot2\cdot3\cdots(p-1)\\ &=1\cdot g\cdot g^2\cdots g^{p-2}\\ &=g^{0+1+2+3+\cdots+(p-2)}. \end{aligned} $$ In the last form the exponent is $$ E=\sum_{j=0}^{p-2}j=\frac12(p-2)(p-1). $$ Because $p$ is odd, we see that $E$ is an odd multiple of $(p-1)/2$.

On the other hand, by cyclicity, $g^{(p-1)/2}$ is of order two. As $-1$ is the only element of order two, we thus have $$ W:=g^{(p-1)/2}=-1, $$ and $$ g^E=W^{p-2}=(-1)^{p-2}=-1. $$

$\endgroup$
  • $\begingroup$ Seems good! Realy based on things that I want to use, but there I don't see usage of hint from my teacher to use constant term of $x^{p-1} - 1$. Well, will see tomorrow what my teacher really wants. $\endgroup$ – Lust_For_Love Mar 6 '17 at 21:44
  • $\begingroup$ What about when $p$ is even? $\endgroup$ – Stella Biderman Mar 6 '17 at 23:13
  • $\begingroup$ @Stella If $p=2$, then $(p-1)!=1=-1$, but IMHO that case is not very interesting? The corresponding argument in $K=\Bbb{F}_{2^m}$ then shows that $$\prod_{x\in K^*}x=g^{0+1+\cdots+2^m-2}=g^E,$$ where this time $$E=\frac12(2^m-2)(2^m-1)$$ is divisible by $2^m-1$. Therefore $g^E=1=-1$. $\endgroup$ – Jyrki Lahtonen Mar 7 '17 at 5:59
  • 2
    $\begingroup$ @JyrkiLahtonen Certainly, I just think it's worth a mention, and the phrasing of your proof implies that every prime number is odd. $\endgroup$ – Stella Biderman Mar 7 '17 at 6:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.