Is 100! + 1 a Prime Number
==========================
Here's one I've found on Quora, but let ChatGPT solve it there.
100! is such a big number that the answer to the
question is "probably no".
If it appears as an exam, it is probebly the second part if a
question, and the first is:
Prove Wilson's theorem.
Wilson's theorem states that.
For any natural number n>1:
n is a prime number iff and only if (n-1)!≡-1 mod n
Both directions can be proven easily:
First direction:
Suppose that n is a prime numbers. Then
each number m in 1,2,...,n-1 has a reciprocal k in
1,2,...,n-1 such that
mk!≡1 mod n
because n is a prime number. You can use Fermat's little
theorem to find the reciprocal.
Now, up to two numbers in 1,2,...n-1 are their own reciprocals:
1 and n-1. The proof is that if
A,B are in 1,2...n-1 and n divides A²-B²
Then
n | (A - B)(A + B)
and because n is a prime number n divides either A-B or A+B
In other words
A = B or (n-A)=B
in particular, when A² ≡ B² ≡ 1 mod n
For n=2, there is nothing to prove. Otherwise, each of the numbers
2,3,...,n-2 can be paired with its reciprocal, thus
(n - 2)! ≡ 1 mod n ⇒ (n - 1)!=(n - 1)(n - 2)! ≡ -1 mod n
Second direction:
Suppose (n - 1)! ≡-1 mod n, but n is composite. Then n has a divisor
d which is other from 1 and n. Thus,
n is in 2,3,...,n-1. Thus,
d | (n - 1)!
But
(n - 1)! ≡ -1 mod n
means that there exists an integer k such that:
(n - 1)! = kn -1 ⇒ (n - 1)! + 1 = kn
and d divides n, thus
d | (n - 1)! + 1 (1)
d also divides (n - 1)!
and with (1):
d | 1 = d = 1
which contradicts our hypothesis that n is composite.
Thus, n is a prime number, and Wi;son's theorem is proven!
