\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{anyfontsize}
\usepackage[super]{nth}
\usepackage{ulem}
\usepackage{multicol}
\usepackage{phaistos}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage[all,arc]{xy}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}

\homework{9: Number Theory (Basic) }{Due Tuesday, Week 5, at the start of class.}

Solve \textbf{three} of the following \textbf{six} problems.  As always, prove your claims!



\begin{enumerate}
\item[0.] Solve any un-signed-up-for problems from HW\#6!
\item (IMO, 1975.) Let $f(n)$ denote the function that sends $n$ to the sum of its decimal digits.  For example, $f(746) = 7+4+6 = 17$.  Find
\begin{align*}
f\left( f \left( f \left( 4444^{4444} \right)\right)\right).
\end{align*}
Hint: mod 9 may be useful.
\item Fix any positive integer $k$.  Consider the following sequence$ \{a_n\}_{n=1}^\infty$, defined recursively:
\begin{itemize}
\item $a_1 = 1$.
\item $a_n$ is the $n$-th positive integer that is greater than $a_{n-1}$ that is also congruent to $n$ mod $k$.
\end{itemize}
For example, if $k=2$, we would get the sequence
\begin{align*}
1, 4, 9, 16, \ldots
\end{align*}
because 
\begin{itemize}
\item 4 is the second positive integer greater than 1 that is congruent to 2 mod 2, 
\item 9 is the third positive integer greater than 4 that is congruent to 3 mod 2,
\item 16 is the fourth positive integer greater than 9 that is congruent to 4 mod 2, \ldots
\end{itemize}
For arbitrary $k$, find a closed formula for $a_n$.

\item Prove that there are unique positive integers $a,n$ such that 
\begin{align*}
a^{n+1} - (a+1)^n = 2001.
\end{align*}
(Hint: if you can just show that $a$ is unique, then $n$'s uniqueness will follow immediately.  To get that $a$ is unique: try rewriting the above expression slightly, and use that to get information about $a$!)

\item Find all functions $g: \mathbb{N} \to \mathbb{N}$ that satisfy the following property:
\begin{align*}
\forall n \in \mathbb{N}, g(n) + 2 \cdot (g(g(n))) = 3n + 5.
\end{align*}

\item (USAMO, 1979)  Find all of the non-negative integer solutions $(x_1, \ldots x_{14}) \in \mathbb{N}^{14}$ to the equation
\begin{align*}
n_1^4 + n_2^4 + n_3^4 + \ldots + n_{14}^4 = 1599.
\end{align*}

\item Prove that there are infinitely many primes of the form $4n-1$, where $n$ is an integer.
\end{enumerate}





\end{document}


