for a prime p of the form 4k3 prove that either p121 mod p o

for a prime p of the form 4k+3 prove that either ((p-1)/2)!1 (mod p) or ((p-1)/2)!-1 (mod p) hence ((p-1)/2)!satisfies the quadratic congruence x^21 (mod p)

Solution

(2k+2) * (2k+3) * ... * (4k+1) * (4k+2) = (p - (2k+1)) * (p - 2k) * ... * (p - 2) * (p - 1).

This second product can be simplified mod p:

(p-(2k+1)) * (p-2k) *...* (p-2) * (p-1) -(2k+1) * -2k * ... * -2 * -1 = (-1)^{2k+1} * [(p-1)/2]!.

Of course, (-1)^{2k+1} is -1, so we can conclude that

(2k+2) * (2k+3) * ... * (4k+1) * (4k+2) -[(p-1)/2]!

Therefore,

1 * 2 * ... * (2k+1) * (2k+2) * ... * (4k+2) [(p-1)/2]! * -[(p-1)/2]! = - ( [(p-1)/2]! )^2.

However, Wilson\'s theorem tells us that the left hand side is -1 (mod p). (I\'m not familiar with Burton, but most texts on elementary number theory include a proof of Wilson\'s theorem. If not, you should try to prove it yourself. It\'s not too hard -- think about inverses. If you\'re really stuck, the first proof in the Wikipedia article is a fairly standard, easy proof.) Therefore, we have now proven that

( [(p-1)/2]! )^2 1 (mod p).

It follows immediately that [(p-1)/2]! +/- 1 (mod p).