1
$\begingroup$

I wish to show that $(p-2)! \equiv 1 \pmod p$ for a prime $p \ge 3$ using the fact that $(p-1)! \equiv -1 \pmod p$. (Deducing the latter is a later, and more advanced task.)

We have that $(p-1)(p-2)! \equiv -1 \pmod p$. We have that $(p-1) \equiv (p-1)\pmod p$, but this does not help. A weird thought along the lines of "What if I went to the other way around?" popped in my head, I wrote $(p-1) \equiv -1 \pmod p$ and $(-1)(p-2)! \equiv -1 \pmod p \implies (p-2)! \equiv 1 \pmod p$.

Much to my surprise, this was the right answer. I don't understand much of it, so this is a classic example of the right answer for the wrong reasons. If my methods are indeed valid; why do they work? If they are not; how would one normally go about solving this task, and how does one validate each step, basing ones arguments in elementary arithmetic?

$\endgroup$
6
  • 2
    $\begingroup$ Why is it a weird thought? $p - 1 \equiv -1$, so replacing $p-1$ by $-1$ is valid. Then you just multiply both sides by $-1$. $\endgroup$
    – TMM
    Mar 17, 2014 at 16:30
  • $\begingroup$ I don't get it, which is why I classified it as weird. Why is $p - 1 \equiv -1 \pmod p$? Isn't $p-1 \equiv p-1 \pmod p$? $\endgroup$
    – Andrew Thompson
    Mar 17, 2014 at 16:32
  • $\begingroup$ Perhaps then you should revisit the basics of congruences and modular arithmetic. What does it mean if $a \equiv b \mod p$? Can you then prove that $p-1 \equiv -1 \mod p$? $\endgroup$
    – TMM
    Mar 17, 2014 at 16:34
  • 1
    $\begingroup$ We say that $a = b \bmod n $ if n divides $a - b$. That's just the definition. And $p$ does indeed divide $(p-1) - (-1)$. $\endgroup$
    – Ink
    Mar 17, 2014 at 16:34
  • 1
    $\begingroup$ @DonAntonio I am to deduce that in a later task, as mentioned in the OP. $\endgroup$
    – Andrew Thompson
    Mar 17, 2014 at 16:35

2 Answers 2

Reset to default
1
$\begingroup$

The focus of this answer would be on its explanation rather than its content.

Notice that for all prime (integers, more generally) $p \ge 3$, we have

$$(p - 1)! = (p-1)(p-2)!$$

Now, suppose $(p-1)! \equiv -1 \pmod{p}$. This is the assumption in the question. It is the consideration we have to make. Then, taking both sides modulo $p$, we have

$$-1 \equiv (p-1)(p-2)! \pmod p$$

But $p -1$ gives a remainder of $-1$ when divided by $p$. In other words, $$p-1\equiv -1\pmod p$$

Substituting back, we have:

$$-1\equiv -1\cdot(p-2)!\pmod p$$

Multiplying both sides by $-1$, we have

$$(p-2)! \equiv 1 \pmod p$$

What this says is that

$$(p-1)!\equiv -1 \pmod p \implies (p-2)! \equiv 1 \pmod p$$

for all prime $p \ge 3$.

Now, I believe you would have to prove $p \ge 3$ prime $\implies (p-1)! \equiv -1 \pmod p$, to prove that the above deduction is true for $p \ge 3$ prime.

$\endgroup$
4
  • $\begingroup$ Thank you. My misunderstanding was when working with groups of the likes of $\mathbb{Z}_n$, all numbers in the interval $[0, n-1]$ "equaled themselves", that is, I did not have to find any remainder after division. Using long division on $(p-1) / p$, one may get the remainder $p-1$ if one chooses to set it equal to $0$, or a remainder of $-1$ if one sets it equal to $1$. If I understand your answer correctly, both are acceptable methods, although the latter is the one needed to solve the task. $\endgroup$
    – Andrew Thompson
    Mar 17, 2014 at 17:04
  • 1
    $\begingroup$ Yes, indeed! Saying "a remainder of $-1$ after a division by $p$" is exactly the same as saying "a remainder of $p-1$ after division by $p$", because the integers modulo $p$ are closed and "wraps around" under addition (and subtraction), you could say. $\endgroup$
    – Yiyuan Lee
    Mar 17, 2014 at 17:07
  • $\begingroup$ Wait, is $8 \mod 16 = 8$ equivalent to saying $8 \mod 16 = -8$? $\endgroup$
    – Andrew Thompson
    Mar 17, 2014 at 19:27
  • $\begingroup$ Yes it is equivalent $\endgroup$
    – Yiyuan Lee
    Mar 18, 2014 at 2:07
0
$\begingroup$

For $p > 1$, the modular inverse of $(p - 1)$ is $(p - 1)$. From this, we have \begin{align*} (p-1)! &\equiv_p -1\\ \Rightarrow (p-1)(p-2)! &\equiv_p -1\\ \Rightarrow (p-1)(p-1)(p-2)! &\equiv_p 1-p\\ \Rightarrow (p-2)! &\equiv_p 1 - p \equiv_p 1 \end{align*}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .