A positive integer $n$ is prime iff $\varphi(n)! \equiv -1 \pmod n$

230 Views Asked by At

Is this proof acceptable ?

Theorem 1 (Wilson)

A positive integer $n$ is prime iff $(n-1)! \equiv -1 \pmod n$

Theorem 2

A positive integer $n$ is prime iff $\varphi(n)! \equiv -1 \pmod n$ .

Proof

Necessity : $\textit{If}~ n~ \textit{is prime}~ \textit{then}~\varphi(n)! \equiv -1 \pmod n $

If $n$ is prime then we have $\varphi(n) = n-1$ and

by Theorem $1$ : $(n-1)!=-1 \pmod n$ ,

hence $\varphi(n)! \equiv -1 \pmod n$ .

Sufficiency : $\textit{If}~\varphi(n)! \equiv -1 \pmod n ~ \textit{then}~ n~ \textit{is prime}$

For $n=2$ and $n=6$ :

$\varphi(2)! \equiv -1 \pmod 2$ and $2$ is prime .

$\varphi(6)! \not\equiv -1 \pmod 6$ and $6$ is composite .

For $n \neq 2,6$ :

Suppose $n$ is composite and $p$ is the least prime such that $p \mid n$ ,

then we have $\varphi(n)! \equiv -1 \pmod p$ .

Since $\varphi(n) \geq \sqrt{n}$ for all $n$ except $n=2$ and $n=6$ , see [1]

and $p \leq \sqrt{n}$ it follows $p \mid \varphi(n)!$ , hence $\varphi(n)! \equiv 0 \pmod p$ a contradiction .

Therefore , $n$ must be prime .

Reference

[1]: Mitrinović, D. S. and Sándor, J. Handbook of Number Theory. Dordrecht, Netherlands: Kluwer, 1995.

1

There are 1 best solutions below

0
On BEST ANSWER

It is correct.
If $n$ is composite then $\gcd(\phi (n)!,n)\geq p$ where $p$ denotes the smallest prime divisor of $n$.
Clearly $p$ is not equal to $-1$ mod n and therefore is true.
Nice one but not very helpfull in practice.