Paper 4, Section II, D

Numbers and Sets | Part IA, 2012

State Fermat's Theorem and Wilson's Theorem.

For which prime numbers pp does the equation x21(modp)x^{2} \equiv-1(\bmod p) have a solution? Justify your answer.

For a prime number pp, and an integer xx that is not a multiple of pp, the order of xx (modp)(\bmod p) is the least positive integer dd such that xd1(modp)x^{d} \equiv 1(\bmod p). Show that if xx has order dd and also xk1(modp)x^{k} \equiv 1(\bmod p) then dd must divide kk.

For a positive integer nn, let Fn=22n+1F_{n}=2^{2^{n}}+1. If pp is a prime factor of FnF_{n}, determine the order of 2(modp)2(\bmod p). Hence show that the FnF_{n} are pairwise coprime.

Show that if pp is a prime of the form 4k+34 k+3 then pp cannot be a factor of any FnF_{n}. Give, with justification, a prime pp of the form 4k+14 k+1 such that pp is not a factor of any FnF_{n}.

Typos? Please submit corrections to this page on GitHub.