\documentclass[11pt]{article} \usepackage{amsmath,amssymb,amsthm} \usepackage{hyperref} \hypersetup{colorlinks=true,urlcolor=blue,citecolor=blue,linkcolor=blue} \usepackage{courier} \usepackage{tikz} \usetikzlibrary{calc,matrix,arrows,decorations.markings} \usepackage{array} \usepackage{color} \usepackage{enumerate} \usepackage{nicefrac} \usepackage{listings} \lstset{ basicstyle=\small\ttfamily, keywordstyle=\color{blue}, language=python, xleftmargin=16pt, } \textwidth=5.8in \textheight=9in \topmargin=-0.5in \headheight=0in \headsep=.5in \hoffset -.4in \pagestyle{empty} % growing list of useful macros, use these where appropriate and add to this list as needed \newcommand{\kbar}{\bar{k}} \newcommand{\Fp}{\mathbb{F}_p} \newcommand{\Fpbar}{\overline{\mathbb{F}}_p} \newcommand{\Fq}{\mathbb{F}_q} \newcommand{\Fqbar}{\overline{\mathbb{F}}_q} \newcommand{\Fqm}{\mathbb{F}_{q^m}} \newcommand{\Fqn}{\mathbb{F}_{q^n}} \newcommand{\F}{\mathbb{F}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Qbar}{\overline{\Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \renewcommand{\H}{\mathbb{H}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Zhat}{\widehat\Z} \newcommand{\Zbar}{\overline\Z} \newcommand{\Kbar}{\overline K} \newcommand{\NN}{\mathbb{N}} \newcommand{\Aut}{{\rm Aut}} \newcommand{\Gal}{{\rm Gal}} \newcommand{\SL}{{\rm SL}} \newcommand{\GL}{{\rm GL}} \newcommand{\PGL}{{\rm PGL}} \newcommand{\dy}{\,dy} \newcommand{\dx}{\,dx} \newcommand{\tr}{\operatorname{tr}} \newcommand{\kron}[2]{\bigl(\frac{#1}{#2}\bigr)} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\ceil}[1]{\lceil{#1}\frac{1}eil} \newcommand{\Exp}{{\rm E}} \renewcommand{\O}{\mathcal{O}} \newcommand{\OK}{\O_K} \newcommand{\T}{{\rm T}} \newcommand{\N}{{\rm N}} \renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\Li}{\operatorname{Li}} \newcommand{\ord}{\operatorname{ord}} \newcommand{\cl}{\operatorname{cl}} \newcommand{\cond}{\operatorname{cond}} \newcommand{\disc}{\operatorname{disc}} \newcommand{\p}{\mathfrak{p}} \newcommand{\q}{\mathfrak{q}} \newcommand{\m}{{\mathfrak m}} \renewcommand{\c}{{\mathfrak c}} \renewcommand{\a}{{\mathfrak a}} \newcommand{\Frob}{{\rm Frob}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tor}{{\rm tors}} \newcommand{\I}{\mathcal{I}} \newcommand{\D}{\mathcal{D}} \newcommand{\id}{\operatorname{id}} \newcommand{\A}{\mathcal A} \renewcommand{\P}{\mathcal P} \newtheorem*{theorem}{Theorem} \theoremstyle{definition} \newtheorem*{definition}{Definition} \newtheorem*{remark}{Remark} \begin{document} \setlength{\unitlength}{1in} \begin{center} \large \textbf{18.785 Number Theory\hspace{228pt}Fall~2018}\\\vspace{4pt} \textbf{Problem Set \#9\hspace{220pt}Due: 11/16/2018} \normalsize \begin{picture}(5.8,.1) \put(0,0) {\line(1,0){5.8}} \end{picture} \end{center} \subsection*{Description} These problems are related to the material covered in Lectures 16--18. Your solutions are to be written up in latex (you can use the latex source for the problem set as a template) and submitted as a pdf-file with a filename of the form \texttt{SurnamePset9.pdf} via e-mail to \texttt{drew@math.mit.edu} by {\bf noon} on the date due. Collaboration is permitted/encouraged, but you must identify your collaborators, and any references you consulted. If there are none, write ``\textbf{Sources consulted:\ none}" at the top of your problem set. The first person to spot each non-trivial typo/error in any of the problem sets or lecture notes will receive 1-5 points of extra credit. \bigskip \noindent \textbf{Instructions:} First do the warm up problems, then pick two of problems 1--5 to solve and write up your answers in latex, then complete the survey problem 6. \subsection*{Problem 0.} These are warm up problems that do not need to be turned in. \begin{enumerate} \setlength\itemsep{0pt} \item[(a)] Show $\pi(x):=\sum_{p\le x}1=\int_{2^-}^\infty (1/\log t)d\vartheta(t)$ and $\vartheta(x):=\sum_{p\le x}\log p = \int_{2^-}^\infty \log t d\pi(t)$, and use these identities to prove \[ \vartheta(x)=\pi(x)\log x - \int_2^x\frac{\pi(t)}{t}dt,\qquad \pi(x)=\frac{\vartheta(x)}{\log x}+\int_2^x \frac{\vartheta(t)}{\log^2 t}dt, \] which provides an alternative proof that $\pi(x)\sim x/\log x$ if and only if $\vartheta(x)\sim x$. \item[(b)] Let $\chi$ be a primitive Dirichlet character of conductor $m>1$. Verify the identity \[ \sum_{n\ge 1}\chi(n)x^n=\frac{1}{1-x^m}\sum_{n=1}^{m-1}\chi(n)x^n \] and use this to prove that $\Gamma(s)L(s,\chi)$ extends to a holomorphic function on $\C$. Conclude that $L(s,\chi)$ has an analytic continuation to $\C$. \end{enumerate} \subsection*{Problem 1. Mertens' Theorems (49 points)} In his 1874 paper Mertens' proved three asymptotic bounds on sums over primes; he necessarily did not rely on the Prime Number Theorem, which wasn't proved until 1896. Define the constants \[ \alpha :=-\sum_{n\ge 2}\frac{\mu(n)}{n}\log\zeta(n)\approx 0.315718,\qquad \gamma:=\lim_{x\to\infty} \left(\sum_{1\le n\le x}\frac{1}{n}-\log x\right)\approx 0.577216, \] where $\mu(n)$ is the M\"obius function from Problem Set 8: \[ \mu(n):=\begin{cases} (-1)^{\#\{p|n\}}&\text{if $n\ge 1$ is square free};\\ 0&\text{otherwise}. \end{cases} \] Let $\Lambda(n)$ denote the \emph{von Mangoldt function}: \[ \Lambda(n):=\begin{cases} \log p&\text{if $n>1$ is a power of a prime $p$};\\ 0&\text{otherwise}. \end{cases} \] \begin{theorem}[Mertens] As $x\to \infty$ we have the following asymptotic bounds: \begin{enumerate} \item[{\rm (1)}] $\displaystyle{\sum_{p\le x}\tfrac{\log p}{p} = \log x + O(1)}$; \item[{\rm (2)}] $\displaystyle{\sum_{p\le x}\tfrac{1}{p} = \log\log x + \gamma - \alpha + O\Bigl(\tfrac{1}{\log x}\Bigr)}$; \item[{\rm (3)}] $\displaystyle{\sum_{p\le x}\log\Bigl(1\!-\!\tfrac{1}{p}\Bigr) = -\!\log\log x - \gamma + O\Bigl(\tfrac{1}{\log x}\Bigr)}$. \end{enumerate} \end{theorem} \begin{remark} Mertens showed that the $O(1)$ term in (1) has absolute value bounded by $2$, but we will not need this. One often sees (3) written as $\prod_{p\le x} (1-\tfrac{1}{p}) = \tfrac{e^{-\gamma}+o(1)}{\log x}$ but our version is a slightly sharper statement that reflects what Mertens actually proved. \end{remark} \begin{enumerate}[{\bf(a)}] \item Show that $\log(n)=\sum_{d|n}\Lambda(d)$ and derive the bounds \[ \sum_{n\le x}\log n = \sum_{d\le x}\Lambda(d)\lfloor \tfrac{x}{d}\rfloor\qquad\text{and}\qquad \sum_{d\le x}\frac{\Lambda(d)}{d}=\log x + O(1). \] Use these bounds and Stirling's formula to prove (1). \item Let $A(x)$ denote the sum in (1). Prove that \[ \sum_{p\le x}\frac{1}{p} = \frac{A(x)}{\log x}+\int_2^x\frac{A(t)}{t(\log t)^2} dt = \log\log x + c + O\Bigl(\tfrac{1}{\log x}\Bigr), \] for some constant $c$. \item Prove that for $\Re(s)>1$ we have \[ \frac{1}{s}\log \zeta(s) = \int_2^\infty\frac{\pi(t)\, dt}{t(t^s-1)}, \] and for $t>1$ we have \[ \frac{1}{t^2(t-1)} = -\sum_{n\ge 2}\frac{\mu(n)}{t(t^n-1)}. \] \item Prove that \[ \sum_{n\ge 2}\sum_p\frac{1}{np^n} = \int_2^\infty\frac{\pi(t)\,dt}{t^2(t-1)} = \alpha \] and deduce that (2) and (3) are equivalent. \end{enumerate} \begin{remark} Parts (b) and (d) imply that (3) holds if we replace $\gamma$ with $c'=c+\alpha$. Problem~2 gives a proof that in fact $c'=\gamma$, so both (2) and (3) hold. \end{remark} \begin{enumerate}[{\bf(a)}] \setcounter{enumi}{4} \item Let $P(x):=\sum_{p\le x}\frac{1}{p}=\log\log x +c + \epsilon(x)$ with $\epsilon(x)=O\bigl(\tfrac{1}{\log x}\bigr)$ as in (b). Show that \[ \pi(x) = \int_{2^-}^x t\, dP(t) = O\Bigl(\frac{x}{\log x}\Bigr), \] and that with the error bound $\epsilon(x)=o\bigl(\tfrac{1}{\log x}\bigr)$ one obtains $\pi(x)\sim\tfrac{x}{\log x}$. Thus a slightly stronger version of Mertens' 2nd theorem implies the prime number theorem. \end{enumerate} \subsection*{Problem 2. Mellin transforms of Dirichlet series (49 points)} Associated to any arithmetic function $f\colon \Z_{n\ge 1}\to \C$ is a Dirichlet series \[ D_f(s):=\sum_{n\ge 1} f(n)n^{-s}, \] which we may view a function of the complex variable $s$ on any region $\Re(s)>\sigma\ge 0$ in which the series converges; conversely, the coefficients of a Dirichlet series define an arithmetic function. We also have the \emph{summatory function} $S_f\colon\R\to \C$ associated to $f$, defined by \[ S_f(x):=\sum_{1\le n\le x}f(n), \] and the \emph{logarithmic summatory function} $L_f\colon \R\to \C$ defined by \[ L_f(x):=\sum_{1\le n\le x}\frac{f(n)}{n}. \] \begin{enumerate}[{\bf(a)}] \item Show that $D_f(s)$ is related to $S_f(x)$ and $L_f(x)$ via the formulas \begin{align*} D_f(s)&=s\int_1^\infty S_f(t)t^{-s-1}\,dt\qquad\quad\ \, (\Re(s) >\max(0,\sigma)),\\ D_f(s)&=(s-1)\int_1^\infty L_f(t)t^{-s}\,dt\qquad (\Re(s) > \max(1,\sigma)). \end{align*} \item By applying (a) to $f=1$, show that \[ \zeta(s) = \frac{s}{s-1}-s\int_1^\infty \{t\}{t^{-s-1}}\,dt\qquad (\Re(s)>0), \] where $\{t\}:=t-\lfloor t\rfloor$. Use this to show that as $s\to 1$ we have \[ \zeta(s) = \frac{1}{s-1}+\gamma + O(|s-1|). \] \item Let \[ P(x):=-\sum_{p\le x}\log(1-\tfrac{1}{p}) \] be the negation of the sum in Mertens' 3rd theorem (see Problem 1), and let $\kappa(n)$ be the arithmetic function defined by $\kappa(n)=1/k$ when $n=p^k$ is a prime power $(k\ge 1)$ and $\kappa(n)=0$ otherwise (as in Problem 4.e on Problem set 8). Show that \[ P(x)=L_\kappa(x)+O\left(\tfrac{1}{\log x}\right). \] \item Show that $\log\zeta(s) = D_\kappa(s)$ and use (b) to prove that \[ D_\kappa(s)=\log\frac{1}{s-1}+O(s-1) \] as $s\to 1^+$ (along the real line). \end{enumerate} \noindent From parts (b) and (d) of Problem 1 we know that \begin{equation}\label{eq:P} P(x)=\log\log x + C + O\left(\tfrac{1}{\log x}\right) \end{equation} for some constant $C$ which, according to Mertens' 3rd theorem, is equal to Euler's constant $\gamma$. You are now in a position to prove this. \begin{enumerate}[{\bf(a)}] \setcounter{enumi}{4} \item From (c) and \eqref{eq:P} we know that $L_\kappa = \log\log x + C+ O\left(\tfrac{1}{\log x}\right)$. By plugging this into to the formula relating $D_\kappa$ and $L_\kappa$ from (a), show that we have \[ D_\kappa(s)=\log\frac{1}{s-1} + C + \int_0^\infty (\log t)e^{-t}dt + O\left((s-1)\log\tfrac{1}{s-1}\right) \] as $s\to 1^+$. \item By combining (d) and (e) and letting $s\to 1^+$ show that \[ C=-\int_0^\infty (\log t)e^{-t}dt. \] Then show that the integral is equal to $\Gamma'(1)$, and prove that $\Gamma'(1)=-\gamma$ (you can do this either by using (b) and the functional equation for $\zeta(s)$, or by evaluating the \emph{digamma function} $\Psi(s):=\Gamma'(s)/\Gamma(s)$ at $1$). \end{enumerate} \subsection*{Problem 3. Dirichlet density (49 points)} Let $K$ be a global field and let $\mathcal P$ be the set of nonzero prime ideals of $\O_K$. The \emph{natural density} of a set $S\subseteq \mathcal P$ is defined by \[ \delta(S):=\lim_{x\to\infty} \frac{\#\{\p\in S:\N(\p)\le x\}}{\#\{\p \in \mathcal P:\N(\p)\le x\}} \] (whenever this limit exists), and its \emph{Dirichlet density} is defined by \[ d(S):=\lim_{s\to1^+} \frac{\sum_{\p\in S}\N(\p)^{-s}}{\sum_{\p\in \mathcal P}\N(\p)^{-s}} \] (whenever this limit exists). Here $\N(\p):=[\O_K:\p]$ is the absolute norm. \begin{enumerate}[{\bf(a)}] \item Show that the denominator in $d(S)$ is finite for real $s > 1$ and that \[ \sum_{\p\in \P}\N(\p)^{-s} \sim \log\left(\frac{1}{s-1}\right) \] as $s\to 1^+$. \item Let $S$ and $T$ be subsets of $\mathcal P$ with Dirichlet densities. Show that $S\subseteq T$ implies $d(S)\le d(T)$, and that $d(S)=0$ when $S$ is finite. Conclude that if $S$ and $T$ differ by a finite set (that is, the sets $S-T$ and $T-S$ are both finite), then $d(S)=d(T)$. \item Suppose $S,T\subset\P$ have finite intersection. Show that if any two of the set $S$, $T$, and $S\cup T$ have a Dirichlet density then so does the third and $d(S\cup T)=d(S)+d(T)$. \item Suppose $K$ is a number field or a finite separable extension of $\Fp(t)$ and define $\P_1:=\{\p \in \P:\N(\p)\text{ is prime}\}$. Show that $d(\P_1)=1$ and therefore $\P_1$ is infinite. \item With $K$ and $\mathcal P_1$ as in (d) show for any $S\subseteq \P$, if $S$ has a Dirichlet density then $d(S)=d(S\cap \P_1)$ and otherwise $S\cap \P_1$ does not have a Dirichlet density. Compute the density of the set of primes of $\Q(i)$ that lie above a prime $p\equiv 3\bmod 4$. \item Show that if $S\subseteq \P$ has a natural density then it has Dirichlet density $d(S)=\delta(S)$. \item Show that for $K=\Fq(t)$ the set of primes $(f)$ where $f$ is an irreducible polynomial of even degree has Dirichlet density $1/2$ but no natural density. \item Show that for $K=\Q$ the set $S_1$ of primes whose leading decimal digit is equal to $1$ has no natural density. \item Let $A$ be the set of positive integers with leading decimal digit equal to $1$. Show that \[ \lim_{s\to 1^+} \frac{\sum_{n\in A} n^{-s}}{\frac{1}{s-1}} = \lim_{s\to 1^+}\frac{\sum_{n\in A}n^{-s}}{\sum_{n\ge 1} n^{-s}} = \log_{10}(2). \] \item Adapt your argument in (i) to show that $d(S_1)=\log_{10}(2)$. \end{enumerate} \subsection*{Problem 4. PNT for arithmetic progressions (49 points)} For each integer $m>1$ and integer $a$ coprime to $m$ we define the prime counting function \[ \pi(x;m,a):=\sum_{\substack{p\le x\\ p\equiv a\bmod m}} 1. \] In this problem you will adapt the proof of the PNT in \cite{zagier} (which is essentially the same as given in class except for the argument to show that $\zeta(s)$ has no zeros on $\Re(s)=1$) to prove the PNT for arithmetic progressions, which states that \[ \pi(x;m,a)\sim\frac{\pi(x)}{\phi(m)}\sim \frac{1}{\phi(m)}\frac{x}{\log x}, \] where $\phi(m):=\#(\Z/m\Z)^\times$ is the Euler function. We first set some notation. Let $\chi$ denote a primitive Dirichlet character of conductor dividing $m$ and define \[ L(s,\chi):=\sum_{n\ge 1}\chi(n)n^{-s},\qquad \theta_{m,a}(x):=\phi(m)\hspace{-12pt}\sum_{\substack{p\le x\\p\equiv a\bmod m}}\hspace{-12pt}\log p, \] \[ \phi(s,\chi):=\sum_p\chi(p)p^{-s}\log p,\quad\Phi_m(s):=\sum_\chi\phi(s,\chi),\quad \Phi_{m,a}(s):=\sum_\chi \overline{\chi(a)}\phi(s,\chi). \] Finally, let $K=\Q(\zeta_m)$ be the $m$th cyclotomic field with Dedekind zeta function $\zeta_K(s)$. \begin{enumerate}[{\bf(a)}] \item Show that $\theta_{m,a}(x)=O(x)$. \item Show that for each $\chi$ we have \[ -\frac{L'(s,\chi)}{L(s,\chi)}=\phi(s,\chi)+h(s,\chi), \] for some $h(s,\chi)$ holomorphic on $\Re(s)>1/2$, and conclude that \[ -\frac{\zeta_K'(s)}{\zeta_K(s)} = \Phi_m(s)+h(s), \] for some $h(s)$ holomorphic on $\Re(s)>1/2$. \item Show that $\zeta_K(s)$ is real-valued on real values of $s$ and proceed as in step (IV) of \cite{zagier} to show that $\zeta_K(s)$, and therefore each $L(s,\chi)$, has no zeros on $\Re(s)=1$. \item Show that $\Phi_{m,a}(s)-\frac{1}{s-1}$ is holomorphic on $\Re(s)\ge 1$ and prove that \[ \Phi_{m,a}(s)=s\int_0^\infty e^{-st}\theta_{m,a}(e^t)dt \] \item Show that the Laplace transform of $f(t)=\theta_{m,a}(e^t)e^{-t}-1$ extends to a holomorphic function on $\Re(s)\ge 0$ and use this to prove $\theta_{m,a}(x)\sim x$. \item Show that (e) implies \[ \pi(x,m)\sim \frac{\pi(x)}{\phi(m)}\sim \frac{1}{\phi(m)}\frac{x}{\log x}. \] \end{enumerate} \subsection*{Problem 5. Factoring with the analytic class number formula (49 points)} Let $K$ be an imaginary quadratic field with discriminant $D<0$. Recall from Problem 2 of Problem Set 7 that each ideal class in $\cl\O_K$ can be uniquely represented by a reduced binary quadratic form \[ f(x,y)=ax^2+bxy+cy^2 \] which we compactly denote $f=(a,b,c)$. The coefficients $a,b,c$ are integers with no common factor with $a>0$ and $b^2-4ac=D$ (so $f$ is integral, primitive, positive definite, and of discriminant $D$), and if \[ -a 1$ be an integer coprime to $6$, not a perfect power. Show that if $n\equiv 3\bmod 4$ then for the discriminant $D=-n$ every ideal class in $\cl \O$ of order 2 (of which there is at least one) is represented by an ambiguous form whose coefficients yield a nontrivial factorization $uv$ of $n$; show that if $n\equiv 1\bmod 4$ then for the discriminant $D=-3n$ a similar statement holds for all but one ideal class of order 2 (of which there are at least 3). \item Show that for $\O=\O_K$ we have $\#\cl\O=\frac{1}{\pi}\sqrt{|D|}L(1,\chi)$, where $\chi$ is the Dirichlet character defined by the Kronecker symbol $\left(\tfrac{D}{\cdot}\right)$ (so $\chi(n)=\left(\tfrac{D}{n}\right)$). This also holds for $\O\subsetneq\O_K$, but you are not required to prove this. \end{enumerate} The Extended Riemann Hypothesis (ERH) states that the zeros of every Dirichlet $L$-function $L(s,\chi)$ all lie on the critical line $\Re(s)=\frac{1}{2}$. Under this assumption there is an effectively computable constant $c_1$ such that if we compute the partial product \[ L^*:=\prod_{p\le n^{1/5}}\left(1-\chi(p)p^{-1}\right)^{-1} \] of $L(1,\chi)$ and put $h^*:=\frac{1}{\pi}\sqrt{|D|}L^*$ (with $D<-4$), then for $h=\#\cl\O$ we have \[ |h-h^*|1$ does one of the following: (1) outputs a nontrivial factorization of $n$, (2) proves that $n$ is prime, (3) proves that the ERH is false. Assume arithmetic operations on integers (and rational numbers) can be performed in quasi-linear time (i.e. $O(b^{1+o(1)})$ where~$b$ is the number of bits in the operands). You do not need to spell out all the details of the algorithm, a summary of each step is sufficient (note: you will need to address the case where $n$ is a perfect power separately). If you are not familiar with the baby-steps giant-steps algorithm, see section 8.8 in these \href{http://ocw.mit.edu/courses/mathematics/18-783-elliptic-curves-spring-2017/lecture-notes/MIT18_783S17_lec8.pdf}{notes} for a quick overview). \end{enumerate} \subsection*{Problem 6. Survey (2 points)} Complete the following survey by rating each problem you attempted on a scale of 1 to~10 according to how interesting you found it (1 = ``mind-numbing," 10 = ``mind-blowing"), and how difficult you found it (1 = ``trivial," 10 = ``brutal"). Also estimate the amount of time you spent on each problem to the nearest half hour. \begin{center} \begin{tabular}{l|r|r|r|} & Interest & Difficulty & Time Spent\\\hline Problem 1 & & & \\\hline Problem 2 & & & \\\hline Problem 3 & & & \\\hline Problem 4 & & & \\\hline Problem 5 & & & \\\hline \end{tabular} \end{center} \noindent Please rate each of the following lectures that you attended, according to the quality of the material (1=``useless", 10=``fascinating"), the quality of the presentation (1=``epic fail", 10=``perfection"), the pace (1=``way too slow", 10=``way too fast", 5=``just right") and the novelty of the material to you (1=``old hat", 10=``all new"). \begin{center} \begin{tabular}{l|l|r|r|r|r|r} Date & Lecture Topic & Material & Presentation & Pace & Novelty\\\hline 11/6 & Dirichlet L-functions & & & & \\\hline 11/12 & Analytic class number formula & & & & \\\hline \end{tabular} \end{center} \noindent Please feel free to record any additional comments you have on the problem sets and the lectures, in particular, ways in which they might be improved. \begin{thebibliography}{99} \bibitem{bach} E. Bach, \href{http://www.ams.org/journals/mcom/1990-55-191/S0025-5718-1990-1023756-8/S0025-5718-1990-1023756-8.pdf}{\textit{Explicit bounds for primality testing and related problems}}, Math. Comp. \textbf{55} (1990), 335--380. \bibitem{LMO} J.C. Lagarias, H.L. Montgomery, and A.M. Odlyzko, \href{http://link.springer.com/article/10.1007%2FBF01390234}{\textit{A bound for the least prime ideal in the Chebotarev Density Theorem}}, Invent. Math. \textbf{54} (1979), 271--296. \bibitem{schoof} R. Schoof, \href{http://cr.yp.to/bib/1982/schoof.html}{\textit{Quadratic fields and factorization}}, in "Computational Methods in Number Theory", MC-Tracts 154/155, 1982, 235--286. \bibitem{zagier} D. Zagier, \href{http://people.mpim-bonn.mpg.de/zagier/files/doi/10.2307/2975232/fulltext.pdf}{\textit{Newman's short proof of the prime number theorem}}, Amer. Math. Monthly \textbf{104} (1997), 705--708. \end{thebibliography} \end{document}