# Prime number characterisation using congruences

I want to prove that $n$ is prime. From the Wilson's theorem it follows that $n$ is prime if and only if $$(n-1)! + 1 \equiv 0 \pmod{n}$$

However, in my proof, I reduce the congruences to the following form:

$$24((n-1)! + 1) \equiv 0 \pmod{n}$$

I believe I can divide the congruence by 24 only if 24 is coprime to $n$, so I can safely deduce that if $n$ is coprime to 24, it is also prime. Otherwise I do not know what can I find out from the following congrunce. Numerical calculations suggest that this successfully characterises primes grater than 24, but I fail to see why. Can anyone please explain to me which (probably obvious and simple) step I am missing?

Edit:

Perhaps the question was not clear enough. It can be expressed in shorter form, without the background:

Given the congruence

$$24((n-1)! + 1) \equiv 0 \pmod{n}$$

what can one tell about the primality of $n$?

• Indeed I did misunderstand your question, although some of what I say in my answer looks relevant to what you actually meant. I am still slightly confused though: where did the factor of $24$ come from?? – Pete L. Clark Apr 22 '13 at 19:50
• In my opinion a "less localized" question would be: prove or disprove: for any positive integer $a$, all but finitely many positive integers $n$ satisfying the congruence $a((n-1)!+1) \equiv 0 \pmod{n}$ are prime. – Pete L. Clark Apr 22 '13 at 20:06
• It appears to me in the last stage of the proof for the following characterisation of the prime triplets of form n, n+2, n+6: $4320(4((n-1)!+1)+n) + 361n(n+2) \equiv 0 \pmod{n(n+2)(n+6)}$ Or, if you prefer, it's given in the question - it's the only problem there, otherwise I could safely deduce that $n$ is prime if congruence holds and not, if otherwise. – jureslak Apr 22 '13 at 20:06
• Yes, that is indeed more general version of my question. – jureslak Apr 22 '13 at 20:07

## 3 Answers

Yours is special case $\rm\ A = 24\$ in the following generalization.

Theorem $\rm\,\ \ N\mid A\,(1\!+\!(N\!-\!1)!)\iff N\mid A\ \ or\ \ N\:$ is prime.

Proof $\,\ (\Rightarrow)\$ $\rm\:d := gcd(N,A).\,$ By Euclid, $\rm\:d=1\:\Rightarrow\:N\mid(1\!+\!(N\!-\!1)!)\:\Rightarrow\:N\,$ prime by Wilson.
Else $\rm\:d>1\:$ and $\rm\: N = n d,\ A = a d,\:$ for $\rm\:n,a\in \Bbb N.\:$ Cancelling $\rm\:d\:$ yields $\rm\: n\mid \color{#c00}a\,(1\! +\! (\color{#0a0}{nd\!-\!1)!\,}).\$
Note $\rm\:d>1\:\Rightarrow\: n\mid\color{#0a0}{(n d\!-\!1)!\,},\$ so $\rm\ n\mid \color{#c00}a,\$ so $\rm\: n d\mid a d,\:$ i.e. $\rm\:N\mid A.\:$ $\ (\Leftarrow)\$ is clear, by Wilson.

Remark $\ \$ The above is the special case $\rm\ f(N)\, =\, 1+(N\!-\!1)!\$ of the following

Theorem $\ \$ If $\rm\,\ f\, :\, \Bbb N\to \Bbb N\:$ satisfies $\rm\ d>1\:\Rightarrow\:\color{#c00}{gcd(n,f(nd))= 1}\$ for all $\rm\:n,d\in\Bbb N,\$ then

$$\rm N\mid A\,f(N)\ \iff\ N\mid A\ \ or\ \ N\mid f(N)\qquad\qquad$$

Proof $\ \$ Let $\rm\ d = (N,A),\,\ N = nd,\,\ A = ad.\$ Canceling the factor $\rm\:d\:$ from $\rm\ N,A\$ yields

if $\rm\:\ d> 1\$ then $\rm\ N\mid A\,f(N)\iff \color{#c00}n\mid a\,\color{#c00}{f(nd)\stackrel{Euclid}{\iff}} n\mid a\:\iff nd\mid ad\iff N\mid A.$

If $\rm\ d = 1\$ then $\rm\ N\mid A\,f(N) \stackrel{Euclid}{\iff} N\mid f(N),\$ by $\rm\ (N,A) = d = 1.$ 

• +1: this is a typically clean solution. I admit though that my answer was intentionally suboptimal in an attempt to leave something for the OP to do. – Pete L. Clark Apr 23 '13 at 2:57

The proposed congruence $24((n-1)! + 1) \equiv 0 \pmod{n}$ does not hold for all positive integers $n$: the first two counterexamples are $n = 9$ and $n = 10$.

In fact:

$\bullet$ If $2^4 \mid n$, then $24((n-1)!+1)$ is not divisible by $16$, so the congruence fails.

$\bullet$ For any odd prime $p$, if $p^2 \mid n$ then $24((n-1)!+1) \equiv p \pmod{p^2}$, so the congruence fails.

$\bullet$ If $n$ is of the form $ap$ for a prime $p \geq 5$ and $a \geq 2$, then $24((n-1)!+1)$ is not divisible by $p$, so the congruence fails.

Can you finish it off from here?

Here's how my sister solved it (Not a valid proof though)

$N$ be any composite number. Such that $N$'s factorization of primes is $p_1p_2 \dots p_k$

$\{p_1, \dots p_k \} \subset \{1,2, \dots n-1 \}$, therefore $N | (N-1)!$ and therefore $(N-1)!$ can't be $k (\mod N)$, where $k \neq 0$. The case of $N$ being composite is thus dismissed.