A natural number $n>2$ is a prime iff $\prod_{k=1}^{n-1} k \equiv n-1 \pmod {\sum_{k=1}^{n-1} k}$

335 Views Asked by At

Is this proof acceptable ?

Theorem 1 (Wilson). A natural number $n>1$ is a prime iff: $$(n-1)! \equiv -1 \pmod n.$$

Theorem 2. A natural number $n>2$ is a prime iff: $$\prod_{k=1}^{n-1} k \equiv n-1 \pmod {\sum_{k=1}^{n-1} k}.$$

Proof

Necessity: If $n$ is a prime, then $$\prod_{k=1}^{n-1} k \equiv n-1 \pmod {\sum_{k=1}^{n-1} k}.$$ If $n$ is an odd prime, then by Theorem $1$ we have $$\prod_{k=1}^{n-1} k \equiv n-1 \pmod n$$ Hence, $n \mid ((n-1)!-(n-1))$ and therefore $n \mid(n-1)((n-2)!-1)$.

Since $ n \not\mid (n-1)$ it follows $n \mid ((n-2)!-1)$ , hence $$\frac{n(n-1)}{2} \mid (n-1)((n-2)!-1),$$ thus $$\prod_{k=1}^{n-1} k \equiv n-1 \pmod {\sum_{k=1}^{n-1} k}.$$

Sufficiency: If $$\prod_{k=1}^{n-1} k \equiv n-1 \pmod {\sum_{k=1}^{n-1} k}$$ then $n$ is a prime.

Suppose $n$ is a composite and $p$ is a prime such that $p \mid n$, then since $\sum_{k=1}^{n-1} k = \frac{n(n-1)}{2}$ it follows $p \mid \sum_{k=1}^{n-1} k$ .

Since $$\prod_{k=1}^{n-1} k \equiv n-1 \pmod {\sum_{k=1}^{n-1} k},$$ we have $$\prod_{k=1}^{n-1} k \equiv n-1 \pmod {p}.$$

However , since $p \leq n-1$ it divides $\prod_{k=1}^{n-1} k$, and so $$\prod_{k=1}^{n-1} k \equiv 0 \pmod p,$$ a contradiction . Hence $n$ must be prime.

Q.E.D.

2

There are 2 best solutions below

0
On BEST ANSWER

After "thus" I had to backtrack because I didn't realize that $(n-1)! - (n-1)$ and $ (n-1) \cdot ((n-2)!-1)$ are the same number, you only said that they are both divisible by $n$ but the conclusion doesn't follow from that alone; also you ought to point out that $\sum_{k=1}^{n-1}{k}=\frac{n \cdot (n-1)}{2}$ here instead of later.

Also it would be a bit simpler to replace $n-1$ with $n$ everywhere, it would make the summation identity more recognizable too so maybe you don't even need to mention it at all.

Aside from those minor quibbles, it is clear and convincing!

0
On

"Suppose $n$ is a composite and $p$ is a prime such that $p \mid n$, then since $\sum_{k=1}^{n-1} k = \frac{n(n-1)}{2}$ it follows $p \mid \sum_{k=1}^{n-1} k$."

This only follows if $p$ is an odd prime (consider $p=2, n=6$). It's easy to dismiss the other options, but this should explicitly be part of the proof.