- #36

- 19,141

- 24,450

fishturtle1 said:Lemma: If ##p## is prime then the only solutions to ##x^2 = 1 \text{ (mod p)}## are ##x = -1, 1##.

Proof: Suppose ##x^2 = 1 \text{ (mod p)}##. Then ##p \vert (x^2 - 1)## i.e. ##p \vert (x-1)(x+1)##. Since ##p## is prime, we have ##p \vert x + 1## or ##p \vert x - 1##. This implies ##x = -1 \text{ (mod p)}## or ##x = 1 \text{ (mod p)}##. And we see ##1## and ##-1## really are solutions to ##x^2 = 1 \text{ (mod p)}##. []

Proof of problem in OP: ##(\Longleftarrow): ## Suppose ##p## is prime. Then

$$(p-1)! = (p-1)(p-2)\cdot \dots \cdot 2 \cdot 1 = -1\cdot (p-2) \cdot \dots \cdot 2 \cdot 1 = -1 \cdot 1 = -1 \text{ (mod p)}$$

The second equality is from ##p-1 = -1 \text{ (mod p)}## and the third inequality is using the fact the only squares are ##-1## and ##1##, therefore every other element is canceled by its inverse.

You should have mentioned the ##p=2## case, but ok, we can assume that ##p## is odd.

I don't get it. ##(p-k)\cdot k=-k^2\in \{\pm 1\} \;(p)##. Why isn't it ##-1## an odd number of times?

It would have been better to use ##n## instead of ##p##. If you start with ##p## then your readers associate a prime whilst this is what you want to have at the end, and not at the beginning.fishturtle1 said:##(\Longrightarrow): ## Suppose ##(p-1)! = -1 \text{ (mod p)}##. We will show ##p## must be prime. Suppose ##1 \le d < p## is a divisor of ##p##. Then ##d## is also a divisor of ##(p-1)!##. We can rewrite the congruence as

$$-1 = (p-1)! + p\cdot k$$ for some integer ##k##.

Correct.fishturtle1 said:Since ##d## divides the right hand side, it must divide the left hand side. Hence, ##d \vert -1## which implies ##d = 1##. This implies the only divisors of ##p## are ##1## and ##p##. We may conclude ##p## is prime. []

fishturtle1 said:For the next part, we claim the first two primes that satisfy ##(p-1)! = -1 \text{ (mod p^2)}## are ##p = 5## and ##p = 13##. Observe,

\begin{align}

(2-1)! &= 1 \text{ (mod 4)} \\

(3-1)! &= 2 \text{ (mod 9)} \\

(5-1)! &= 24 = -1 \text{ (mod 25)} \\

(7-1)! &= 720 = 34 \text{ (mod 49)} \\

(11-1)! &= 3628800 = 10 \text{ (mod 121)} \\

(13-1)! &= 479,001,600 = 168 = -1 \text{ (mod 169)}

\end{align}

Right. Up to now, there is only one more so-called Wilson prime known, namely ##563.## It is unknown whether there are more than that. If, then they are greater than ##20,000,000,000,000.## The conjecture is, that there are infinitely many Wilson primes.