# Backward direction – Wilson’s Theorem – p is prime $\iff (p-1)!\equiv-1(mod\ p)$.

(1) How can you preconceive to prove by contradiction?

Prove by contradiction. Suppose $$n$$ is composite. This means there exists a divisor $$d|n$$ such that $$1. We are given that $$(n-1)!\equiv-1(mod\ n)$$ which means $$n|[(n-1)!+1]$$. Since $$d|n$$ so

$$d|[(n-1)!+1]$$ which gives $$dk=\color{seagreen}{ (n-1)! }+1$$ for some integer $$k$$.

From the first line, and independently from the above paragraph, we have $$1 < d < n$$. Therefore $$d|(n-1) ! \implies \color{seagreen}{dm=(n-1)}$$ ! for some integer $$m$$.

(2) How can you preconceive to consider $$1 < d < n$$ alone and separately, in the middle of the proof?

(3) Why $$d|(n - 1)!$$ ? By reason of $$1 < d < n \iff 2 \le d \le n - 1$$?

Substitute $$dm$$ into $$dk$$, $$dk=dm+1 \iff d(k-m)=1 \iff d$$ divides 1.

Origin — p4 — better than Jones p82 Question 4.20

• The proof by contradiction comes after one finds out what's happenin' when $n$ is composite. Minor fooling around with a couple of numerical examples shows that in that case $(n-1)!$ will have stuff in common with $n$. Then one writes up a tight argument that pins it down. If you don't want to mention contradiction, you can write a non-contradiction proof that if $n$ is composite, then $(n-1)!$ and $n$ have a common divisor $d\gt 1$. May 10 '14 at 20:46

(1) How can you preconceive to prove by contradiction?

Consider a few examples. $3! = 6$, $4! = 24$, $5! = 120$. These are highly divisible numbers, and in particular $(n-1)!$ contains every number up to $n-1$. You therefore expect that if $n$ is not prime, then $(n-1)!$ will be divisible by $n$. Hence, prove by contrapositive, or alternately proof contradiction will do the trick. (Note: $n = 4$ is the only exception where $(n-1)!$ is not divisible by $n$, but it still has some of the same factors.)

Beyond that, note that proof by contradiction, in general, is easier than both a normal proof and a proof by contrapositive, because you get to assume twice as many things. Thus, when stuck, always try a proof by contradiction.

(2) How can you preconceive to consider $1 < d < n$ alone and separately, in the middle of the proof?

You essentially want to show that $(n-1)!$ has some of the same factors as $n$. Thus naturally you find some $d$ which should be in the expansion of $(n-1)!$. So you need $1 < d < n$.

(3) Why $d|(n - 1)!$ ? By reason of $1 < d < n \iff 2 \le d \le n - 1$?

Any positive integer less than $n$ is included in the expansion $$(n-1)! = (n-1)(n-2) \cdots (2)(1).$$ In particular for $d$ to be in this expansion, we need $2 \le d \le n-1$. So yes, that is the correct reason.