\documentclass{article}
\usepackage{amssymb}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
%\theoremstyle{Remark}
%\newtheorem{remark}
\renewcommand{\today}{}
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\Lap}[1]{\mathcal{L}\left\{#1\right\}}


\addtolength{\topmargin}{-.875in}
\addtolength{\textheight}{1.75in}

\newcommand{\solution}[1]{
\begin{quote}\color{red}Solution:\quad 
\color{black} #1
\end{quote}
}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Zplus}{\Z^+}

\begin{document}
\title{Math 228: Homework 2}
\author{Mary Radcliffe}
\date{due 16 Sept 2016}
\maketitle

Complete the following problems. Fully justify each response. You need only turn in those problems marked with a (*).

\begin{enumerate}

\item (*) Select 38 positive integers, all less than 1000. Prove that there must be two of them whose difference is less than 27.

\item (*) Prove the identity \[{n\choose 0}-{n\choose 1}+{n\choose 2}- \cdots +(-1)^n{n\choose n} = 0.\]

\item You are given a set $S$ of $n+1$ distinct integers from $[2n]$. 
\begin{enumerate}
\item Prove that there must exist $a, b\in S$ having no common divisor.
\item Is it true that there must exist $a, b\in S$ having $a=2b$? If so, prove it. If not, provide a counterexample.
\item Is it true that there must exist $a, b\in S$ having $a=kb$ for some integer $k$? If so, prove it. If not, provide a counterexample.
\end{enumerate}

\item (*) Prove that $\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$.

\item How many ways can we permute the characters $\{1, 1, 2, 2, 3, 4, 5, 5\}$ so that no two identical digits are in consecutive positions?

\item (*) Given a positive integer $n$, we define $\phi(n)$ to be the number of integers in $[n]$ that share no divisors with $n$. For example, if $n=6$, $\phi(n)=2$, since the integers in $\{1, 2, 3, 4, 5, 6\}$ that share no divisor with $6$ are $1$ and $5$. This is called Euler's totient function, or, more colloquially, Euler's $\phi$-function.
\begin{enumerate}
\item Calculate $\phi(n)$ for $1\leq n\leq 10$.
\item Prove that if $p$ is prime and $k\geq 1$, then $\phi(p^k) = p^k\left(1-\frac{1}{p}\right)$.
\item Use Inclusion-Exclusion to prove that if $p$ and $q$ are both prime, with $p\neq q$, and $k,j\geq 1$, then $\phi(p^kq^j)=p^kq^j\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)$.
\item Generalize part (c) to come up with a formula for $\phi(n)$ for any $n$. Prove that your formula is correct.
\end{enumerate}

\end{enumerate}

\end{document}