\documentclass{article}[11 pts] 
\begin{document}

\centerline{\bf THEORY OF NUMBERS, Math 115 B}
\centerline{\bf Homework }
\vskip 5pt

\begin{enumerate}

\item  For which positive integers $a$ is the congruence $ax^4 \equiv 2$
$mod \ 13$ solvable?

\item Let $p$ be an odd prime. Show that the congruence $x^4 \equiv -1 (mod \ p)$has a solution if and only if $p$ is of the form $8k+1$. 

\item Using the previous exercise prove that there are infinitely many primes
of the form $8k+1$. 

\item Use the index system modulo 60 to find the solutions of $11x^7 \equiv 43 (mod \ 60)$.

\item Encrypt the message DO NOT PASS GO using the ElGamal cryptosystem
with the public-key  $(p,r,b)=(2251,6,33)$. Show how the resulting ciphertext
can be decrypted using the private key a=13.

\item Find all the quadratic residues of the following integers:
a) 7, b) 8, c) 15, d) 18.

\item Find the values of the Legendre symbols $( \frac{j}{5})$ for $j=1,2,3,4,5$

\item Show that that there are infinitely many primes of the form $4k+1$.

\item What is the law of quadratic reciprocity?

\item Evaluate the Legendre symbols of $( \frac{3}{53})$ $( \frac{111}{991})$
$( \frac{31}{641})$
 
\item Show that there are infinitely many primes of the form $5k+4$.

\item Find the solution to the following quadratic congruence $x^2+5x+1 \equiv 0$ $(mod \ 7)$.

\end{enumerate}

\end{document}





