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?

  • 2
    Hint: Suppose to the contrary that $n=ab$ where $a>1$, $b>1$. Then $a \le n-1$, so $a$ divides $(n-1)!$.2011-09-19
  • 3
    @alv By the way, I think you should consider accepting some answers to your previous questions.2011-09-19
  • 0
    @André: How do you get from $a>1, b>1$ that $a \leq n-1$ and that a divides $(n-1)!$?2011-09-19
  • 0
    But once check my proof2011-09-19
  • 2
    Your calculations show that $(p-1)! \equiv -1 \pmod{p}$ for the first few primes $p$. Even if you went on to prove that $(p-1)!\equiv -1 \pmod{p}$ for **all** primes $p$, this would still not prove that **if** $n>1$ and $(n-1)! \equiv -1\pmod{n}$, **then** $n$ is prime. The question you were asked is whether the congruence can hold at a composite $n$, not whether it holds at primes. (Actually, the congruence holds at all primes, and fails at all non-primes $>1$. The proof that the congruence holds at all primes is quite a bit harder than the proof it fails at all composite numbers.)2011-09-19
  • 0
    This goes by the name "Wilson's Theorem" (http://en.wikipedia.org/wiki/Wilson's_theorem) by the way.2011-09-19
  • 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
    But did you used antithesis in your proof to show that then $(n-1)! \notequiv -1( \pmod n)$2011-09-19
  • 0
    @alvoutila: If you want to use that wording, change the answer slightly. Write "Suppose to the contrary that $(n-1)!\equiv -1 \pmod{n}$." Then proceed **exactly** like in the answer above to show that $n$ is prime. That gets you your desired contradiction. I avoided a proof by contradiction in the hope that that would make the logic clearer.2011-09-19
  • 0
    But did you used antithesis in your proof to show that then $(n−1)! \not \equiv −1(\pmod n)$? Would you please show some hint on how to prove this that way by antithesis?2011-09-19
  • 0
    I described, in comment above, exactly how to turn the answer into an explicit proof by contradiction (antithesis). It involves adding the sentence in quotes at the beginning, (together with $n>1$ not prime), then appending the proof I wrote, and then saying we have reached a contradiction.2011-09-19
  • 0
    But in my opinion proof by antithesis would as following: AT. suppose that n be not prime( not: suppose that $(n-1)! \equiv -1\pmod n$ )... => $(n-1)! \not \equiv -1\pmod n$. Isn't it?2011-09-19
  • 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