\documentclass[a4paper,12pt,twoside,draft]{amsart}
\usepackage[headings]{fullpage}

\title{Math 365, Final examination solutions}
\author{David Pierce}
\date{January 11, 2008}

\address{Mathematics Dept\\
Middle East Technical University\\
Ankara 06531, Turkey}

\email{dpierce@metu.edu.tr}
\urladdr{http://www.math.metu.edu.tr/~dpierce/}

\usepackage{multicol}
\usepackage{hfoldsty} % provides oldstyle numerals in text mode
\usepackage{verbatim}  % provides comment environment
\usepackage{amsmath,amsthm,amssymb}
\usepackage{layout}

\newcommand{\size}[1]{\left|#1\right|}
%\theoremstyle{definition}
\newtheorem{Problem}{Problem}
\newenvironment{problem}{\begin{Problem}}{\end{Problem}}
\theoremstyle{definition}
\newtheorem*{solution}{Solution}
\theoremstyle{remark}
\newtheorem*{remark}{Remark}

\renewcommand{\theenumi}{\alph{enumi}}
\renewcommand{\labelenumi}{(\theenumi)}
\renewcommand{\theenumii}{\roman{enumii}}

\renewcommand{\leq}{\leqslant}
\newcommand{\Iff}{\iff}
\newcommand{\N}{\mathbb N}

\newcommand{\divides}{\mathrel{|}}
\newcommand{\ndivides}{\mathrel{\nmid}}
\renewcommand{\land}{\mathrel{\&}}
%\newcommand{\ls}[2]{\left(\displaystyle\frac{#1}{#2}\right)}
\newcommand{\ls}[2]{\Bigl(\displaystyle\frac{#1}{#2}\Bigr)}
\newcommand{\ord}[2]{\operatorname{ord}_{#1}(#2)}

\newcommand{\hw}[1]{\hfill{}\textnormal{[#1]}}

\begin{document}
\maketitle


The following table of powers of $3$ \emph{modulo} $257$ was provided
for use in several problems:

\begin{center}
\makebox[0pt]{
$\setlength{\arraycolsep}{2pt}
  \begin{array}{|c||*{16}{r|}}\hline
     k &1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\\hline\hline
 3^k &3&9&27&81&-14&-42&-126&-121&-106&-61&74&-35&-105&-58&83&-8\\\hline
 3^{16+k} &-24&-72&41&123&112&79&-20&-60&77&-26&-78&23&69&-50&107&64\\\hline
 3^{32+k} &-65&62&-71&44&-125&-118&-97&-34&-102&-49&110&73&-38&-114&-85&2\\\hline
 3^{48+k} &6&18&54&-95&-28&-84&5&15&45&-122&-109&-70&47&-116&-91&-16\\\hline
 3^{64+k} &-48&113&82&-11&-33&-99&-40&-120&-103&-52&101&46&-119&-100&-43&128\\\hline
 3^{80+k} &127&124&115&88&7&21&63&-68&53&-98&-37&-111&-76&29&87&4\\\hline
 3^{96+k} &12&36&108&67&-56&89&10&30&90&13&39&117&94&25&75&-32\\\hline
 3^{112+k} &-96&-31&-93&-22&-66&59&-80&17&51&-104&-55&92&19&57&-86&-1\\\hline
  \end{array}$
}
\end{center}


\begin{problem}
  For positive integers $n$, let $\omega(n)=\size{\{p\colon
  p\divides n\}}$, the number
  of primes dividing~$n$.
  \begin{enumerate}
    \item
Show that the function $n\mapsto2^{\omega(n)}$ is multiplicative.
\item
Define the M\"obius function $\mu$ in terms of $\omega$.
\item
Show $\displaystyle\sum_{d\divides n}\size{\mu(d)}=2^{\omega(n)}$ for
all positive integers $n$.
  \end{enumerate}
\end{problem}
Powers of $3$ \emph{modulo} $257$:

\begin{solution}
  \begin{enumerate}
    \item
If $\gcd(m,n)=1$, then $\omega(mn)=\omega(m)+\omega(n)$, so
\begin{equation*}
2^{\omega(mn)}=2^{\omega(m)+\omega(n)}=2^{\omega(m)}\cdot
2^{\omega(n)}.
\end{equation*}
\item
$\mu(n)=
  \begin{cases}
    0,&\text{ if $p^2\divides n$ for some $p$;}\\
(-1)^{\omega(n)},&\text{ otherwise.}
  \end{cases}$
\item
As $\mu$ is multiplicative, so are $\size{\mu}$ and
$n\mapsto\sum_{d\divides n}\size{\mu(d)}$.  Hence it is enough to
establish the equation when $n$ is a prime power.  We have
\begin{equation*}
  \sum_{d\divides p^s}\size{\mu(d)}=\sum_{k=0}^s\size{\mu(p^k)}
=\size{\mu(1)}+\size{\mu(p)}=1+1=2=2^1=2^{\omega(p^s)}.
\end{equation*}
  \end{enumerate}
\end{solution}

  \begin{problem}
    Fill out the following table of Legendre symbols:
    \begin{equation*}
      \begin{array}{|c*{9}{|r}|}\hline
	a&1&2&3&5&7&11&13&17&19\\\hline
\left(\displaystyle\frac a{257}\right)&&&&&&&&&\\\hline
      \end{array}
    \end{equation*}
  \end{problem}

  \begin{solution}
By the table of powers, $3$ must be a primitive root of $257$.  Hence
$(a/257)=1$ if and only if $a$ is an even power of $3$ \emph{modulo}
$257$.  In particular, $(-1/257)=1$, so $(a/257)=(-a/257)$.  So the
table of powers yields the answers:
\begin{equation*}
      \begin{array}{|c*{9}{|r}|}\hline
	a&1&2&3&5&7&11&13&17&19\\\hline
\left(\displaystyle\frac a{257}\right)&1&1&-1&-1&-1&1&1&1&-1\\\hline
      \end{array}
    \end{equation*}    
  \end{solution}

  \begin{remark}
    Many people preferred to find these Legendre symbols by means of
    the Law of Quadratic Reciprocity.  Possibly this method is faster than
    hunting for numbers in the table of powers; but it may also provide
    more opportunity for error.
  \end{remark}

  \begin{problem}
In the following table, in the box below each number $a$, write the
least positive integer $n$ such that $\ord{257}n=a$. 
\begin{equation*}
  \begin{array}{*{9}{|r}|}\hline
    1&2&4&8&16&32&64&128&256\\\hline
     & & & &  &  &  &   &    \\\hline
  \end{array}
\end{equation*}
  \end{problem}

  \begin{solution}
    If $r$ is a primitive root of $257$, then
    $\ord{257}{r^{256/a}}=a$.  The primitive roots of $257$ are $3^s$,
    where $s$ is odd.  So below $a$ we want the least $n$ such that
    $n\equiv3^{(256/a)\cdot s}$ for some odd $s$. 
    (In searching the table of powers, since $3^{k+128}\equiv-3^k$, we can
    ignore signs, except when $a\leq2$.  For example, when $a=4$, then
    $3^{(256/a)\cdot s}=3^{64s}$, so $n$ can only be $\size{3^{64}}$.
    When $a=32$, then $3^{(256/a)\cdot s}=3^{8s}$, so $n$ will be the
    absolute value of an entry in the column of powers that is headed
    by $8$.) 
\begin{equation*}
  \begin{array}{*{9}{|r}|}\hline
    1&  2& 4&8&16&32&64&128&256\\\hline
    1&256&16&4& 2&15&11&  9&  3\\\hline
  \end{array}
\end{equation*}
  \end{solution}

  \begin{remark}
Another way to approach the problem is to note that
\begin{equation*}
    \ord{257}{3^k}=\frac{256}{\gcd(256,k)}.
\end{equation*}
Then one must look among those powers $3^k$ such that
$\gcd(256,k)=256/a$.  \emph{Some} explanation is necessary, though it
need not be so elaborate as what I gave above.

    Some people apparently misread the problem as asking for the
    orders of the given numbers.  Others provided numbers that had the
    desired orders; but they weren't the \emph{least positive} such numbers.
  \end{remark}

  \begin{problem}
    Solve $x^2+36x+229\equiv0\pmod{257}$.
  \end{problem}

  \begin{solution}
Complete the square:
    $(36/2)^2=(2\cdot 9)^2=4\cdot 81=324$, and $324-229=95$, so (using
    the table of powers)
    \begin{align*}
      x^2+36x+229\equiv0
&\iff(x+18)^2\equiv95\equiv3^{128+52}\equiv3^{180}\equiv(3^{90})^2\\
&\iff x+18\equiv\pm3^{90}\equiv\mp98\\
&\iff x\equiv-116,80\\
&\iff x\equiv 141,80\pmod{257}.
    \end{align*}
  \end{solution}

  \begin{remark}
    There were a few unsuccessful attempts to factorize the polynomial
    directly.  See my remark on Problem 7 of Exam 3.
  \end{remark}

  \begin{problem}
    Solve $197^x\equiv137\pmod{257}$.
  \end{problem}

  \begin{solution}
From the table of powers of $3$, we can obtain logarithms:
    \begin{align*}
      197^x\equiv137\pmod{257}
&\iff(-60)^x\equiv-120\pmod{257}\\
&\iff x\log_3(-60)\equiv\log_3(-120)\pmod{256}\\
&\iff x\cdot24\equiv72\pmod{256}\\
&\iff x\cdot8\equiv24\pmod{256}\\
&\iff x\equiv3\pmod{32}\\
&\iff x\equiv 3,35,67,99,131,163,195,227\pmod{256}.
    \end{align*}
  \end{solution}

  \begin{remark}
    A number of people overlooked the change of modulus when passing
    from $x\cdot 8\equiv24$ to $x\equiv 3$.  One need not use
    logarithms explicitly; one can observe instead
    $197\equiv-60\equiv3^{24}$ and
    $137\equiv-120\equiv3^{72}\pmod{256}$, so that
    \begin{align*}
      197^x\equiv137\pmod{257}
&\iff3^{24x}\equiv3^{72}\pmod{257}\\      
&\iff24x\equiv72\pmod{256},
    \end{align*}
and then proceed as above.
  \end{remark}

\begin{problem}
Solve $127x+55y=4$.
\end{problem}

\begin{solution}
  Use the Euclidean algorithm:
  \begin{equation*}
    \begin{aligned}[t]
      127&=55\cdot2+17,\\
       55&=17\cdot3+4,\\
       17&= 4\cdot 4+1,
    \end{aligned}\qquad
    \begin{aligned}[t]
      17&=127-55\cdot 2,\\
 4&=55-(127-55\cdot2)\cdot3=55\cdot7-127\cdot3,\\
1&=17-4\cdot4=127-55\cdot2-(55\cdot7-127\cdot3)\cdot4\\
&=127\cdot13-55\cdot30.
    \end{aligned}
  \end{equation*}
Hence $4=127\cdot52-55\cdot 120$, and $\gcd(127,55)=1$, so the
original equation has the general 
solution 
\begin{equation*}
(52,-120)+(55,-127)\cdot t.
\end{equation*}
\end{solution}

\begin{remark}
Some people omitted
  to find the general solution.
  In carrying out the Euclidean algorithm here, one can save a step,
  as some people did, by
  noting that, once we find $4=55\cdot 7-127\cdot3$, we need not find
  $1$ as a linear combination of $127$ and $55$; we can pass
  immediately to the general solution $(7,-3)+(55,-127)\cdot t$.
\end{remark}

\begin{problem}
  Solve $x^2\equiv59\pmod{85}$.
\end{problem}

\begin{solution}
Since $85=5\cdot 17$, we first solve $x^2\equiv59$ \emph{modulo} $5$
and $17$ separately:
\begin{equation*}
  \begin{aligned}[t]
 &   x^2\equiv59\pmod5\\
&\iff x^2\equiv4\pmod5\\
&\iff x\equiv\pm2\pmod5;
  \end{aligned}\qquad
  \begin{aligned}[t]
& x^2\equiv59\pmod{17}\\
&\iff x^2\equiv8\pmod{17}\\
&\iff x^2\equiv25\pmod{17}\\
&\iff x\equiv\pm5\pmod{17}.
  \end{aligned}
\end{equation*}
Now there are four systems to solve:
\begin{gather*}
  \left.
\begin{aligned}
    x&\equiv\pm2\pmod5\\
x&\equiv\pm5\pmod{17}
  \end{aligned}
\right\}
\iff x\equiv\pm22\pmod{85},\\
\left.
\begin{aligned}
    x&\equiv\pm2\pmod5\\
x&\equiv\mp5\pmod{17}  
\end{aligned}
\right\}
\iff x\equiv\pm12\pmod{85}.
\end{gather*}
(I solved these by trial.)
So the original congruence is solved by
\begin{equation*}
  x\equiv\pm22,\pm12\pmod{85},
\end{equation*}
or $x\equiv12,22,63,73\pmod{85}$.
\end{solution}

\begin{remark}
  One may, as some people did, use the algorithm associated with the
  Chinese Remainder Theorem here.  Even if we do not use the
  algorithm, we rely on it to know that the solution we find to each
  pair of congruences is the \emph{only} solution.  Some used a
  theoretical formation of the solution, noting for example that 
$\left\{\begin{aligned}
    x&\equiv2\pmod5\\
x&\equiv5\pmod{17}
  \end{aligned}
\right\}$ has the solution $x\equiv2\cdot17^{\phi(5)}+5\cdot
5^{\phi(17)}\pmod{85}$; but this is not \emph{useful} (the number is
not between $0$ and $85$, or between $-85/2$ and $85/2$).
\end{remark}

%\layout
\end{document}



%\layout
\end{document}