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

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

\begin{document}
\headers{Math545}{Homework 1}{Due Tue Sep. 7, 2021}

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

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

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve the following problems.  Your solutions should be electronically typeset and all written work should be your own.

\begin{enumerate}

\item {} \emph{Sums of squares}.
\begin{enumerate}
	\item {} [NT 1-1.1] Prove that $1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$.
	\item Determine the set $A$ of positive integers $n$ such that $n$ divides the sum $1^2+2^2+\cdots + n^2$.  Note: your answer should give a simple description of $A$ and a proof that $n$ divides $1^2+\cdots + n^2$ if and only if $n\in A$.
\end{enumerate}

\item {} Prove that for each non-negative integer $n$, we have that $169$ divides $3^{3n+3} - 26n - 27$.

\item {} \emph{Divisibility and exponents}.
\begin{enumerate} 
	\item Prove that if $a$ and $n$ are integers with $a\ge 3$ and $n\ge 2$, then $a^n-1$ is not prime.
	\item Prove that if $2^n - 1$ is prime, then $n$ is prime.
\end{enumerate}

\item {} Give the base $6$ representation for 42,201.

\item {} Let $d = \gcd(63119, 38227)$.  Find $d$ and obtain integers $p$ and $q$ such that $d = 63119p + 38227q$.  Show your work.


\item {} \textbf{[Challenge]} Let $A_n = \{(x,y)\st \mbox{$1\le x\le n$, $1\le y\le n$, and $\gcd(x,y) = 1$}\}$.  Note that $A_n$ contains all points $(x,y)$ in the $(n\times n)$-grid with corners $(1,1)$ and $(n,n)$ such that the line segment joining $(0,0)$ and $(x,y)$ contains no other integer lattice points.  The first few such sets are as follows:  
\begin{align*}
A_1 &= \{(1,1)\}\\
A_2 &= \{(1,1), (2,1), (1,2)\}\\
A_3 &= \{(1,1), (1,2), (1,3), (2,3), (2,1), (3,1), (3,2)\}
\end{align*}
Let $f(n) = |A_n|$.  Note that $f(1) = 1$, $f(2) = 3$, $f(3) = 7$, and $f(4) = 11$.  Prove that there is a positive constant $C$ such that $f(n) \ge Cn^2$.

\end{enumerate}
\end{document}
