\documentclass{amsart}
%\usepackage{setspace}

%================DIMENSIONS======================
%\setlength{\textheight}{43pc}
%\setlength{\textwidth}{28pc} 

%\oddsidemargin 0.625in \evensidemargin 0.625in
%\textwidth 5.7in
%\topmargin 0.125in
%\headheight .21in
%\headsep .29in   % \headheight + \headsep = 0.5in
%\textheight 8in % \textheight includes \footskip
%\footskip .5in

%\skip\footins 22.8pt plus 4pt minus 2pt
%\parskip 5 pt plus 1.5pt minus .5pt
%\itemsep 0 pt plus .5pt
%================DIMENSIONS======================

\usepackage{amsmath,amsthm,amsfonts,amscd,amssymb}

\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{ax}{Axiom}
\newtheorem{prob}{Problem}
\newtheorem{quest}{Question}
\newtheorem{conj}{Conjecture}

\theoremstyle{definition}
\newtheorem{defn}{Definition}[section]

\theoremstyle{remark}
\newtheorem{rem}{Remark}[section]
\newtheorem*{notation}{Notation}

\begin{document}
\title{MATH 175, Spring 2018, Final Exam}

\maketitle

\def\A{{\mathcal A}}
\def\B{{\mathcal B}}
\def\C{{\mathcal C}}
\def\D{{\mathcal D}}
\def\F{{\mathcal F}}
\def\x{{\mathcal H}}
\def\I{{\mathcal I}}
\def\J{{\mathcal J}}
\def\K{{\mathcal K}}
\def\kk{{\mathfrak K}}
\def\L{{\mathcal L}}
\def\M{{\mathcal M}}
\def\mm{{\mathfrak m}}
\def\MM{{\mathfrak M}}
\def\R{{\mathcal R}}
\def\s{{\mathcal S}}
\def\V{{\mathcal V}}
\def\X{{\mathcal X}}
\def\Y{{\mathcal Y}}
\def\Z{{\mathcal Z}}
\def\H{{\mathcal H}}
\def\OO{{\mathfrak O}}
\def\CC{{\mathfrak C}}
\def\cee{{\mathbb C}}
\def\Nn{{\mathbb N}}
\def\pee{{\mathbb P}}
\def\que{{\mathbb Q}}
\def\real{{\mathbb R}}
\def\zed{{\mathbb Z}}
\def\hyp{{\mathbb H}}
\def\AA{{\mathbb A}}
\def\hs{{\hat \sigma}}
\def\gmn{{\mathbb G_m^N}}
\def\qbar{{\overline{\mathbb Q}}}
\def\kkbar{{\overline{\mathfrak K}}}
\def\kbar{{\overline{K}}}
\def\eps{{\varepsilon}}
\def\vek{{\varepsilon_k}}
\def\ahat{{\hat \alpha}}
\def\bhat{{\hat \beta}}
\def\gt{{\tilde \gamma}}
\def\h{{\tfrac12}}
\def\ba{{\boldsymbol a}}
\def\be{{\boldsymbol e}}
\def\bei{{\boldsymbol e_i}}
\def\bc{{\boldsymbol c}}
\def\bm{{\boldsymbol m}}
\def\bk{{\boldsymbol k}}
\def\bi{{\boldsymbol i}}
\def\bl{{\boldsymbol l}}
\def\bq{{\boldsymbol q}}
\def\bu{{\boldsymbol u}}
\def\bt{{\boldsymbol t}}
\def\bs{{\boldsymbol s}}
\def\bv{{\boldsymbol v}}
\def\bw{{\boldsymbol w}}
\def\bx{{\boldsymbol x}}
\def\bX{{\boldsymbol X}}
\def\bz{{\boldsymbol z}}
\def\bwy{{\boldsymbol y}}
\def\bg{{\boldsymbol g}}
\def\bY{{\boldsymbol Y}}
\def\bL{{\boldsymbol L}}
\def\baa{{\boldsymbol\alpha}}
\def\bb{{\boldsymbol\beta}}
\def\bet{{\boldsymbol\eta}}
\def\bxi{{\boldsymbol\xi}}
\def\bo{{\boldsymbol 0}}
\def\bol{{\boldsymbol 1}_L}
\def\ep{\varepsilon}
\def\p{\boldsymbol\varphi}
\def\q{\boldsymbol\psi}
\def\rank{\operatorname{rank}}
\def\aut{\operatorname{Aut}}
\def\lcm{\operatorname{lcm}}
\def\sgn{\operatorname{sgn}}
\def\spn{\operatorname{span}}
\def\md{\operatorname{mod}}
\def\Norm{\operatorname{Norm}}
\def\dim{\operatorname{dim}}
\def\det{\operatorname{det}}
\def\Vol{\operatorname{Vol}}
\def\rk{\operatorname{rk}}
\def\GL{\operatorname{GL}}

