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

Question

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.

Answer 1

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.

Answer 2

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}}$.

Answer 3

One more way to think of this is that Wilson's Theorem says $$ (p-1)!-(p-1)\equiv0\pmod{p}\tag{1} $$ and because $(p-1)!\equiv p-1\equiv0\quad\left(\!\bmod\frac{p-1}{2}\right)$ $$ (p-1)!-(p-1)\equiv0\quad\left(\!\bmod\frac{p-1}{2}\right)\tag{2} $$ Since $\left(p,\frac{p-1}{2}\right)=1$, the Chinese Remainder Theorem says $$ (p-1)!-(p-1)\equiv0\quad\left(\!\bmod p\cdot\frac{p-1}{2}\right)\tag{3} $$