4
$\begingroup$

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.

  • 3
    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}$.2012-06-10

3 Answers 3

1

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

4

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

2

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.