1
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ 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?? $\endgroup$ – Pete L. Clark Apr 22 '13 at 19:50
  • $\begingroup$ 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. $\endgroup$ – Pete L. Clark Apr 22 '13 at 20:06
  • $\begingroup$ 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. $\endgroup$ – jureslak Apr 22 '13 at 20:06
  • $\begingroup$ Yes, that is indeed more general version of my question. $\endgroup$ – jureslak Apr 22 '13 at 20:07
2
$\begingroup$

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.$ $ $

$\endgroup$
  • $\begingroup$ +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. $\endgroup$ – Pete L. Clark Apr 23 '13 at 2:57
2
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.