4
$\begingroup$

I need help understanding Wilson's Theorem. I was reading a post on this blog explaining this theorem.

$(p-1)! \equiv p -1 \bmod p$

$(p-1)! ≡ -1 \bmod p$

How is $p - 1 \pmod p$ equal to $-1 $?

$\endgroup$
  • 1
    $\begingroup$ We have $p-1\equiv -1\pmod{p}$, since the difference between the two numbers is divisible by $p$. $\endgroup$ – André Nicolas Sep 24 '13 at 6:35
  • $\begingroup$ If p was 5, wouldn't (4-1) mod p be equal to 3? This is where I am confused. $\endgroup$ – Quaxton Hale Sep 24 '13 at 6:40
  • $\begingroup$ Yes, (4-1) mod p would be equivalent to 3, but it would not be equivalent to (p-1) = (5-1), which is equivalent to both 4 and -1. $\endgroup$ – qaphla Sep 24 '13 at 6:42
  • 1
    $\begingroup$ It is $4-(-1)=5$. $\endgroup$ – André Nicolas Sep 24 '13 at 6:46
  • 3
    $\begingroup$ The point that might be troubling you is that in mathematics, $\ldots \equiv \ldots \mod p$ is a relation, not a function. So $5 - 1 \equiv 4 \mod 5$ and $5 - 1 \equiv -1 \mod 5$ are both true statements. $\endgroup$ – Robert Israel Sep 24 '13 at 6:48
3
$\begingroup$

We have $a\equiv b\pmod{m}$ if and only if $m$ divides the difference $a-b$.

Let $a=p-1$, $b=-1$, $m=p$. Then $a-b=p-1-(-1)=p$. This is divisible by $p$.

In general, $p-a\equiv -a\pmod{p}$: same argument.

Remark: There are unfortunately two different but related uses of "mod." The first, wich was the first line of the answer, is the one primarily used in mathematics. The second, primarily used in computer science, is to write $a\bmod{m}=b$ if $b$ is the remainder when you divide $a$ by $m$. There is a relationship between the two notions: $$a\equiv b\pmod{m}\quad\text{if and only if}\quad a\bmod{m}=b\bmod{m}.$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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