\newif\ifOCW %\OCWtrue \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} \ifOCW\usepackage{soul}\let\oldhref\href\renewcommand{\href}[2]{\oldhref{#1}{\ul{#2}}}\fi \ifOCW\newcommand{\due}[1]{\hfill\phantom{Due: #1}}\else\newcommand{\due}[1]{\hfill{Due: #1}}\fi \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{plain} % 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~2025}\\\vspace{4pt} \textbf{Problem Set \#1\due{09/12/2025}}\\\vspace{-6pt} \normalsize \begin{picture}(5.8,.1) \put(0,0) {\line(1,0){5.8}} \end{picture} \end{center} \noindent These problems are related to Lectures 1--2. Your solutions should be written up in latex (please do not submit handwritten solutions) and submitted as a PDF \ifOCW\else to \href{https://www.gradescope.com/courses/1110057}{Gradescope}\fi\ before midnight on the date due. You can use the latex source for this problem set as a template, and are welcome to use the latex environment of your choice (I personally use \href{https://www.overleaf.com/}{Overleaf} and \href{https://www.xm1math.net/texmaker/}{Texmaker}, but there are \href{https://en.wikipedia.org/wiki/Comparison_of_TeX_editors}{many other options}). \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. Collaboration is permitted/encouraged, but you must identify your collaborators (including any LLMs you consulted) and any references you consulted outside the course \ifOCW syllabus \else\href{https://math.mit.edu/classes/18.785/2025/syllabus.html}{syllabus}\fi. Include this information after the \textbf{Collaborators/Sources} prompt at the end of the problem set (if there are none, you should enter ``none'', do not leave it blank). Each student is expected to write their own solutions; it is fine to discuss problems with others, but your writing must be your own. \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}\Bigl( \Fp[x,y]/(y^2-x^3-x-1)\Bigr)$ can be viewed as both a degree 2 extension of $\Fp(x)$ and a degree 3 extension of $\Fp(y)$, but that the isomorphism $\Fp(x)\simeq \Fp(y)$ 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}$ (note $n:=1+\cdots+1\in k$). (\textbf{Hint}: use the binomial theorem.) \item[\textbf{(b)}] Prove Ostrowski's Theorem: every nontrivial absolute value on $\Q$ is equivalent to~$|\cdot|_p$ for some prime $p\le \infty$. (\textbf{Hint}: if $|b|>1$ for some $b\in \Z_{>1}$, let $|b|=b^\alpha$ and show there is a $C>0$ such that $|n|\le Cn^\alpha$ for all $n\in \Z_{\ge 1}$, and by applying this to powers deduce $|n|\le n^\alpha$ for all $n\in \Z_{\ge 1}$. Now prove $|n| \ge n^\alpha$ for all $n\in \Z_{\ge 1}$ by fixing $n$, choosing $s$ so $b^s\le n0$ that does not depend on $n$, and apply to powers again.) \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 $n$ 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 contain the integer $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 time you spent on each problem to the nearest half hour. \begin{center} \begin{tabular}{l|r|r|r|} & Interest & Difficulty & Time\\\hline Problem 1 & & & \\\hline Problem 2 & & & \\\hline Problem 3 & & & \\\hline Problem 4 & & & \\\hline \end{tabular} \end{center} \noindent Please feel free to record any additional comments you have on the problem sets or the lectures, in particular, ways in which you think they could be improved. \medskip \noindent \textbf{Collaborators/Sources}: \end{document}