9
$\begingroup$

Suppose that $p$ is a prime. Suppose further that $h$ and $k$ are non-negative integers such that $h + k = p − 1$.

I want to prove that $h!k! + (−1)^h \equiv 0 \pmod{p}$

My first thought is that by Wilson's theorem, $(p-1)! \equiv -1 \pmod{p}$, and $h!k!$ divides $(p-1)!$ (definition of a binomial). Where would I go from here?

$\endgroup$
0
6
$\begingroup$

Wilson's theorem $\Rightarrow$ any complete system of representatives $\,r_i\,$ of $\rm\color{#c00}{nonzero}$ remainders mod $\,p\,$ has product $\equiv -1,\,$ by $\,r_i\equiv i\,\Rightarrow\,\displaystyle \prod_{i=1}^{p-1} r_i\equiv \prod_{i=1}^{p-1} i \equiv (p-1)!\equiv -1\,$ by inductive extension of Congruence Product Rule. In particular this is true for any sequence of $\,p\,$ consecutive integers, after removing its unique $\rm\color{#c00}{multiple}$ of $\,p.\,$ Your special case is the sequence $$\, \underbrace{\color{#90f}{-h},\,-h\!+\!1,\ldots,\color{#0a0}{-1}}_{\!\!\textstyle\equiv\,\color{#90f}{k\!+\!1},\,k\!+\!2,\cdots,\color{#0a0}{p\!-\!1}}\!\!\!\!,\require{cancel}\color{#c00}{\cancel{0,}} 1,2,\ldots, k\ \ \ \text{whose product is}\,\ \ (-1)^h h!\,k!\equiv -1\qquad$$

since $\,\color{#90f}{-h\equiv k\!+\!1}\,$ by $\,h\!+\!k\!+\!1\equiv p\equiv 0$

Remark $\ $ This is slight reformulation of the Wilson reflection formula mentioned yesterday

$$ k! = (p\!-\!1\!-\!h)! \equiv \frac{(-1)^{h+1}}{h!}\!\!\pmod{\! p},\,\ \ 0\le h< p\ {\rm prime}\qquad $$

$\endgroup$
4
$\begingroup$

Use the fact that

$$h! = (-1)^h (p-1)(p-2) \dots (p-h) \mod p$$

$\endgroup$
1
  • $\begingroup$ Ah, so h!k! becomes [(-1)^h](p-1)! mod p, which is just -(-1)^h. Thanks so much! $\endgroup$
    – Johan
    Feb 27 '11 at 22:59

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.