% =====================================================================================
% MATH 3800: Theory of Numbers -- Homework #1
% Vanderbilt University, Fall 2026
% =====================================================================================

\documentclass[11pt]{article}

\usepackage[margin=1in]{geometry}
\usepackage{amsmath, amssymb, amsfonts, amsthm, mathtools}
\usepackage{xcolor}
\usepackage{graphicx}
\usepackage{enumitem}
\setlist[enumerate]{label=(\alph*), itemsep=0pt, topsep=0pt, labelindent=*}

\usepackage{fancyhdr}
\pagestyle{fancy}
\lhead{\name}
\chead{\class}
\rhead{Homework \assignmentNumber}
\renewcommand{\headrulewidth}{0.4pt}

% ------------------------------- Theorem-like environments -------------------------
\newtheorem{theorem}{Theorem}
\newtheorem*{proposition}{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
%\newtheorem{problem}[theorem]{Problem}
\newtheorem{remark}[theorem]{Remark}
\renewcommand*{\proofname}{{\color{blue}Solution}}

\newenvironment{problem}[2]{\par\medskip\noindent\textbf{\S{#1} \#{#2}.}}{\par\medskip}

% ------------------------------- Number sets ----------------------------------------
\newcommand*{\NN}{\mathbb{N}}
\newcommand*{\ZZ}{\mathbb{Z}}
\newcommand*{\QQ}{\mathbb{Q}}
\newcommand*{\RR}{\mathbb{R}}
\newcommand*{\CC}{\mathbb{C}}
\newcommand*{\FF}{\mathbb{F}}
\newcommand*{\Zmod}[1]{\mathbb{Z}/#1\mathbb{Z}}
\newcommand*{\Zstar}[1]{(\mathbb{Z}/#1\mathbb{Z})^{\times}}

% ------------------------------- Number-theoretic operators -------------------------
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\sgn}{sgn}
\newcommand*{\divides}{\mid}
\newcommand*{\ndivides}{\nmid}
\newcommand*{\legendre}[2]{\left(\dfrac{#1}{#2}\right)}   % Legendre/Jacobi symbol

% ------------------------------- General-purpose notation ---------------------------
\newcommand*{\card}{\#}
\newcommand*{\abs}[1]{{\lvert #1 \rvert}}
\newcommand*{\ang}[1]{{\langle #1 \rangle}}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}
\DeclarePairedDelimiterX\set[1]\lbrace\rbrace{\def\given{\;\delimsize\vert\;}#1}
\newcommand*{\given}{\mid}
\makeatletter
\newcommand*{\defeq}{\mathrel{\rlap{\raisebox{0.3ex}{$\m@th\cdot$}}\raisebox{-0.3ex}{$\m@th\cdot$}}=}
\makeatother
\newcommand*{\maps}{\nobreak\mskip2mu\mathpunct{}\nonscript
  \mkern-\thinmuskip{:}\mskip6muplus1mu\relax}

\newcommand*{\note}[1]{\textcolor{red}{\textbf{#1}}}

\setlength{\parindent}{0pt}
\setlength{\parskip}{1.25ex}

% ===================================================================================
% ================================== Title Info =====================================
% ===================================================================================

\newcommand*{\name}{YOUR NAME}
\newcommand*{\class}{Math 3800: Theory of Numbers}
\newcommand*{\assignmentNumber}{\#1}
\newcommand*{\dueDate}{September 3, 2026}

\title{\class{}\\ Homework \assignmentNumber}
\author{\name}
\date{Due \dueDate}

% ===================================================================================
% ==================================== Body =========================================
% ===================================================================================

\begin{document}

\maketitle

\begin{itemize}
\item These problems rely on material from our upcoming lecture on Tuesday.  Because this problem set has such a quick turnaround, I have tried to limit it to something that I think is doable in 1 to 3 hours.
\item While the problems are more or less taken from Strayer, small changes have been made here and there---please keep that in mind if you refer back to the text!  I have included some hints at the bottom of the second page, but I encourage you to refer to them only if you become well and truly stuck on a problem, or to check your work.
\item Feel free to use the accompanying {\sc .tex} file as a homework template for this assignment.  (There is a proof environment commented out below each problem statement.)
\item Remember, every computation or claim should be sufficiently justified for full credit, and if you work with anyone else, please write their name(s) next to the problem.
\end{itemize}

\begin{problem}{1.1}{3}
  Find the unique quotient $q$ and remainder $r$ guaranteed by the division algorithm for each dividend $a$ and divisor $b$ below:
  \begin{enumerate}
    \item $a = 47$, $b = 6$
    \item $a = 281$, $b = 13$
    \item $a = 343$, $b = 49$
    \item $a = -105$, $b = 10$
    \item $a = -469$, $b = 31$
    \item $a = -500$, $b = 28$
  \end{enumerate}
\end{problem}
% \begin{proof}
%   (I collaborated with COLLABORATOR NAMES.)  SOLUTION
% \end{proof}

\begin{problem}{1.1}{4}
  If $a, b \in \ZZ$, find a necessary and sufficient condition that $a \divides b$ and $b \divides a$.
\end{problem}
% \begin{proof}
%   (I collaborated with COLLABORATOR NAMES.)  SOLUTION
% \end{proof}

\begin{problem}{1.1}{8}
  Let $a,n \in \ZZ_{>0}$.  Prove that $a \divides (a+1)^n - 1$.
\end{problem}
% \begin{proof}
%   (I collaborated with COLLABORATOR NAMES.)  SOLUTION
% \end{proof}

\begin{problem}{1.1}{10}  Let $n \in \ZZ$.
  \begin{enumerate}
    \item Prove that $3 \divides n^3 - n$.
    \item Prove that $5 \divides n^5 - n$.
    \item Is it true that $4 \divides n^4 - n$? Provide a proof or counterexample.
  \end{enumerate}
\end{problem}
% \begin{proof}
%   (I collaborated with COLLABORATOR NAMES.)  SOLUTION
% \end{proof}

\textit{The following excersise formalizes the calculation that we did at the end of the first class, where we reduced the Diophantine equation $x^{4} - 117x + 31 = 0$ ``modulo $2$'' (meaning that we forgot all information about the supposed integral solution $x$ and the coefficients of the polynomial except whether they were even or odd).}

\begin{problem}{1.1}{11}  Recall that $n \in \ZZ$ is called \textit{even} if $2 \divides n$, and \textit{odd} otherwise.
  \begin{enumerate}
    \item Prove that $n$ is even if and only if $n = 2m$ for some $m \in \ZZ$.
    \item Prove that $n$ is odd if and only if $n = 2m + 1$ for some  $m \in \ZZ$.
    \item Prove that the sum and product of two even integers are both even.
    \item Prove that the sum of two odd integers is even and that their product is odd.
    \item Prove that the sum of an even integer and an odd integer is odd and that their product is even.
  \end{enumerate}
\end{problem}
% \begin{proof}
%   (I collaborated with COLLABORATOR NAMES.)  SOLUTION
% \end{proof}

\begin{problem}{1.1}{12}
  Prove that the square of any odd integer is expressible in the form $8n + 1$ with $n \in \ZZ$.
\end{problem}
% \begin{proof}
%   (I collaborated with COLLABORATOR NAMES.)  SOLUTION
% \end{proof}

\vfill

\tiny
\textbf{Hints:}\vspace{-10pt}
\begin{itemize}[itemsep=-3pt]
\item \#3(a): $q = 7, r = 5$, (c): $q = 7, r = 0$, (e): $q = -16, r = 27$
\item \#4: $a = \pm b$
\item \#8: Use the binomial theorem to expand $(a + 1)^{n}$, or prove it by induction on $n$.
\item \#10(a): Use induction.
\item \#12: Use \#11(b).
\end{itemize}

\end{document}
