%q9S.tex: 
%begin macros
\baselineskip=14pt
\parskip=10pt
\magnification=\magstephalf
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
\def\g{\bigtriangledown}
\def\S{\cal S}
\nopagenumbers
%end macros
 

\centerline
{
\bf  Solutions to Quiz \# 9 for Dr. Z.'s Number Theory
Course for Nov. 21, 2013
}
\bigskip

{\bf 1.} (5 points) State the M\"obius inversion formula, and check it empirically for
all $n \in Div(30)$

{\bf sol. to 1}: If $f(n)$ is any function defined on the integers, and
you define a brand-new function
$$
g(n):=\sum_{d|n} f(d) \quad ,
$$
then you can get the function $f(n)$ back from the function $g(n)$ in terms of
the formula
$$
f(n):=\sum_{d|n} \mu(d) g(n/d) \quad ,
$$
where $\mu(d)$ is the famous M\"obius function.

Now $30=2 \cdot 3 \cdot 5$ so
$$
Div(30)= \{1,2\} \cdot \{1,3\} \cdot \{1,5\}=
\{1,2,3,6\} \cdot \{1, 5 \}=
\{1,2,3,6, 5, 10, 15, 30\}
$$
$$
=\{1,2,3,6, 5, 10, 15, 30\} =\{1,2,3,5, 6, 10, 15, 30\} \quad .
$$

We have for $n \in Div(30)$:
$$
g(1)= f(1) \quad ,
$$
$$
g(2)= f(1) + f(2) \quad ,
$$
$$
g(3)= f(1) + f(3) \quad ,
$$
$$
g(5)= f(1) + f(5) \quad ,
$$
$$
g(6)=f(1)+f(2)+f(3)+f(6) \quad ,
$$
$$
g(10)=f(1)+f(2)+f(5)+f(10) \quad ,
$$
$$
g(15)=f(1)+f(3)+f(5)+f(15) \quad ,
$$
$$
g(30)=f(1)+f(2)+f(3)+f(5)+f(6)+ f(10)+f(15)+ f(30) \quad . 
$$

Now let's compute $\sum_{d|n} \mu(d) g(n/d)$ for all $n \in Div(30)$.

n=1:
$$
\sum_{d|1} \mu(d) g(1/d) = \mu(1) g(1)= f(1)
$$

n=2:
$$
\sum_{d|2} \mu(d) g(2/d) = \mu(1) g(2) + \mu(2) g(1) = g(2)-g(1)=
f(1)+f(2)-f(1)=f(2) \quad .
$$

n=3:
$$
\sum_{d|3} \mu(d) g(3/d) = \mu(1) g(3) + \mu(3) g(1) = g(3)-g(1)=
f(1)+f(3)-f(1)=f(3) \quad .
$$


n=5:
$$
\sum_{d|5} \mu(d) g(5/d) = \mu(1) g(5) + \mu(5) g(1) = g(5)-g(1)=
f(1)+f(5)-f(1)=f(5) \quad .
$$

n=6:
$$
\sum_{d|6} \mu(d) g(6/d) = \mu(1) g(6) + \mu(2) g(3) + \mu(3) g(2)+ \mu(6) g(1) = 
g(6) - g(3) - g(2)+g(1) = 
$$
$$
f(1)+f(2)+f(3)+f(6) - (f(1)+f(3)) - (f(1)+f(2))+f(1)= f(6)
$$


n=10:
$$
\sum_{d|10} \mu(d) g(10/d) = \mu(1) g(10) + \mu(2) g(5) + \mu(5) g(2)+ \mu(10) g(1) = 
g(10) - g(5) - g(2)+g(1) = 
$$
$$
f(1)+f(2)+f(5)+f(10) - (f(1)+f(5)) - (f(1)+f(2))+f(1)= f(10)
$$


n=15:
$$
\sum_{d|15} \mu(d) g(15/d) = \mu(1) g(15) + \mu(3) g(5) + \mu(5) g(3)+ \mu(15) g(1) = 
g(15) - g(5) - g(3)+g(1) = 
$$
$$
f(1)+f(3)+f(5)+f(15) - (f(1)+f(5)) - (f(1)+f(3))+f(1)= f(15)
$$


n=30:
$$
\sum_{d|30} \mu(d) g(30/d) 
$$
$$
= \mu(1) g(30) + \mu(2) g(15) + \mu(3) g(10) + \mu(5) g(6)+ \mu(6) g(5) +\mu(10)g(3) + \mu(15) g(2) + \mu(30) g(1)
$$
$$
= g(30) - g(15) - g(10) - g(6) + g(5) + g(3) +  g(2) - g(1)
$$
$$
f(1)+f(2)+f(3)+f(5)+f(6)+f(10)+f(15)+f(30)
$$
$$
-(f(1)+f(3)+f(5)+f(15)) -(f(1)+f(2)++f(5)+f(10))-(f(1)+f(2)+f(3)+f(6))
$$
$$
+(f(1)+f(5))+ (f(1)+f(3))+(f(1)+f(2))
$$
$$
-f(1)=f(30) \quad .
$$

{\bf 2.} (5 points) Using the important test (involving modular exponentiation) (no credit for brute force!) find 

$\left ( \frac{8}{19} \right )$ 

{\bf Sol. of 2}.

We have to find
$$
8^{(19-1)/2} \bmod 19 \quad = 8^{9} \bmod 19  \quad .
$$

$$
8^1 \bmod 19 = 8
$$
$$
8^2 \bmod 19 = 64 \bmod 19 = 7
$$
$$
8^4 \bmod 19 = 7^2 \bmod 19 = 49 \bmod 19 = -8 \quad
$$
$$
8^8 \bmod 19 = (-8)^2 \bmod 19 = 7 \quad
$$
So
$$
8^9 \bmod 19 = 8 \cdot 8^8 \bmod 19 = 8 \cdot 7 \bmod 19 = 56 \bmod 19 = -1 \quad .
$$

{\bf Ans. to 2}: $\left ( \frac{8}{19} \right )=-1$ 


{\bf Note}: Some people used the rule $\left ( \frac{ab}{p} \right )= \left ( \frac{a}{p} \right )\left ( \frac{b}{p} \right )$
To first do
$$
\left ( \frac{8}{19} \right )=\left ( \frac{2}{19} \right )^3 \quad,
$$ 
and then found out that $2^{9} \bmod 19 =-1$. That's OK too.

\end






