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

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

\begin{document}
\headers{Math545}{Homework 4}{Due Thurs Oct. 28, 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}}
\newcommand{\RR}{\mathbb{R}}

\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 $M$ be the set of all positive integers $m$ such that $a^{\phi(m) + 1} \equiv a\pmod{m}$ for each integer $a$.  Give a simple characterization of $M$ and prove that your characterization is correct.


\item {}[NT 5-2.\{9,10\}] 
\begin{enumerate}
	\item Prove that if $p$ is a prime and $p \equiv 1 \pmod{4}$, then $\displaystyle \left[\left(\frac{p-1}{2}\right)!\right]^2 \equiv -1 \pmod{p}$.

	\item Use the above to find a solution for each of the following.
	\begin{enumerate}
		\item $x^2 \equiv -1 \pmod{13}$
		\item $x^2 \equiv -1 \pmod{17}$
	\end{enumerate}
\end{enumerate}

\item {} Prove that if $m$ is not a prime and $\phi(m) \mid m-1$, then $m$ has at least three distinct prime factors.

\item {} Prove that the number of ways of writing $n$ as a sum of consecutive positive integers equals $d(m)$, where $m$ is the largest odd divisor of $n$.  For example, for $n=42$ we have $m=21$ and $d(m) = d(21) = 4$.  As expected, there are $4$ ways to express $42$ as the sum of consecutive positive integers:  $42$, $13+14+15$, $9+10+11+12$, and $3+4+\cdots+9$.

\item {}[NT 6-4.2] Prove that if $f(n)$ is multiplicative and not identically zero, then 
$\displaystyle \sum_{d\mid n} \mu(d)f(d) = \prod_{p \mid n} (1-f(p))$.

\newcommand{\ZeroFunc}{\mathbb{O}}
\item {} Dirichlet product and Mobius pairs.  Let $\ZeroFunc\st \ZZ^+\to\RR$ be the identically zero function.  
\begin{enumerate}
	\item Prove that the Dirichlet product is bilinear.  That is, for all functions $f,g,h \st \ZZ^+ \to \RR$ and all constants $\alpha,\beta \in \RR$, we have $f * (\alpha g + \beta h) = \alpha (f*g) + \beta (f*h)$.
	\item Prove that if $f * g = \ZeroFunc$, then $f = \ZeroFunc$ or $g=\ZeroFunc$.
	\item Show that if both $(h_1,h_2)$ and $(h_2,h_1)$ are Mobius pairs, then $h_1 = h_2 = \ZeroFunc$.
\end{enumerate}


\item {}\textbf{[Challenge]}  Prove that if $n$ divides $3^n-1$, then $n=1$ or $n$ is even.



\end{enumerate}

\end{document}
