\documentclass[11pt,a4paper,twoside]{article}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{hfoldsty}
\usepackage{typearea}
\usepackage{paralist}
\setlength{\parindent}{0pt}
\newtheorem{problem}{Problem}
\theoremstyle{definition}
\newtheorem*{solution}{Solution}
\theoremstyle{remark}
\newtheorem*{remark}{Remark}
\renewcommand{\theenumi}{\alph{enumi}}
\renewcommand{\labelenumi}{\theenumi.}
\renewcommand{\theequation}{\fnsymbol{equation}}
\newcommand{\included}{\subseteq}
\newcommand{\nincluded}{\nsubseteq}
\newcommand{\N}{\mathbb N}

\newcommand{\units}[1]{#1{}\!^{\times}}
\newcommand{\Zmod}[1][n]{\mathbb Z_{#1}}
\newcommand{\Zmodu}[1][n]{\units{\Zmod[#1]}}

\pagestyle{headings}

\renewcommand{\emptyset}{\varnothing}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\newcommand{\rem}[1]{\operatorname{rem}(#1)}
\usepackage{bm}
\usepackage{upgreek}
\newcommand{\divides}{\mid}
\newcommand{\ndivides}{\nmid}

\begin{document}
\title{METU MATH 365, Exam 2 \emph{solutions}}
\author{David Pierce} 
\date{Exam date: Thursday, December 16, 2010}
\maketitle

\begin{problem}
  Exactly one of $1458$ and $1536$ has a primitive root.  Which one,
  and why?  Find a primitive root of the number that has one.
\end{problem}

\begin{solution}
$1458=2\cdot729=2\cdot 3^6$ and
$1536=3\cdot 512=3\cdot 2^9$.

The numbers with primitive roots are just $2$, $4$, $p^k$, and $2\cdot
p^k$, where $p$ is an \emph{odd} prime. 

Therefore $1458$, but not $1536$, has a primitive root.

$\upphi(9)=6$, and
\begin{equation*}
\begin{array}{*8{|r}|}\hline
  k&1&2&3&4&5&6&\\\hline
5^k&5&-2&-1&4&2&1&\bmod 9\\\hline
\end{array}
\end{equation*}
so $5$ is a primitive root of $9$.

Then $5$ is a primitive root of $3^6$.

Since $5$ is odd, it is a primitive root of $1458$.
\end{solution}

\begin{remark}
\begin{asparaenum}[1.]
\item
A number of people computed $\upphi(1458)$ and $\upphi(1536)$, but
this is of no practical use in this problem. 
\item
Some people pointed out that if $a$ is a primitive root of $n$, then
$a^{\upphi(n)}\equiv1\pmod n$.  This is logically correct, but
useless, since by Euler's Theorem we have
$a^{\upphi(n)}\equiv1\pmod n$ whenever $\gcd(a,n)=1$ (not just when
$a$ is a primitive root). 
\item
Our sequence of theorems about primitive roots of composite numbers is
the following.  Throughout, $p$ is an odd prime. 
\begin{compactenum}[(i)]
\item
If $r$ is a primitive root of $p$, then $r$ or $r+p$ is a primitive
root of $p^2$. 
\item
If $r$ is a primitive root of $p^2$, then $r$ is a primitive root of
$p^s$ whenever $s\geqslant2$. 
\item
If $r$  is a primitive root of $p^s$ (where $s\geqslant2$), then $r$
or $r+p^s$ (whichever is odd) is a primitive root of $2p^s$. 
\end{compactenum}
Some people misremembered this sequence, or wrongly combined two of
its theorems.  For example, some wrote `If $r$ is a primitive root of
$p$, then $r$ or $r+p^s$ (whichever is odd) is a primitive root of
$2p^s$.'  This assertion is false.  It would be correct to say for
example, `If $r$ is a primitive root of $p^2$, then $r$ or $r+p^2$
(whichever is odd) is a primitive root of $2p^s$.'  Using this, one
might observe that $2$ is a primitive root of $9$, and therefore $11$
is a primitive root of $1458$. 
\end{asparaenum}
\end{remark}

\pagebreak

\begin{problem}
Remembering that $p$ is always prime,
  define the arithmetic function $\upomega$ by
  \begin{equation*}
 \upomega(n)=\sum_{p\divides n}1.
  \end{equation*}
  \begin{enumerate}
  \item
  Define $\upmu$, preferably using $\upomega$.
  \item 
Prove that, if $m$ and $n$ are co-prime, then
$\upomega(mn)=\upomega(m)+\upomega(n)$. 
\item
Prove that
\begin{equation*}
  \sum_{d\divides n}\uptau(d)\cdot\upmu(d)=(-1)^{\upomega(n)}.
\end{equation*}
\item
Find a simple description of the function $f$ given by
\begin{equation*}
f(n)=\sum_{d\divides n}\upomega(d)\cdot\upmu\Bigl(\frac nd\Bigr).
\end{equation*}
  \end{enumerate}
\end{problem}

\begin{solution}
\begin{asparaenum}
\item
$\mu(n)=\begin{cases}
	0,&\text{ if }p^2\divides n \text{ for some }p,\\
	(-1)^{\upomega(n)},&\text{ if }p^2\divides n \text{ for no }p.
\end{cases}$.
\item
Assume $m$ and $n$ are co-prime.  If $p\divides mn$, then
\begin{equation*}
p\divides m\iff p\ndivides n.
\end{equation*}
Therefore
\begin{equation*}
\upomega(mn)=\sum_{p\divides mn}1=\sum_{p\divides m}1+\sum_{p\divides n}1 =\upomega(m)+\upomega(n).
\end{equation*}
\item
Each side of the equation is multiplicative, and
\begin{equation*}
\sum_{d\divides p^k}\uptau(d)\cdot\upmu(d)=\uptau(1)\cdot\upmu(1)+\uptau(p)\cdot\upmu(p)=1-2=(-1)^{\upomega(p^k)}.
\end{equation*}
\item
By M\"obius inversion,
\begin{equation*}
\upomega(n)=\sum_{d\divides n}f(d).
\end{equation*}
Since also $\upomega(n)=\sum_{p\divides n}1$, we have
\begin{equation*}
f(n)=\begin{cases}
	1,&\text{ if $n$ is prime},\\
	0,&\text{ if $n$ is not prime.}
\end{cases}
\end{equation*}
\end{asparaenum}
\end{solution}

\begin{remark}
\begin{asparaenum}[1.]
\item
In my solution to part a, the condition `$p^2\divides n$ for no $p$'
is equivalent to `$p^2\ndivides n$ for all $p$'.  Similarly in part
d. 
\item
For part a, some people wrote (as part of their answer)
`$\upmu(n)=(-1)^s$ if $n=p_1\dotsm p_s$'.  Strictly, one must specify that
the $p_i$ are all distinct.  The best way that I know to do this is to
say $p_1<\cdots<p_s$. 
\item
As an alternative solution to part b, one can write (as some people
did) that, since $m$ and $n$ are co-prime, we have 
\begin{align*}
m&=p_1{}^{m(1)}\dotsm p_s{}^{m(s)},&
n&=q_1{}^{n(1)}\dotsm q_t{}^{n(t)},
\end{align*}
where the exponents are positive, $p_1<\cdots<p_s$, $q_1<\cdots<q_t$,
and $p_i\neq q_j$ in each case, and therefore 
\begin{equation*}
\upomega(mn)=s+t=\upomega(m)+\upomega(n).
\end{equation*}
This may be a clearer argument than the one I wrote above.  I don't
know a good way to make the argument just with the $\Sigma$-notation.  
Some people wrote
\begin{equation*}
 \text`\upomega(mn)=\sum_{pq\divides mn}1\text', 
 \end{equation*}
 which doesn't make sense.  (If it means anything, it means
 $\upomega(mn)$ is the number of factors $d$ that $mn$ has, where $d$
 is the product of two primes, possibly not distinct.  This is not
 what $\upomega(mn)$ is.) 
 Others wrote 
 \begin{equation*}
 \text`\upomega(mn)=\sum_{p\divides m}\sum_{q\divides n}1\text'; 
\end{equation*}
 this is meaningful, but false, since it makes $\upomega(mn)$ equal to
 the \emph{product} $\upomega(m)\cdot\upomega(n)$. 
 \item
 In part c, it doesn't hurt to say \emph{why} the two sides are
 multiplicative.  The left-hand side is multiplicative because the
 product of two multiplicative functions is multiplicative (we didn't
 prove this, but it's fairly obvious), and if $g$ is multiplicative,
 so is $n\mapsto\sum_{d\divides n}g(d)$ (we did prove this).  The
 right-hand side is multiplicative by part b. 
 \item
 In notation introduced in class, the function $f$ in part d is given
 by $f=\upomega*\mu$, and therefore $\upomega=f*1$ by M\"obius
 inversion.  It may not be immediately obvious that $f$ \emph{must} be
 as in the solution above.  But if $f$ \emph{is} that function, then
 indeed $\upomega=f*1$, and therefore $f=\upomega*\upmu$, as
 required.  So $f$ must be as given in the solution.
\end{asparaenum}
\end{remark}

\pagebreak

\begin{problem}
  Find the least positive $x$ such that
  \begin{equation*}
    11^{5117}x\equiv57\pmod{600}.
  \end{equation*}
\end{problem}

\begin{solution}
$600=2^3\cdot3\cdot5^2$, so $\upphi(600)=4\cdot2\cdot20=160$.
We compute
\fbox{\begin{math}
%  Code from TUGboat Vol. 18 (1997), No. 2 
\newdimen\digitwidth
\settowidth\digitwidth{0}
\def~{\hspace{\digitwidth}}
\def\divrule#1#2{%
   \noalign{\moveright#1\digitwidth%
   \vbox{\hrule width#2\digitwidth}}}
160\,
\begin{array}[b]{@{}r@{}}
   31\\\hline
\big)
\begin{array}[t]{@{}l@{}}
  5117\\
  480\\\divrule03
  ~317\\
  ~160\\\divrule13
  ~157
\end{array}
\end{array}
\end{math}}.  Hence
\begin{equation*}
5117\equiv157\equiv-3\pmod{160}.
\end{equation*}
Therefore
\begin{align*}
&\phantom{{}\iff{}}11^{1557}x\equiv5\pmod{600}\\
&\iff11^{-3}x\equiv5\pmod{600}\\
&\iff x\equiv5\cdot11^3\pmod{600}.
\end{align*}
But
\begin{gather*}
11^3=121\cdot11=1331\equiv131\pmod{600},\\
5\cdot131=655\equiv55\pmod{600},
\end{gather*}
so the least positive solution is \fbox{$55$}.
\end{solution}

\begin{remark}
Not too many problems here.  I'm guessing this is the sort of problem
that the \emph{dershane} prepares one for.  According to the Wikipedia
article `Long division', my notation for long division is what used in
Anglophone countries; the notation I see on papers, Francophone.  But
the symbolism $b\mathrel)a$ (used in the former notation) for $a/b$ is
traced to Michael Stifel of the University of Jena in Germany in 1544
(see the Wikipedia article `Division (mathematics)'). 
\end{remark}

\pagebreak

\begin{problem}
  \begin{enumerate}
  \item
Since $2$ is a primitive root of $29$, the function $x\mapsto\log_2x$
from $\Zmodu[29]$ to $\Zmod[28]$ is defined.  Considering this as a
function from $\{-14,\dots,-1,1,\dots14\}$ to $\{-14,\dots,14\}$,
fill out the table below.  
\begin{equation*}\renewcommand{\arraystretch}{2}
  \begin{array}{|r||*{14}{p{3.8mm}|}}\hline
        m & \hfill$1$ & \hfill$2$ & \hfill$3$ & \hfill$4$ & \hfill$5$
        & \hfill$6$ & \hfill$7$ & \hfill$8$ & \hfill$9$ & \hfill$10$ &
        \hfill$11$ & \hfill$12$ & \hfill$13$ & \hfill$14$\\\hline\hline
\log_2  m & & & & & & & & & &  &  &  &  &  \\\hline
\log_2(-m)& & & & & & & & & &  &  &  &  &  \\\hline
  \end{array}
\end{equation*}
\item
With respect to the modulus $29$, exactly
one of the two congruences
\begin{align*}
  x^{400}&\equiv13,&x^{400}&\equiv-13
\end{align*}
has a solution.  Find all of its solutions (\emph{modulo} $29$), and
explain why the other congruence has no solutions.
  \end{enumerate}
\end{problem}

\begin{solution}
\begin{asparaenum}
\item\mbox{}
\begin{equation*}
\makebox[0pt]{
\begin{math}%\renewcommand{\arraystretch}{2}
  \begin{array}{|r||*{14}{r|}}\hline
        m & 1&  2& 3&  4& 5& 6& 7&  8& 9&10&11&12& 13&14\\\hline\hline
\log_2  m & 0&  1& 5&  2&-6& 6&12&  3&10&-5&-3& 7&-10&13\\\hline
\log_2(-m)&14&-13&-9&-12& 8&-8&-2&-11&-4& 9&11&-7&  4&-1\\\hline
  \end{array}
\end{math}}
\end{equation*}
\item
For the first congruence, we have
\begin{gather*}
x^{400}\equiv13\pmod{29}\\
\iff 400\log x\equiv-10\pmod{28}\\
\iff200\log x\equiv-5\pmod{14};
\end{gather*}
 the congruence has no solution since $\gcd(200,14)=2$, and $2\ndivides-5$.
For the second congruence:
\begin{gather*}
x^{400}\equiv-13\pmod{29}\\
\iff 400\log x\equiv4\pmod{28}\\
\iff100\log x\equiv1\pmod{7}\\
\iff2\log x\equiv1\pmod7\\
\iff\log x\equiv4\pmod 7\\
\iff\log x\equiv4,11,-10,-3\pmod{28}\\
\iff x\equiv-13,-11,13,11\pmod{29}.
\end{gather*} 
\end{asparaenum}
\end{solution}

\begin{remark}
The quickest way I know to fill out the table is, keeping in mind
\begin{equation*}
\log_2m\equiv k\bmod28\iff2^k\equiv m\bmod29,
\end{equation*}
to start out as follows,
\begin{equation*}
\makebox[0pt]{
\begin{math}%\renewcommand{\arraystretch}{2}
  \begin{array}{|r||*{14}{r|}}\hline
        m & 1&  2& 3&  4& 5& 6& 7&  8& 9&10&11&12& 13&14\\\hline\hline
\log_2  m & 0&  1&  &  2&  &  &  &  3&  &  &  &  &   &  \\\hline
\log_2(-m)&  &   &  &   &  &  &  &   &  &  &  &  &  4&  \\\hline
  \end{array}
\end{math}}
\end{equation*}
continuing to get
\begin{equation*}
\makebox[0pt]{
\begin{math}%\renewcommand{\arraystretch}{2}
  \begin{array}{|r||*{14}{r|}}\hline
        m & 1&  2& 3&  4& 5& 6& 7&  8& 9&10&11&12& 13&14\\\hline\hline
\log_2  m & 0&  1& 5&  2&  & 6&12&  3&10&  &  & 7&   &13\\\hline
\log_2(-m)&14&   &  &   & 8&  &  &   &  & 9&11&  &  4&  \\\hline
  \end{array}
\end{math}}
\end{equation*}
then filling in the remaining spaces by using
\begin{equation*}
\log m-\log(-m)\equiv\log(-1)\equiv\pm14\pmod{28}.
\end{equation*}
Some people may have done something like this, but they put the logarithms into the set $\{0,\dots,27\}$ rather than $\{-14,\dots,14\}$ as requested (this set could have been $\{-13,\dots,14\}$.  Other people gave negative logarithms, but they were off by $1$, as if the modulus had been taken as $29$ rather than $28$.  In solving the congruences, there were various confusions about modulus.
\end{remark}

\end{document}