\begin{center}
{\bf Please print your name clearly!}
\end{center}
\bigskip

\noindent
{\bf Name:\underline{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  }}
\bigskip

\noindent
{\it This is a take-home test, due in class on Wednesday, 5/2/18. You may use your textbook for this class along with your in-class notes and homework solutions. You are not allowed to use any other materials. You are also not allowed to consult with anyone about this test. In other words, this should be solely your work with the use of (at most) class materials.}
\bigskip



\begin{prob} \label{p1}  {\bf (15 points)} 
Two prime numbers $p$ and $q$ are called {\bf twin primes} if $q=p+2$. Prove that there exists an integer $a$ such that $p|(a^2-q)$ if and only if there exists an integer $b$ such that $q|(b^2-p)$.
\bigskip

\noindent
{\bf Remark: \it It is a famous open problem to prove that there are infinitely many twin primes.}

\end{prob}
\newpage

\begin{prob} \label{p2} {\bf (30 points)} 

\noindent
{\bf a) - 15 points.} Let $x$ be an integer, and let $p$ be an odd prime. Prove that if $p|(x^2+1)$, then $p \equiv 1\ (\md 4)$. 

\noindent
{\bf b) - 15 points.} Use part a to prove that there are infinitely many primes congruent to 1 mod 4.


\end{prob}

\newpage

\begin{prob} \label{p3} {\bf (30 points)} As usual, write $\mu$ for the M\"obius function, and $\omega$ the number of prime divisors function. Prove the following two formulas:
\medskip

{\bf a) - 15 points.} For any positive integer $n$,
$$\mu(n) \mu(n+1) \mu(n+2) \mu(n+3) = 0.$$
\smallskip

{\bf b) - 15 points.} For any positive integer $n$,
$$\sum_{d \mid n} \left| \mu(d) \right| = 2^{\omega(n)}.$$

\end{prob}



\newpage

\begin{prob} \label{p4}  {\bf (15 points)} Let $n > 2$ be an integer. Define $S(n)$ to be the sum of all integers $t$ such that $1 \leq t \leq n$ and $\gcd(t,n)=1$. Let $\varphi(n)$ be Euler $\varphi$-function. What is $S(n)/\varphi(n)$ equal to?
\end{prob}

\newpage

\begin{prob} \label{p5}  {\bf (10 points)} Let $p$ be an odd prime, and suppose that $a$ and $b$ are primitive roots modulo $p$. Prove that $ab$ is {\bf not} a primitive root modulo $p$.
\end{prob}

\newpage

\begin{prob} \label{p6}  {\bf (10 points)}

Tchebyshev said, and I'll say it again - 

There is always a prime between $n$ and $2n$
\bigskip

\noindent
This statement is called {\bf Bertrand's postulate}. We will not quite prove that. Instead, use Tchebyshev's Theorem to prove that there exists a positive real number $C$ such that for any real number $x > C$ there exists a prime $p$ such that 
$$x < p \leq 200x.$$
\end{prob}

\newpage

\begin{prob} \label{p7}  {\bf (10 points)} Let $k,m_1,\dots,m_{k+1}$ be positive integers, each greater than 1. Assume that the integers $m_1,\dots,m_{k+1}$ are pairwise relatively prime. Prove that there exist $k+1$ consecutive integers $n,n+1,\dots,n+k$ such that $m_{i+1}^2 | (n+i)$ for each $0 \leq i \leq k$.

\end{prob}



\end{document}