2
$\begingroup$

Suppose that $n>1$ satisfies $(n-1)! \equiv -1 \pmod n$. Show that $n$ is a prime. (Hint: Antithesis)

My own trying: $n=3$: $(3-1)!+1= 3 \cdot 1$ => $3|2!+1$. $n=5$: $(5-1)!+1=25 = 5 \cdot 5$ => $5|4!+1$. $n=7$: $(7-1)!+1=3 = 720+1 = 7 \cdot 103$ => $7|6!+1$. So at least it holds for $n=3, 5$ and $7$. But how to prove it?

  • 0
    As DJC says it is called Wilson's theorem and the converse of your problem follows from the fact that $\mathbb{Z}_n$ is$a$field when $n$ is prime. Pair off all elements of $\mathbb{Z}_n$ except $1$ and $-1$ into inverse pairs, that is, $a$ is paired with $a^{-1}$. Since the only solutions of $x^2=1$ in a field are $1$ and $-1$, $(n-1)!\pmod{n}$ is the product of all these pairs (which equals $1$) then $1$ and $-1$. Therefore, if$n$is prime, $(n-1)!=-1\pmod{n}$.2011-10-04

2 Answers 2

3

We will show that if $(n-1)! \equiv -1 \pmod{n}$, and $n>1$, then $n$ is prime.

Let $a$ be any (positive) divisor of $n$ which is not equal to $n$. Then $a \le n-1$. So $a$ is one of the numbers which get multiplied together to form $(n-1)!$. It follows that $a$ divides $(n-1)!$.

Suppose now $(n-1)! \equiv -1\pmod{n}$. Then, by the definition of congruence modulo $n$, $n$ divides $(n-1)!+1$. But since $a$ divides $n$, the fact that $n$ divides $(n-1)!+1$ implies that $a$ divides $(n-1)!+1$.

But $a$ divides $(n-1)!$. Since $a$ divides both $(n-1)!+1$ and $(n-1)!$, it follows that $a$ divides the difference between these two numbers. But this difference is $1$. So $a$ divides $1$, and therefore $a=1$.

We have shown that if $a$ is any (positive) divisor of $n$ such that $a \ne n$, then $a$ must be equal to $1$. Since $n>1$, this forces $n$ to be prime, by the definition of prime. (The primes are precisely the numbers $n>1$ whose only positive divisors are $n$ and $1$. We have shown that if our congruence holds, and $a$ is a positive divisor of $n$ such that $a \ne n$, then $a=1$.)

  • 0
    That is more or less what I wrote just above, I had adding the sentence .... (together with n>1 not prime).2011-09-19
1

If $n=ab$ is composite, what can you say about $a$ and $b$? Relate that to $(n-1)!$.

Here is the full answer: If $n=ab$ is a non-trivial factorization, then $a and $b, and so $a\le n-1$ and $b\le n-1$. But then both $a$ and $b$ appear in $(n-1)!$ and so $(n-1)!\equiv 0 \pmod{n}$.

  • 0
    The argument does not work for $n=4$ but then it's obvious that $(4-1)! \equiv 2 \pmod 4$. See http://en.wikipedia.org/wiki/Wilson's_theorem#A_simple_generalization2011-09-27