## 507 – Homework 2

This set is due Monday, October 18.

1. Given arithmetic functions ${f,g:{\mathbb Z}^+\rightarrow{\mathbb C}}$, define their convolution ${f*g}$ by
$\displaystyle f*g(n)=\sum_{d|n}f(d)g(n/d),$

so that if ${D_h}$ is the Dirichlet series associated to a function ${h}$, then ${D_{f*g}=D_fD_g}$.

Last homework we showed that ${D_\mu\zeta=1}$, i.e., ${\mu*\vec 1=\delta}$, where ${\vec 1}$ is the function that always takes the value ${1}$, and ${\delta}$ is the function that takes value 1 at 1, and 0 otherwise.

Prove the Möbius inversion formula: If ${F=f*\vec 1}$, i.e., ${F(n)=\sum_{d|n}f(d)}$ for all ${n\ge 1}$, then

$\displaystyle f(n)=\sum_{d|n}\mu\left(\frac nd\right)F(d)$

for all ${n\ge 1}$. (This is Theorem 6.14 in the text, try to prove it without looking at the argument there.)

Use this and the fact shown in class that ${\varphi*1=\text{id}}$ to find a formula for Euler’s ${\varphi}$.

A function ${f}$ is multiplicative iff ${f(ab)=f(a)f(b)}$ whenever ${a,b}$ are relatively prime. Let ${F}$ be the function defined by ${F=f*\vec 1}$. Show that if ${f}$ is multiplicative, then so is ${F}$.

Also, solve exercise 8.2.5 from the book.

2. This exercise continues the analysis of ${{\mathbb Z}[i]}$ from the first homework. First, by induction on ${N(\alpha)}$, show that any ${\alpha\in{\mathbb Z}[i]}$ that is not a unit and is not 0 is a product of irreducibles.Second, show that ${{\mathbb Z}[i]}$ is a principal ideal domain (pid). This means that ${{\mathbb Z}[i]}$ has no zero divisors and that every ideal is principal. You may want to look up the meaning of these terms in an abstract algebra book if needed. Here is a hint, it should remind you of the corresponding argument we proved for ${{\mathbb Z}}$: Given an ideal ${I\ne\{0\}}$, let ${\alpha\in I}$ be of minimal norm among the nonzero elements of ${I}$. We want to show that ${I}$ consists precisely of the multiples of ${\alpha}$. For this, show that the ${\gamma\alpha}$ with ${\gamma\in{\mathbb Z}[i]}$ form the vertices of an infinite family of squares that fill up the plane. For example, one of these squares has vertices ${0,\alpha,i\alpha,(1+i)\alpha}$. Check that ${I}$ contains all these ${\gamma\alpha}$, and nothing else, or else a geometric argument shows that ${N(\alpha)}$ is not minimal.

Use that ${{\mathbb Z}[i]}$ is a pid to conclude that ${{\mathbb Z}[i]}$ admits unique factorization.

Here is a way of using these results to show Fermat’s two squares theorem: Let ${p}$ be a prime with ${p\equiv1\pmod4}$. We know that the equation ${x^2\equiv-1\pmod p}$ has a solution ${x=n\in{\mathbb Z}}$. Use that ${p|(n^2+1)=(n+i)(n-i)}$ to conclude that ${p}$ is not irreducible in ${{\mathbb Z}[i]}$. By considering a product ${p=\alpha\beta}$ where neither ${\alpha}$ nor ${\beta}$ is a unit, and taking norms, conclude that ${p}$ must be a sum of two squares.

3. The goal of this exercise is to show that the proof given in lecture of Fermat’s result discussed in the previous exercise generalizes to show:
1. A prime ${p}$ is of the form ${x^2+2y^2}$ iff ${p=2}$ or ${p\equiv1,3\pmod8}$.
2. A prime ${p}$ is of the form ${x^2+3y^2}$ iff ${p\equiv 1\pmod 3}$.

First, check that for any ${n>0}$,

$\displaystyle (x^2+ny^2)(z^2+nw^2)=(xz\pm nyw)^2+n(xw\mp yz)^2.$

We proved that if ${N}$ is sum of two relatively prime squares and so is the prime ${q}$, and ${q|N}$, then ${N/q}$ is itself sum of two relatively prime squares. State and prove the appropriate version of this result for each of the two cases we are now considering. Check that the argument works when ${n=3}$ and ${q=4}$ (although of course 4 is not prime).

Show that the descent argument can be adapted to show that if a prime ${p}$ divides a number of the form ${x^2+2y^2}$ with ${(x,y)=1}$, then ${p}$ has the form ${x_1^2+2y_1^2}$.

Show the similar result for ${x^2+3y^2}$. Be careful, since you must ensure that the prime ${q that is obtained in this case is odd (because the result fails for ${p=2}$).

Suppose that ${p=3k+1}$ is prime. Prove that ${x^2\equiv -3\pmod 3}$ has a solution, by appropriately factoring ${4(x^{3k}-1)}$.

Conclude the proofs.

Typeset using LaTeX2WP. Here is a printable version of this post.

### 4 Responses to 507 – Homework 2

1. Jason Droesch says:

Dr. Caicedo:

I’m having trouble interpreting the l-function defined on p. 275 in reference to exercise 8.2.5 in our text. I’m not sure the difference between l(n) and the von Mangoldt Function. I mean I can read the difference: in $\ell(n)$, n = p is a prime power; and in von Mangoldt, it’s $n = p^k$ is a prime power. I’m just not sure how to interpret the difference.

Thanks for any help.

• Jason Droesch says:

I guess I mean to ask would say n = 9 count as a prime power for $\ell(n)$?

• Oh, that’s a typo! I have it in my list but hadn’t typed it yet, sorry.

For $\ell$, $n$ needs to be a prime number. Also, for $\Lambda$, $n$ needs to be a non-trivial prime power, i.e., $k>0$.

2. Jason Droesch says:

Thank you!