\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=Wednesday, March 08, 2023 22:16:19}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%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 221 Winter 2023 (Darij Grinberg): homework set 4}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\begin{center}
\textbf{Math 221 Winter 2023 (Darij Grinberg): homework set 4}

due date: Sunday 2023-02-21 at 11:59PM on gradescope (
\url{https://www.gradescope.com/courses/487830} ).

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

\begin{noncompile}
NOTE TO SELF: This problem set was generally \textbf{too hard} for this course.
\end{noncompile}

We begin with some exercises on greatest common divisors:

\begin{exercise}
Recall the \texttt{bezout\_pair} function defined in \S 3.4.4 (Lecture 9).
This function outputs a Bezout pair for any given pair $\left(  a,b\right)  $
with $a\in\mathbb{Z}$ and $b\in\mathbb{N}$. Tweak it so that it works for
arbitrary $b\in\mathbb{Z}$ (not just for $b\in\mathbb{N}$). \medskip

[Feel free to use your favorite programming language instead of Python, but do
not change the logic in the case when $b\geq0$.]
\end{exercise}

\begin{noncompile}
NOTE TO SELF: The above exercise is \textbf{not particularly well-suited} for
this course. Students use $a//b$ or $a\%b$ when $b$ is negative, and some
struggle with syntax, even when everyone is studying CS. Also, hard to tell if
some answers are original or copypasted.
\end{noncompile}

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

\begin{exercise}
Let $a\in\mathbb{Z}$ and $b\in\mathbb{Z}$ be nonzero integers. Let $\left(
x,y\right)  $ be some Bezout pair for $\left(  a,b\right)  $.

Let $g=\gcd\left(  a,b\right)  $. Let $a^{\prime}=a/g$ and $b^{\prime}=b/g$.

Prove that each Bezout pair for $\left(  a,b\right)  $ can be written in the
form $\left(  x+kb^{\prime},\ y-ka^{\prime}\right)  $ for some $k\in
\mathbb{Z}$.

[\textbf{Hint:} It is probably easiest to first prove this in the case when
$a$ and $b$ are coprime. In this case, $g=1$ and $a^{\prime}=a$ and
$b^{\prime}=b$.]
\end{exercise}

\begin{noncompile}
NOTE TO SELF: The above exercise is \textbf{fairly hard}. Maybe give a clearer
hint next time?
\end{noncompile}

\bigskip

Now, some exercises on primes:

\begin{exercise}
Let $\left(  a_{0},a_{1},a_{2},\ldots\right)  $ be a sequence of integers
defined recursively by%
\[
a_{n}=1+a_{0}a_{1}\cdots a_{n-1}\ \ \ \ \ \ \ \ \ \ \text{for all }n\geq0.
\]
(This sequence has been studied in Exercise 5 on midterm 1.) \medskip

\textbf{(a)} Prove that $\gcd\left(  a_{n},a_{m}\right)  =1$ for any two
distinct integers $n,m\in\mathbb{N}$. \medskip

For each $n\in\mathbb{N}$, let $p_{n}$ be a prime that divides $a_{n}$. (Such
a prime exists, since $a_{n}=1+\underbrace{a_{0}a_{1}\cdots a_{n-1}}_{\geq
1}\geq1+1>1$. Of course, there will often be several choices. In this case,
just choose one.) \medskip

\textbf{(b)} Prove that the primes $p_{0},p_{1},p_{2},\ldots$ are distinct.
\end{exercise}

\begin{remark}
This shows that there are infinitely many primes.
\end{remark}

\begin{noncompile}
NOTE TO SELF: The above exercise is among the hardest in this course, despite
its short solution. Only pose \textbf{(a)}.
\end{noncompile}

\bigskip

Two primes that differ by $2$ are called \textbf{twin primes}. (For instance,
$17$ and $19$ are twin primes.) To this day, no one knows whether there are
infinitely many twin primes (this is the infamous \textquotedblleft%
\href{https://en.wikipedia.org/wiki/Twin_prime}{twin prime conjecture}%
\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}

And finally, here is a generalization of the $p\mid\dbinom{p}{k}$ divisibility
(Theorem 3.6.3) from Lecture 10:

\begin{exercise}
Let $p$ be a prime. Let $m\in\mathbb{N}$, and let $k\in\left\{  1,2,\ldots
,p^{m}-1\right\}  $. Prove that $p\mid\dbinom{p^{m}}{k}$.
\end{exercise}


\end{document}