\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}

\begin{document}
\headers{Math545}{Homework 2}{Due Thurs, Sept 23, 2021}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\newcommand{\compicon}%
{%
	\begin{tikzpicture}[scale=0.15]%
		\draw[double] (0,0) rectangle (1,1) ;
		\begin{scope}[yshift=-5pt]
			\draw (-0.5, -0.5) rectangle (1.5, 0) ;
		\end{scope}
	\end{tikzpicture}
}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve the following problems; challenge problems are optional for extra credit.  See the course syllabus and the Homework Webpage on the course website for general directions and guidelines.

\begin{enumerate}

\item {}[NT 2-3.1] Find the general solution (if solutions exist) of each of the following linear Diophantine equations:
\begin{enumerate}
	\item $15x + 51y = 41$
	\item $23x + 29y = 25$
	\item $121x - 88y = 572$
\end{enumerate}

\item {} Let $a_1,\ldots,a_n,c$ be integer constants and let $x_1,\ldots,x_n$ be integer variables.  Give a simple condition that characterizes when the Diophantine equation $a_1x_1 + \cdots + a_nx_n = c$ has integral solutions.  Prove your characterization is correct.

\item {} Binomial Coefficients and Parity.
\begin{enumerate}
	\item {} [NT 3-1.3] Using the definition of $\binom{n}{r}$, show combinatorially that $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$.  (To show an identity combinatorially, find an appropriate set $A$ and show that both sides of the identity count the elements in $A$.)
	\item {} Prove that if $n$ is even and $r$ is odd, then $\binom{n}{r}$ is even.
\end{enumerate}

\item {} Prove that $n^5$ and $n$ have the same last digit.

\item {} Prove that if $a$ and $b$ are positive integers, then it is not possible for both $a+b^2$ and $a^2 + b$ to be square numbers (i.e. of the form $k^2$ for some integer $k$).  Hint: after $a^2$, what is the next largest square?

\item {} Prove that if $p$ is an odd prime, then there are infinitely many integers $n$ such that $p\mid n2^n + 1$.

\item {} Prove that if $n$ is an integer and $n\ge 2$, then $n^4 + 4^n$ is not prime.

\item {} \textbf{[Challenge]} Fermat's ``medium'' theorem?
\begin{enumerate}
	\item Let $p$ and $q$ be distinct primes.  Count the number of cyclic lists of length $pq$ with entries in a set of size $n$.  (For example, for $p = 2$, $q = 3$, and $n=2$, we are counting cyclic lists of length $6$ with entries in, say, $\{\textrm{red},\textrm{blue}\}$; there are $14$ of these.)
	\item Use part (a) to show that if $p$ and $q$ are distinct primes and $n$ is a positive integer, then $pq$ divides $n^{pq} - n^p - n^q + n$.
\end{enumerate}

\end{enumerate}
\end{document}
