The Converse Of Wilson's Theorem

Wilson's Theorem states:

$$ n \text{ is prime} \implies (n - 1)! ≡ -1 \bmod n $$

The converse of this would be:

$$ (n - 1)! ≡ -1 \bmod n \implies n \text{ is prime} $$

Let \(n = ab\) where \(a\) and \(b\) are integers, and let \(a \le \sqrt{n}\).

$$ 1 \le a \le \sqrt{n} \implies a|(n-1)! $$

Since \((n - 1)! ≡ -1 \bmod n\). This means:

$$ n | (n - 1)! + 1 $$

Since \(a|n\):

$$\begin{gather} a | (n - 1)! + 1 ∧ a|(n-1)! \\ \implies a|((n-1)! + 1) - (n-1)! \implies a|1\end{gather}$$

This means if \(a \le \sqrt{n}\), then \(a=1\), which means \(n\) is prime.

Styles

(uses cookies)