Confirm that $(n-1)! \equiv -1 \pmod{n}$ iff $n$ is prime [Wilson's Theorem]

Just how can I show that $(n-1)!$ is conforming to $-1 \pmod{n}$ if and also just if $n$ is prime?

Many thanks.

2019-05-06 21:42:37
Source Share
Answers: 4

[NOTE : it appears that there is some distinction in between sneak peek and also real result, so rather if making use of (mod p) I stick to (p) ]

to show that $(p-1)! \equiv -1 (p)$ without clearly make use of group theory, possibly the most basic course is : (the adhering to thinks $p$ is weird, yet if $p=2$ after that the outcome is prompt)

  1. offered $n \ne 0$, all values $n, 2n, ... (p-1)$ $n$ are various mod $p$. Or else, if $hn \equiv kn (p)$ after that $(h-k)n \equiv 0 (p)$ versus the theory that $p$ is prime.

  2. this suggests that each $n$ has an inverted mod $p$, that is for each and every $n$ there is a $m$ such that $mn \equiv 1 (p)$.

  3. the formula $x^2\equiv 1 (p)$ might be created as $(x+1)(x-1) \equiv 0 (p)$ ; consequently its only remedies are $x \equiv 1 (p)$ and also $x \equiv -1 (p)$. For each and every various other number $n$, an inverted $m$ has to exist (as a result of the pigeonhole concept) yet $m \neq n$.

  4. we are virtually done. Allow's couple every number from $2$ to $p-2$ with its very own inverse. Their item is $1 (p)$, so they do not count in the general total amount. $1$ does not count either ; it continues to be simply $p-1$, that is $-1 (p)$ as asked for.

2019-05-08 19:23:12

Here are a pair feasible evidence of Wilson's theory for $p>2$ ($p=2$ is conveniently examined) :

  1. We have that $x^{p-1}-1$ has origins $1,2,\ldots,p-1$ over $\mathbb{Z}/p\mathbb{Z}$ (by Fermat's Little Theorem). Yet as $\mathbb{Z}/p\mathbb{Z}$ is an area, we have one-of-a-kind factorization of polynomials, to make sure that $x^{p-1}-1=(x-1)(x-2)\ldots(x-(p-1))$. Contrasting constant terms possesses Wilson's theory.

  2. Allow $g$ be a primitive root modulo $p$. After that $(p-1)!\equiv g\times g^2\times \ldots \times g^{p-1}=g^{p\frac{p-1}{2}}\equiv g^{\frac{p-1}{2}}\bmod{p}$ by Fermat's Little Theorem, and also $g^{\frac{p-1}{2}}\equiv -1 \bmod{p}$ due to the fact that if $(g^{\frac{p-1}{2}})^2=g^{p-1}\equiv 1 \bmod{p}$ and also $g^{\frac{p-1}{2}}\not \equiv 1 \bmod{p}$ by the definition of primitive origin.

2019-05-08 19:07:39

$$n\text{ is prime if }(n-1)! \equiv -1 \pmod n$$

This instructions is very easy. If $n$ is composite, after that there exists $k|n$ and also $k\lt n$. So $k|(n-1)!$ and also $k \equiv 1 \pmod n$. This suggests $k$ demands to separate $1$. So $n$ has to be prime (or $1$, yet we can remove this by replacement).

$$(n-1)! \equiv -1\text{ if }n\text{ is prime}$$

Wikipedia has two proofs of this outcome called Wilson's theory. The first evidence just makes use of standard abstract algebra therefore needs to be easy to understand with an excellent expertise of modular math. Simply in instance, I confirm listed below that each component $1, 2, ... n-1$ has an one-of-a-kind inverted $\mod n$.

They make use of the reality that integers $\mod p$ create a team and also therefore that each component $x$ not conforming $0$ has a multiplicative inverse (a number $y$ such that $xy \equiv 1 \mod n$. We show this as adheres to. Intend $n \nmid x$, for $n$ prime. From the individuality of prime factorisations, $xn$ is the first item of $x$, after $0x$, divisible by $n$ (usage prime factorisation theory). If we consider the collection $kn \mod n$, this cycles and also have to have cycle size $n$. Consequently, each component $x, 2x,... nx$ have to be various modulo $n$, consisting of one, $y$, with $xy \equiv 1 \mod n$. In addition, as a result of the cycle size being $n$, each just one of those components will certainly be an inverted. So every component has an one-of-a-kind inverse (although 1 and also - 1 are their very own inverses).

2019-05-08 18:31:19

Hint $\rm\ (p\!-\!1)!\bmod p\,$ is the item of all elts of $\rm\, {\mathbb F}_p^*.\,$ The map $\rm n \mapsto n^{-1}$ is a permutation of $\rm\:{\mathbb F}_p^*\:$ of order $2$ so it decays right into cycles of size $1$ or $2,$ which dividing the item. Each $2$ - cycle $\rm (n, n^{-1})$ has item $1$ so is deletable, leaving just the item of $1$ - cycles $\rm (n)$. They please $\rm\: n^{-1} = n \Rightarrow n^2 = 1 \Rightarrow n = \color{#0a0}{- 1}\,$ or $\color{#c00}1,\,$ by $\rm{\mathbb F}_p$ an area. So the item lowers to $\,\color{#0a0}{-1}\cdot\color{#c00}1 = -1$.

This generalises : if a limited abelian group has an one-of-a-kind component of order $2$ after that it amounts to the item of all the components ; or else the item is $1$, as an example see this thread for tips (this is occasionally called the group - logical kind of Wilson's Theorem ).

Notification just how we've manipulated the presence of a proportion - below an involution that generates an all-natural pairing of elts. Regularly involution and also representation proportions exist at the heart of classy evidence, as an example see the classy evidence by Liouville, Heath-Brown and also Zagier, that every prime $\equiv 1 \pmod 4$ is an amount of $2$ squares, or the little - well-known attractive reflective generation of the ternary tree of primitive Pythagorean triples as a result of Aubry.

2019-05-08 16:54:21