Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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}$. –  anon Jun 10 '12 at 10:21

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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