\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{\F}{\mathbb{F}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Qbar}{\overline{\mathbb{Q}}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Aut}{{\rm Aut}}
\newcommand{\Gal}{{\rm Gal}}
\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}}
\newcommand{\re}{\operatorname{re}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\ord}{{\rm ord}}
\newcommand{\cl}{{\rm cl}}
\newcommand{\disc}{{\rm disc}}
\newcommand{\p}{\mathfrak{p}}
\newcommand{\m}{{\mathfrak m}}
\renewcommand{\a}{\mathfrak{a}}
\renewcommand{\b}{\mathfrak{b}}
\newcommand{\Frob}{{\rm Frob}}

\newtheorem*{theorem}{Theorem}

\begin{document}
\setlength{\unitlength}{1in}
\begin{center}
\large
\textbf{18.785 Number Theory\hspace{228pt}Fall~2019}\\\vspace{4pt}
\textbf{Problem Set \#1\hspace{220pt}Due: 09/11/2019}
\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 material covered in Lectures 1--2.
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 named \texttt{SurnamePset1.pdf} (replace ``\texttt{Surname}'' with your surname) via e-mail to \texttt{drew@math.mit.edu} before \textbf{noon} on the date due (late problem sets will not be graded, but early submissions are welcome).
Collaboration is permitted/encouraged, but you must identify your collaborators and any references you consult that are not listed in the syllabus; if this does not apply to you, write \textbf{Sources consulted:\ none} at the top of your problem set.

The first person to spot each typo/error in any of the problem sets or lecture notes will receive 1--5 points of extra credit, depending on the severity of the error (please do report any errors you spot, even trivial typos -- future students will thank you).
\medskip

\noindent
\textbf{Instructions:} First solve the warm up problems; these do not need to be formally written up or turned in.  Then pick any three of Problems 1--4 to solve and write up your answers in latex.  Finally, complete Problem 5, which is a short survey whose answers will help shape future problem sets and lectures. 

\subsection*{Problem 0. Warm up (0 points)}
These warm up exercises do not need to be written up or turned in, they are provided simply to help you check your understanding.
\begin{enumerate}
\item[\textbf{(a)}] Prove the nonarchimedean ``triangle equality": if $|\cdot|$ is a nonarchimedean absolute value on a field $k$ and $|x|\ne |y|$ then $|x+y|=\max(|x|,|y|)$.
\item[\textbf{(b)}] Let $K$ be a global field (a finite extension of $\Q$ or $\Fp(t)$).  Show that if $K$ has characteristic zero then there is only one way to embed $\Q$ in $K$ but when $K$ has positive characteristic there are infinitely many different ways of embedding $\Fp(t)$ in $K$.  In particular, show that the field $K:=\mathrm{Frac}( \Fp[x,y]/(y^2-x^3-x-1))$ can be viewed as both a degree 2 extension of $\Fq(x)$ and a degree 3 extension of $\Fq(y)$, but that the isomorphism $\Fq(y)\simeq \Fq(x)$ does not commute with the inclusions.
\item[\textbf{(c)}] Write down a monic polynomial $f\in \Z[x]$ with $\sqrt{2}+\sqrt{3}$ as a root.

\end{enumerate}

\subsection*{Problem 1. Absolute values on $\Q$ (32 points)}
\begin{enumerate}
\item[\textbf{(a)}] Prove that an absolute value $|\cdot|$ on a field $k$ is nonarchimedean if and only if $|n|\le 1$ for all $n\in \Z_{>0}$ (here $n:=1+\cdots+1\in k$ for all fields $k$).

\item[\textbf{(b)}] Prove Ostrowski's Theorem: every nontrivial absolute value on $\Q$ is equivalent to~$|\cdot|_p$ for some prime $p\le \infty$.

\item[\textbf{(c)}] Prove the product formula for $\Q$: show that $\prod_{p\le\infty}|x|_p=1$ for all $x\in \Q^\times$.
\end{enumerate}

\subsection*{Problem 2. Absolute values on $\Fq(t)$ (32 points)}

For each prime $\pi\in\Fq[t]$ and any nonzero $f\in \Fq[t]$, let $v_\pi(f)$ be the largest integer for which $\pi^n|f$,
equivalently, the largest $n$ for which $f\in(\pi^n)$.
For each $f/g\in\Fq(t)^\times$ define
\[
v_\pi(f/g):=v_\pi(f)-v_\pi(g),
\]
and let $v_\pi(0):=\infty$; also define $\deg 0 := -\infty$ and $\deg(f/g) := \deg f -\deg g$.

\begin{enumerate}
\item[\textbf{(a)}] For each prime $\pi\in \Fq[t]$, define
$|r|_\pi = (q^{\deg\pi})^{-v_\pi(r)}$
for all $r\in \Fq(t)$.  Show that $|\cdot |_\pi$ is a nonarchimedean absolute value on $\Fq(t)$.

\item[\textbf{(b)}] Define $|r|_\infty := q^{\deg r}$,
for all $r\in\Fq(t)$.  Prove that $|\cdot|_\infty$ is a nonarchimedean absolute value on $\Fq(t)$.

\item[\textbf{(c)}] Determine the residue field of $\Fq(t)$ with respect to $|\cdot|_\pi$; the residue field is the quotient of the valuation ring $\{x\in \Fq(t):|x|_\pi \le 1\}$ by its unique maximal ideal.

\item[\textbf{(d)}] Describe the valuation ring $R:=\{x\in \Fq(t):|x|_\infty \le 1\}$ and its unique maximal ideal~$\m$.
Then determine the residue field of $\Fq(t)$ with respect to $|\cdot|_\infty$.

\item[\textbf{(e)}] Prove Ostrowski's theorem for $\Fq(t)$: every nontrivial absolute value on $\Fq(t)$ is equivalent to $|\cdot|_\infty$ or $|\cdot |_\pi$ for some prime $\pi\in \Fq[t]$.

More precisely, show that if $\Vert\cdot\Vert$ is a nontrivial absolute value on $\Fq(t)$, either $\Vert t\Vert >1$ and $\Vert\cdot\Vert\sim | \cdot |_\infty$, or $\Vert t \Vert\le 1$ and $\Vert\cdot \Vert\sim|\cdot |_\pi$ for some prime $\pi\in\Fq[t]$.
\end{enumerate}

\noindent
In view of (e), we regard $\infty$ as a ``prime" of $\Fq(t)$ and let $\pi$ range over both monic irreducible polynomials in $\Fq[t]$ and $\infty$.

\begin{enumerate}
\item[\textbf{(f)}] Prove the product formula for $\Fq(t)$: show that $\prod_{\pi}|r|_\pi = 1$ for every $r\in\Fq(t)^\times$ .
\end{enumerate}

\subsection*{Problem 3. Quadratic fields (32 points)}
Let $K=\Q(\sqrt{d})$ with $d\ne 0,1$ a squarefree integer, and let $\p$ be a nonzero prime ideal of the ring of integers $\O_K$ that does not divide $(2d)$.
\begin{enumerate}
\item[\textbf{(a)}] Give explicit generators for $\O_K$ as a $\Z$-module.
\item[\textbf{(b)}] Determine the index of $\Z[\sqrt{d}]$ in $\O_K$ as a function of $d$.
\item[\textbf{(c)}] Show that $\p$ can be written in the form $(p,\alpha)$, with $(p)=\p\cap \Z$ and $\alpha\in \O_K$.
\item[\textbf{(d)}] Show that $\O_K/\p\simeq \F_{q}$ where $q=[\O_K:\p]$ is either $p$ or $p^2$, with $\p=(p,\alpha)$.
Give an explicit criterion in terms of $p$ and $d$ for when the two cases occur.
\item[\textbf{(e)}] Determine the number of equivalence classes of archimedean absolute values of $\Q(\sqrt{d})$ as a function of $d$.
\end{enumerate}

\subsection*{Problem 4. The Euler $\phi$-function. (32 points)}
Let $A$ denote $\Z$ or $\Fp[t]$, and let $|\cdot|$ denote $|\cdot |_\infty$ (the standard archimedean absolute value on $\Q$ or the nonarchimedean absolute value of $\Fp(t)$ defined in Problem 2).  Recall that $a\perp b$ means $(a,b)=A$.  Throughout this problem, we assume $a,b\in A$ are nonzero, and understand ``$a\bmod b$'' to mean the image of $a$ under the quotient map $A\to A/(b)$.
\begin{enumerate}
\item[\textbf{(a)}] Prove that $A/(a)$ is a ring with $|a|$ elements.
\end{enumerate}
Define the Euler $\phi$-function $\phi\colon A_{\ne 0}\to \Z_{>0}$ by $\phi(a):=\#(A/(a))^\times$.
\begin{enumerate}
\item[\textbf{(b)}] Prove $\phi(ab)=\phi(a)\phi(b)$ if $a\perp b$ and $\phi(a^n)= |a|^{n-1}(|a|-1)$ for $a$ prime and $n\ge 1$.
\item[\textbf{(c)}] Prove that $\phi(a)=|a|\prod_{q|a}(1-|q|^{-1})$, where $q$ ranges over primes.
\item[\textbf{(d)}] Prove that for $a\perp b$ we have $a^{\phi(b)}\equiv 1\bmod b$.
\item[\textbf{(e)}] Prove that if $b$ is prime then
$
\prod_{0 < |a| < |b|} a \equiv \begin{cases}+1\bmod b & \text{if }A=\Z;\\-1\bmod b &\text{if  }A=\Fp[t].\end{cases}
$
\item[\textbf{(f)}] Let $a\perp b$ with $b$ prime and let $r\ge 2$ divide $|b|-1$.  Show that $a\bmod b$ is an $r$th power if and only if $a^{(|b|-1)/r}\equiv 1\bmod b$, and $\#\{c^r:c\in (A/(b^n))^\times\}=\phi(b^n)/r$.
\end{enumerate}



\subsection*{Problem 5. Survey (4 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
\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
9/4 & Absolute values, discrete valuations & & & & \\\hline 
9/9 & Localizations, Dedekind domains & & & & \\\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.

\end{document}