\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage{amsfonts}
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{tikz}
\usepackage{ytableau}
\usepackage{skak}
\usepackage{rotating}
\usepackage[framemethod=tikz]{mdframed}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Thursday, November 18, 2021 02:02:48}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{ComputeDefs=
%$f\left(  n\right)  =\gcd\left(  15n+4,\ 12n+5\right)  $
%}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\newcounter{exer}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fns}{\begin{footnotesize}}{\end{footnotesize}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\are}{\ar@{-}}
\newcommand{\arebi}[1][]{\ar@{<-}@/_/[#1] \ar@/^/[#1]}
\ihead{Math 220-002 Fall 2021 (Darij Grinberg): homework set 4}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 220-002 Fall 2021 (Darij Grinberg): homework set 4}

due date: Monday 2021-11-09 at noon on gradescope (
\url{https://www.gradescope.com/courses/313263} ).

Please solve only \textbf{4 of the 6 exercises}.
\end{center}

This homework set is mostly about divisibility and congruence.

\begin{exercise}
Let $a,b\in\mathbb{Z}$. Prove the following:

\textbf{(a)} If $a\mid b$, then $a^{k}\mid b^{k}$ for each $k\in\mathbb{N}$.

\textbf{(b)} Let $n\in\mathbb{Z}$. If $a\equiv b\operatorname{mod}n$, then
$a^{k}\equiv b^{k}\operatorname{mod}n$ for each $k\in\mathbb{N}$.
\end{exercise}

\begin{exercise}
Let $n,d,a,b\in\mathbb{Z}$, and assume that $d\neq0$ and $da\equiv
db\operatorname{mod}dn$.

\textbf{(a)} Prove that $a\equiv b\operatorname{mod}n$.

\textbf{(b)} Show by an example that $a\equiv b\operatorname{mod}dn$ is not
necessarily true (i.e., we cannot simply cancel the $d$ from $da$ and $db$
while leaving the $dn$ unchanged).
\end{exercise}

\begin{exercise}
Let $n$ be any integer. Prove the following:

\textbf{(a)} If $n$ is odd, then $8\mid n^{2}-1$.

\textbf{(b)} If $3\nmid n$, then $3\mid n^{2}-1$.

[\textbf{Hint:} In part \textbf{(a)}, write $n$ as $2k+1$. In part
\textbf{(b)}, write $n$ as $q\cdot3+r$ and consider the possible values for
$r$.]
\end{exercise}

\begin{exercise}
Prove that $\gcd\left(  15n+4,\ 12n+5\right)  =1$ for each $n\in\mathbb{Z}$.
\end{exercise}

Two primes that differ by $2$ are called \emph{twin primes}. (For instance,
$17$ and $19$ are twin primes.) An infamous open problem in number theory asks
whether there are infinitely many \textquotedblleft twin
primes\textquotedblright. A much easier variant of this question asks how many
\textquotedblleft double-twin primes\textquotedblright\ (i.e., primes $p$ such
that both $p-2$ and $p+2$ are primes, so that $p$ belongs to two twin-primes
pairs) exist. The answer is, there is exactly one:

\begin{exercise}
Let $p$ be a prime such that $p-2$ and $p+2$ are also prime. Prove that $p=5$.

[\textbf{Hint:} Consider the remainders upon division by $6$.]
\end{exercise}

The next exercise is known as the \textquotedblleft Chicken McNugget
problem\textquotedblright\footnote{Quoting AoPS:
\par
\begin{quote}
Originally, McDonald's sold its nuggets in packs of 9 and 20. Math enthusiasts
were curious to find the largest number of nuggets that could not have been
bought with these packs, thus creating the Chicken McNugget Theorem (the
answer worked out to be 151 nuggets).
\end{quote}
}

\begin{exercise}
Let $a$ and $b$ be two coprime positive integers. Let $m$ be an integer such
that $m>ab-a-b$. Prove that there exist \textbf{nonnegative} integers $x$ and
$y$ such that $m=xa+yb$.

[\textbf{Hint:} First, use Bezout's theorem to argue that there exist integers
$x^{\prime}$ and $y^{\prime}$ such that $x^{\prime}a+y^{\prime}b=1$. Hence,
obtain integers $x^{\prime\prime}$ and $y^{\prime\prime}$ such that
$x^{\prime\prime}a+y^{\prime\prime}b=m$. If these $x^{\prime\prime}$ and
$y^{\prime\prime}$ are nonnegative, then we are done. If not, we can
\textquotedblleft tweak\textquotedblright\ them by adding a multiple $sb$ of
$b$ to $x^{\prime\prime}$ and subtracting the corresponding multiple $sa$ of
$a$ from $y^{\prime\prime}$. Note that $x^{\prime\prime}+sb$ will become
nonnegative if we pick $s$ large enough, while $y^{\prime\prime}-sa$ while
become nonnegative if we pick $s$ small enough. Is the \textquotedblleft
goldilocks zone\textquotedblright\ (i.e., the set of all $s\in\mathbb{R}$ that
are large enough for $x^{\prime\prime}+sb\geq0$ yet small enough for
$y^{\prime\prime}-sa\geq0$) sufficiently large as to contain an integer?]
\end{exercise}


\end{document}