Final Exam

Due Date: Tuesday, May 24 at 11:59 pm

Rules: This is a final exam, not a homework assignment. You must solve the problems entirely on your own, and you should not discuss the problems with any other students in the class. You should feel free to read internet web pages that might be helpful (e.g. Wikipedia articles and online documentation for Mathematica and SageMath), but you should not solicit help by posting questions to any online forums.

1. Write a function FermatFactor that implements the Fermat factoring algorithm, and use your function to factor the following 197-digit number: \[ \begin{array}{l} 15241578780673678546105778311537878076969977842813 \\ 60023657903334546946646802864964577541121338298870 \\ 24612169370291171715970174061649176407328243116361 \\ 17712292664376996559249165876846768069963079567 \end{array} \]
2. If \(p>2\) is prime and \(1 \leq k < p-1\), prove that \[ \sum_{n=1}^{p-1} n^k \,\equiv\, 0\quad(\mathrm{mod}\;p). \]
3. Let \(p\) and \(q\) be distinct primes. Prove that if \(p\) is a primitive element of \(\mathbb{Z}_q\) then the cyclotomic polynomial \(\Phi_q(x)\) is irreducible over \(\mathbb{Z}_p\).
4. Let \(p\) be a prime congruent to 3 modulo 4. Prove that \[ \prod_{j=1}^{p-1}\, \prod_{k=1}^{p-1} \bigl(j^2+k^2\bigr) \,\equiv\, 1\quad(\mathrm{mod}\;p). \]