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

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

\begin{document}
\headers{Math545}{Homework 3}{Due Tue, Oct. 12, 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}
}

\newcommand{\ZZ}{\mathbb{Z}}

\makeatletter
\def\@oddfoot{}
\makeatother

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

\begin{enumerate}

\item {} Prove that $p$ is the smallest prime that divides $(p-1)! + 1$.

\item {}[NT 5-2.4] Let $k=\phi(m)$.  Prove that if $r_1,\ldots,r_k$ is a reduced residue system modulo $m$ and $m$ is odd, then $r_1 + r_2 + \cdots + r_k \equiv 0 \pmod m$.

\item {}[NT 5-3.4]
\begin{enumerate}
	\item Prove that for each $n$, there are $n$ consecutive integers, each of which is divisible by a perfect square larger than $1$.

	\item Using your proof above, explicitly find $3$ consecutive integers, each of which is divisible by a perfect square larger than $1$.  In your answer, give the integers as well as the corresponding perfect squares.
\end{enumerate}

\item {}[NT 5-4.1] Find the set of solutions to the following system of congruences:
\begin{align*}
	2x&\equiv 1 \pmod 5\\
	3x&\equiv 9 \pmod 6\\
	4x&\equiv 1 \pmod 7\\
	5x&\equiv 9 \pmod{11}
\end{align*}

\item {} Let $A = \{a^2 - b^2\st a,b\in\Z\}$.  Give a simple characterization of $A$ (with proof of correctness).

\item {} Prove that there are infinitely many integers $n$ such that $n\mid 2^n+1$.  Hint: first, find the three smallest such integers.

\item {} \textbf{[Challenge]} Prove that if $n \ge 2$, then the sum $1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}$ is not an integer.


\end{enumerate}
\end{document}
