Paper 4, Section II, E

Numbers and Sets | Part IA, 2011

State Fermat's Theorem and Wilson's Theorem.

Let pp be a prime.

(a) Show that if p3(mod4)p \equiv 3(\bmod 4) then the equation x21(modp)x^{2} \equiv-1(\bmod p) has no solution.

(b) By considering (p12)\left(\frac{p-1}{2}\right) !, or otherwise, show that if p1(mod4)p \equiv 1(\bmod 4) then the equation x21(modp)x^{2} \equiv-1(\bmod p) does have a solution.

(c) Show that if p2(mod3)p \equiv 2(\bmod 3) then the equation x31(modp)x^{3} \equiv-1(\bmod p) has no solution other than 1(modp)-1(\bmod p).

(d) Using the fact that 1423(mod199)14^{2} \equiv-3(\bmod 199), find a solution of x31(mod199)x^{3} \equiv-1(\bmod 199) that is not 1(mod199)-1(\bmod 199).

[Hint: how are the complex numbers 3\sqrt{-3} and 13\sqrt[3]{-1} related?]

Typos? Please submit corrections to this page on GitHub.