Solutions to Quiz # 9 for Dr. Z.’s Number Theory Course for Nov. 21, 2013

1. (5 points) State the Möbius inversion formula, and check it empirically for all n ∈ Div(30) sol. to 1: If f(n) is any function defined on the intgers, and you define a brand-new function

g(n) := ∑_{d|n} f(d) ,

then you can get the function f(n) back from the function g(n) in terms of the formula

f(n) := ∑_{d|n} μ(d)g(n/d) ,

where μ(d) is the famous Möbius function. Now 30 = 2 · 3 · 5 so

Div(30) = {1, 2} · {1, 3} · {1, 5} = {1, 2, 3, 6} · {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} .

We have for n ∈ Div(30):

g(1) = f(1) ,
g(2) = f(1) + f(2) ,
g(3) = f(1) + f(3) ,
g(5) = f(1) + f(5) ,
g(6) = f(1) + f(2) + f(3) + f(6) ,
g(10) = f(1) + f(2) + f(5) + f(10) ,
g(15) = f(1) + f(3) + f(5) + f(15) ,
g(30) = f(1) + f(2) + f(3) + f(5) + f(6) + f(10) + f(15) + f(30) .

Now let’s compute ∑_{d|n} μ(d)g(n/d) for all n ∈ Div(30). n=1:

∑_{d|1} μ(d)g(1/d) = μ(1)g(1) = f(1)

n=2:

∑_{d|2} μ(d)g(2/d) = μ(1)g(2) + μ(2)g(1) = g(2) − g(1) = f(1) + f(2) − f(1) = f(2) .

n=3:

∑_{d|3} μ(d)g(3/d) = μ(1)g(3) + μ(3)g(1) = g(3) − g(1) = f(1) + f(3) − f(1) = f(3) .

n=5:

∑_{d|5} μ(d)g(5/d) = μ(1)g(5) + μ(5)g(1) = g(5) − g(1) = f(1) + f(5) − f(1) = f(5) .

n=6:

∑_{d|6} μ(d)g(6/d) = μ(1)g(6) + μ(2)g(3) + μ(3)g(2) + μ(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:

∑_{d|10} μ(d)g(10/d) = μ(1)g(10) + μ(2)g(5) + μ(5)g(2) + μ(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:

∑_{d|15} μ(d)g(15/d) = μ(1)g(15) + μ(3)g(5) + μ(5)g(3) + μ(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:

∑_{d|30} μ(d)g(30/d)

= μ(1)g(30) + μ(2)g(15) + μ(3)g(10) + μ(5)g(6) + μ(6)g(5) + μ(10)g(3) + μ(15)g(2) + μ(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) .

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

(\frac{8}{19})

Sol. of 2.

We have to find

8^{(19−1)/2} mod 19 = 8^{9} mod 19 .

8^{1} mod 19 = 8
8^{2} mod 19 = 64 mod 19 = 7
8^{4} mod 19 = 7^{2} mod 19 = 49 mod 19 = −8
8^{8} mod 19 = (−8)^{2} mod 19 = 7

So

8^{9} mod 19 = 8 · 8^{8} mod 19 = 8 · 7 mod 19 = 56 mod 19 = −1 .

Ans. to 2: (\frac{8}{19}) = −1

Note: Some people used the rule (\frac{ab}{p}) = (\frac{a}{p}) (\frac{b}{p}) To first do

(\frac{8}{19}) = (\frac{2}{19})^{3} ,

and then found out that 2^{9} mod 19 = −1. That’s OK too.