\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}

\begin{document}
\headers{Math545}{Homework 5}{Due Nov 11, 2021}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}
%

\newcommand{\compicon}%
{%
	\begin{tikzpicture}[scale=0.15]%
		\draw[double] (0,0) rectangle (1,1) ;
		\begin{scope}[yshift=-5pt]
			\draw (-0.5, -0.5) rectangle (1.5, 0) ;
		\end{scope}
	\end{tikzpicture}
}

\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZeroFunc}{\mathbb{O}}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve the following problems.  See the course syllabus and the Homework Webpage on the course website for general directions and guidelines.

\begin{enumerate}

\item {}\emph{Primitive Roots I.}
\begin{enumerate}
	\item Find all primitive roots modulo 5, modulo 9, modulo 11, modulo 13, and modulo 15.

	\item Let $a$ and $m$ be positive, relatively prime integers.  Let $S$ be the set of primes dividing $\phi(m)$.  Prove that if $a^{\phi(m)/p} \not\equiv 1 \pmod{m}$ for each $p\in S$, then $a$ is a primitive root of $m$.
\end{enumerate}

\item {}\emph{Primitive Roots II.} 
\begin{enumerate}
	\item Let $m_1$ and $m_2$ be relatively prime integers, and suppose that $p$ and $q$ are odd primes such that $p\mid m_1$ and $q\mid m_2$.  Let $m=m_1m_2$.  Prove that if $a$ and $m$ are relatively prime, then $a^{\phi(m)/2} \equiv 1\pmod{m}$.
	
	\item Show that if $m$ has two distinct odd prime divisors, then $m$ has no primitive roots.
\end{enumerate}

\item {}[NT 8-1.4] Modify the proof of Theorem 8--1 to prove that there exist infinitely many primes congruent to $5\pmod{6}$.

\item {}[NT 8-1.16] Let $n = 132!$.  How many zeros are at the end of the base $2$ representation of $n$?  How many zeros are at the end of the base $10$ representation of $n$?

\item {} \emph{Upper bound on $\sum_{p\le n} \frac{1}{p}$.}  Let $P[a,b)$ be the set of all primes $p$ such that $a\le p < b$.  Let $H_n = \sum_{k=1}^n \frac{1}{k}$ and recall $\ln n \le H_n \le 1 + \ln n$.
\begin{enumerate}
	\item Show that $\sum_{p\in P[1,2^t)} \frac{1}{p} \le 16H_t$.  (Hint: use Chebychev's theorem to bound $\sum_{p\in P[2^{k-1},2^k)} \frac{1}{p}$.)
	\item Prove that $\sum_{p\le n} \frac{1}{p} \le C\ln\ln n$ for some constant $C$.
\end{enumerate}

\item {} \emph{Lower bound on $\sum_{p\le n} \frac{1}{p}$.}  Let $z_n = \sum_{p\le n} \frac{1}{p}$ and let $H_n = \sum_{k=1}^n \frac{1}{k}$.
\begin{enumerate}
	\item Use an integral comparison to show that $\sum_{k\ge t} \frac{1}{k^2} \le \frac{1}{t-1}$.  Conclude that $\sum_p \frac{1}{p^2} \le \frac{3}{4}$.
	\item Prove that $e^{z_n} \ge \prod_{p\le n} (1+\frac{1}{p})$.
	\item Prove that $\prod_{p\le n} (1+\frac{1}{p}) \ge (1-\sum_{p\le n} \frac{1}{p^2}) H_n$.  Conclude that $z_n \ge (1-o(1)) \ln \ln n$.
\end{enumerate}

\item {} \textbf{[Challenge]} Let $f(x)$ be a non-constant polynomial with integer coefficients.  Prove that for infinitely many primes $p$, there exists an integer $n$ such that $p\mid f(n)$.

\end{enumerate}
\end{document}
