# Prove that $(p-1)! \equiv (p-1) \pmod{1+2+3+\cdots+(p-1)}$

Given a prime number $p$ , establish the congruence: $$(p-1)! \equiv (p-1) \pmod{1+2+3+\cdots+(p-1)}$$

I have proceeded like this:
\begin{align*}&(p-1)! \equiv (-1) \pmod{p} \quad \quad \quad \text{by Wilson's Theorem}\\ &(p-1)! \equiv 0 \pmod{\frac{p-1}{2}} \end{align*}
Then I know that I have to apply Chinese remainder theorem but I don't have a thorough understanding of it.So please give me an elaborate answer to this question with respect to Chinese remainder theorem.

-
It's enough to know that there is a unique evaluation modulo $p(p-1)/2$, so it suffices to check that $p-1\equiv-1\bmod p$ and $p-1\equiv0\bmod\frac{p-1}{2}$. –  anon Jun 10 '12 at 10:21

Note that $1 + 2 + ... + p-1 = \frac{p(p-1)}{2}$ and you can assume that $p > 2$ is odd.

You have a congruence $$x = (p-1)! \equiv -1 (\bmod p)$$ $$x = (p-1)! \equiv 0 (\bmod (p-1)/2)$$

Denote $m = p(p-1)/2$ and $m_1 = p , m_2 = (p-1)/2$. Denote $n_i = m/m_i$.

The Chinese Remainder Theorem goes as follows (to our simple case): to solve $x \equiv a_i (\bmod m_i)$ we have to use the fact that $n_i,m_i$ are coprime and thus there are $s_i$ and $r_i$ such that $s_i n_i + r_i m_i = 1$. In our case you can check that $$1 \cdot p - 2 \cdot (p-1)/2 = 1$$ so $n_1 = (p-1)/2 , s_1 = -2$ and $n_2 = p , s_2 = 1$. The general solution is $$x \equiv \sum_{i}a_i s_i n_i \quad (\bmod m)$$ and in our case: $$(p-1)! \equiv -1 \cdot (-2)(p-1)/2 + 0 \cdot 1 \cdot p \equiv p-1 \quad (\bmod \frac{p(p-1)}{2})$$

A general layout of the Chinese algorithm can be found in English Wikipedia though the algorithm in the Hebrew Wikipedia is clearer to my taste.

-

One more way to think of this is that $$(p-1)!-(p-1)\equiv0\pmod{p}\tag{1}$$ and $$(p-1)!-(p-1)\equiv0\quad\left(\text{mod }\frac{p-1}{2}\right)\tag{2}$$ Since $\left(p,\frac{p-1}{2}\right)=1$, we have that $$(p-1)!-(p-1)\equiv0\quad\left(\text{mod }p\cdot\frac{p-1}{2}\right)\tag{3}$$

-

First of all, to get the formalities out of the way, since $p$ and $\frac{p-1}{2}$ are relatively prime, there is a unique evaluation$\pmod {p\cdot\frac{p-1}{2}}$ which corresponds to the two remainders you have. Once you're there, we have $$(p-1) \equiv 0 \pmod{\frac{p-1}{2}}$$ as well as $$(p-1) \equiv (-1) \pmod p$$ Which means that $(p-1)$ and $(p-1)!$ fulfills the same relations, hence they must be congurent$\pmod {p\cdot\frac{p-1}{2}}$.

-