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

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

\begin{document}
\headers{Math545}{Homework 7}{Due Tue, Dec 8, 2015}

%\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.  See the course syllabus and the Homework Webpage on the course website for general directions and guidelines.

\begin{enumerate}

\item Let $p$ be an odd prime.  Determine the number of mutually incongruent solutions to $x^2 + y^2 \equiv 0\pmod{p}$.  (A solution $(x,y)$ is congruent to $(x',y')$ if $(x,y)\equiv (x',y') \pmod{p}$.  When $p=3$, there is 1 solution $(0,0)$, and when $p=5$, there are $9$ solutions.)


\item {} Sums of three squares.
\begin{enumerate}
	\item {} [NT 11-2.9] Show that no integer of the form $4^a(8m+7)$ is the sum of three squares.  Hint: consider the congruence $x^2 + y^2 + z^2 \equiv 7\pmod{8}$.
	\item Prove or disprove: if $x$ and $y$ are representable as the sum of three squares, then so is $xy$.
	\item Prove that if $x$ is representable as the sum of three \emph{positive} squares, then so is $x^2$.
\end{enumerate}

\item Partition Exercises.
\begin{enumerate}
	\item Find the conjugate partition to $16 = 5 + 4 + 4 + 2 + 1$.  
	\item {}[NT 12-3.1] For the case $n=8$, list the corresponding pairs of partitions of $n$ in which all parts are odd and partitions of $n$ into distinct parts given by Theorem 12-3.
\end{enumerate}



\item Let $P(q)$ be the generating function for the partition numbers.  That is, $P(q) = \sum_{n\ge 0} p(n) q^n$ by definition, and $P(q) = \prod_{j\ge 1} \frac{1}{1-x^j}$ for $|q| < 1$ by Theorem 13--3.
\begin{enumerate}
	\item Let $a_k(n)$ be the number of partitions of $n$ in which each part is used less than $k$ times, and let $A_k(q)$ be the generating function $A_k(q) = \sum_{n\ge 0} a_k(n) q^n$.  Show that $A_k(q) = \frac{P(q)}{P(q^k)}$ for $|q| < 1$.

	\item Let $b_k(n)$ be the number of partitions of $n$ in which no part is divisible by $k$, and let $B_k(q)$ be the generating function $B_k(q) = \sum_{n \ge 0} b_k(n) q^n$.  Show that $B_k(q) = \frac{P(q)}{P(q^k)}$ for $|q| < 1$.
\end{enumerate}
Note: Since $A_k(q) = B_k(q)$, it follows that $a_k(n) = b_k(n)$ for all $n$.

\item \textbf{[Challenge]}  Prove that the number of partitions of $n$ into \emph{distinct} parts congruent to $1$, $2$, or $4 \pmod{7}$ equals the number of partitions of $n$ into parts congruent to $1$, $9$, or $11 \pmod{14}$.

\end{enumerate}

\end{document}
