\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

\begin{center}

THEORY OF NUMBERS

ARITHMETIC FUNCTIONS

\end{center}

Functions defined on the set of natural numbers.

\begin{description}

\item[Definition]
$f(n)$ is multiplicative $\Leftrightarrow f(uv)=f(u).f(v)$
whenever $(uv)=1$.

\item[Theorem]
If $f(n)$ is multiplicative then $F(n)=\sum_{d|n}f(d)$ is also
multiplicative.

\item[Proof]
Let $(uv)=1$

\begin{eqnarray*}
F(uv)&=&\sum_{d|uv}f(a)\\ &=&\sum_{d_1|u}\sum_{d_2|u}f(d_1d_2)\\
&=&\sum_{d_1|u}f(d_1)\sum_{d_2|v}f(d_2)\\ &=&F(u)F(v)
\end{eqnarray*}

For every divisor of $uv \exists$ unique $d_1,\ d_2$ such that
$d_1|u\ d_2|v\ d_1d_2=1$.

\item[Definition]
$$d(n)=\sum_{d|n}1$$ $$\sigma(n)=\sum_{d|n}d$$

$d(n)$ and $\sigma(n)$ are both multiplicative. If $p$ is prime
the divisors of $p^\alpha$ are $1,p,p^2,\ldots,p^\alpha$ therefore

\begin{eqnarray*}
d(p^\alpha)&=&\alpha+1\\
\sigma(p^\alpha)&=&\frac{p^{\alpha+1}-1}{p-1}
\end{eqnarray*}

Hence if $n=p_1^{\alpha_1} p_2^{\alpha_2}\ldots p_k^{\alpha_k}$

\begin{eqnarray*}
d(n)&=&\prod_{i=1}^k(\alpha_i+1)\\
\sigma(n)&=&\prod_{i=1}^k\left(\frac{p_i^{\alpha_i+1}-1}{p_i-1}\right)
\end{eqnarray*}

\item[Example]
For every $\epsilon>0,\ d(n)=O(n^\epsilon)$.

Let $D(x)=\sum_{n\leq x}d(n)$ for $x\geq 1$.


\item[Theorem]
$D(x)=x\log x+(2j-1)x+O\left(x^\frac{1}{2}\right)$ for large $x$,
where $j$ is Euler's constant.

\item[Proof]
We shall first proof that

$$D(x)=2\sum_{n\leq
x^\frac{1}{2}}\left[\frac{x}{n}\right]-\left[x^\frac{1}{2}\right]^2\
(x\geq1)$$

Now $d(n)=\sum_{u,\ u|n}1=\sum_{u,v,\ uv=n}1$. So

\begin{eqnarray*}
D(x)&=&\sum_{u,\ v\ uv\leq x}1\\ &=&\sum_{u,\ v\ u\leq
x^\frac{1}{2} uv\leq x}1+\sum_{u,\ v\ u>x^\frac{1}{2}\ uv\leq
x}1\\ &=&\sum_{u\leq
x^\frac{1}{2}}\left[\frac{x}{u}\right]+\sum_{v\leq
x^\frac{1}{2}}\left\{\left[\frac{x}{v}\right]-\left[x^\frac{1}{2}\right]\right\}\\
&=&2\sum_{u\leq
x^\frac{1}{2}}\left[\frac{x}{u}\right]-\left[x^\frac{1}{2}\right]^2\\
&=&2\sum_{n\leq
x^\frac{1}{2}}\left(\frac{x}{n}+O(1)\right)-\left(x^\frac{1}{2}+O(1)\right)^2\\
&=&2x\sum_{n\leq
x^\frac{1}{2}}\frac{1}{n}+O(x^\frac{1}{n}-x+O(x^\frac{1}{2})\\
&=&2x\left(\log
x^\frac{1}{2}+j+O\left(\frac{1}{x^\frac{1}{2}}\right)\right)-x+O(x^\frac{1}{2}\\
&=&x\log x+(2j-1)x+O\left(x^\frac{1}{2}\right)
\end{eqnarray*}

\item[Perfect Numbers]
A perfect number is one for which $\sigma(n)=2n$

\item[Theorem (Euclid-Euler)]
If $p$ is a prime of the from $2^n-1$ then then number $2^{n-1}p$
is perfect and conversely every even perfect number is of this
form.

\item[Proof]
Suppose %p=2^{n}-1$ and $N=2^{n-1}p$.

\begin{eqnarray*}
\sigma(N)&=&\sigma(2^{n-1}p)=\sigma(2^{n-1})\sigma(p)\\
&=&(2_n-1)(1+p)=p.2^n=2N
\end{eqnarray*}

Suppose $N$ is an even perfect number. Write $N=2^{n-1}u$ where
$u$ is odd, so that $n\geq2$. Then
$2^nu=2N=\sigma(N)=\sigma(2^{n-1}u)=\sigma(2^{n-1})\sigma(u)=(2^n-1)\sigma(u)$

i.e. $\sigma(u)=\frac{2^nu}{2^n-1}=u+\frac{u}{2^n-1}$

$\frac{u}{2^n-1}$ is thus an integer, and it divides $u$.

\begin{eqnarray*}
\sigma(u)&=&\textrm{ sum of all divisors of }u\\ &=&u+\textrm{ one
divisor of }u
\end{eqnarray*}

and so this is the only other divisor of $u$, therefore $u=2^n-1$
and $u$ must be prime.

A number is said to be squarefree if it is not divisible by any
square $>1$.

\item[M\"{o}ebius function]

\item[M\"{o}ebius inversion formula]
We define $\mu(1)=1$ and if $n>1$

$\mu(n)=\left\{\begin{array}{cl}(-1)^r&\textrm{ if $n$ is the
product of $r$ distinct primes}\\0&\textrm{ if $n$ is not
squarefree}\end{array}\right.$

It is easy to see that $\mu$ is multiplicative.

\item[Theorem]
$$\sum_{d|n}\mu(d)=\left\{\begin{array}{cl}1&(n=1)\\
0&n>1\end{array}\right.$$

\item[Proof]
The case $n=1$ is trivial. If $n>1$ write $n=p_1^{\alpha_1}\ldots
p_r^{\alpha_r}$

$$\sum_{d|n}\mu(d)=\sum_{d|p_1^{\alpha_1}}\mu(p_1^{\alpha_1}\ldots
\sum_{d|p_r^{\alpha_r}} \mu(p_r^{\alpha_r})$$

\begin{eqnarray*}
\sum_{d|p^\alpha}\mu(d)&=&1+\mu(p)+\mu(p^2)+\ldots \mu(p^\alpha)\\
&=&1-1+0+\ldots+0=0
\end{eqnarray*}

Alternatively

\begin{eqnarray*}
\sum_{d|p_1^{\alpha_1}\ldots
p_r^{\alpha_r}}\mu(d)&=&\sum_{d|p_1\ldots p_r}\mu(d)\\
&=&1+^rc_1(-1)+^rc_2(-1)^2+\ldots^rc_r(-1)^r\\ &=&(1-1)^r=0
\end{eqnarray*}

\item[Theorem]
Given $g(n)$ defined on the natural numbers define
$f(n)=\sum_{d|n}g(d)$ then
$g(n)=\sum_{d|n}\mu(d)f\left(\frac{n}{d}\right)=\sum_{d|n}\mu\left(\frac{n}{d}\right)f(d)$

\item[Proof]
\begin{eqnarray*}
\sum_{d|n}\mu(d)f\left(\frac{n}{d}\right)&=&
\sum_{d|n}\mu(d)\sum_{t\left|\frac{n}{d}\right.}g(t)\\
&=&\sum_{t|n}g(t)\underbrace{\sum_{d\left|\frac{n}{t}\right.}
\mu(d)}_{=\begin{array}{cl}1&\textrm{ if
}t=n\\0&\textrm{otherwise}\end{array}}
\\ &=&g(n)
\end{eqnarray*}


\item[Theorem]
Suppose $G(x)$ is defined for $x\geq1$. Define $F(x)=\sum_{n\leq
x}G\left(\frac{x}{n}\right)\ x\geq1$

Then $G(x)=\sum_{n\leq x}\mu(n)F\left(\frac{x}{n}\right)$

\item[Proof]
\begin{eqnarray*}
\sum_{n\leq x}\mu(n)F\left(\frac{x}{n}\right)&=&\sum_{n\leq
x}\mu(n)\sum_{m\leq\frac{x}{n}}G\left(\frac{x}{mn}\right)\\
&=&\sum_{u\leq x}G\left(\frac{x}{u}\right)\sum_{m,\ n\
mn=u}\mu(n)\\ &=&\sum_{u\leq
x}G\left(\frac{x}{u}\right)\sum_{n|u}\mu(n)\\ &=&G(x)
\end{eqnarray*}

\item[Corollary]
$[x]=\sum_{n\leq x}1$ therefore $1=\sum_{n\leq
x}\mu(n)\left[\frac{x}{n}\right]$

\item[Euler's function]
$$\phi(n)=\sum_{d=1\ (d,n)-1}^n1$$

\item[Theorem]

\begin{description}

\item[(i)]
$\sum_{d|n}\phi(d)=n$

\item[(ii)]
$\frac{\phi(n)}{n}=\sum_{d|n}\frac{\mu(d)}{d}$

\item[(iii)]
$\phi(n)$ is multiplicative.

\item[(iv)]
$\frac{\phi(n)}{n}=\prod_{p|n}\left(1-\frac{1}{p}\right)$

\end{description}

\item[Proof]

\begin{description}

\item[(i)]
Consider the set $1,2,\ldots n$ and divide into classes $C_d$
where $r\in C_d\Leftrightarrow (r,n)=d$. $C_d$ is empty unless
$D|n$.

Suppose $D|n$ then $C_d$ consists of those $r$ among $1,2\ldots n$
for which $(r,n)=d$.

Write $r=dr'\ n=dn'\ (r',\ n')=1$

$C_d$ consists of those $r'$ among $1,2,\ldots\frac{n}{d}$ such
that $\left(r',\ \frac{n}{d}\right)=1$ therefore $C_d$ contains
exactly $\phi\left(\frac{n}{d}\right)$ elements. Therefore

$$\sum_{d|n}\phi(d)=\sum_{d|n}\phi\left(\frac{n}{d}\right)=n$$

\item[(ii)]
$n=\sum_{d|n}\phi(d)$ therefore
$\phi(n)=\sum_{d|n}\mu(d)\frac{n}{d}$ therefore
$\frac{\phi(n)}{n}=\sum_{d|n}\frac{\mu(d)}{d}$.

\item[(iii)]
$\mu(d)$ is multiplicative and $d$ is multiplicative,

therefore $\frac{\mu(d)}{d}$ is multiplicative,

therefore $\frac{\phi(n)}{n}$ is multiplicative,

$n$ is multiplicative therefore $\phi(n)$ is multiplicative.

\item[(iv)]
$\phi(1)=1$

$$\frac{\phi(n)}{n}=\sum_{d|p_1^{\alpha_1}\ldots
p_r^{\alpha_r}}\frac{\mu(d)}{d}=\sum_{d|p_1^{\alpha_1}}
\frac{\mu(d)}{d}\ldots\sum_{d|p_r^{\alpha_r}} \frac{\mu(d)}{d}$$

$$\sum_{d|p_1^{\alpha_1}}\frac{\mu(d)}{d}=\left(1-\frac{1}{p_1}\right)$$

Therefore $$\phi(n)=n\prod_{p|n}1-\frac{1}{p}$$

\end{description}

\item[The Zeta function]
$$\zeta(s)=\sum_{n=1}^\infty n^{-s}$$

\item[Theorem]
$$\zeta(s)=\prod_p\left(1-\frac{1}{p^s}\right)^{-1}$$

\item[Proof]
$\prod_p\left(1-\frac{1}{p^s}\right)^{-1}\\=\left(1+
\frac{1}{2^s}+\frac{1}{(2^2)^s}+\ldots\right)
\left(1+\frac{1}{3^s}+\frac{1}{(3^2)^s}+\ldots\right)
\ldots\left(1+\frac{1}{p^s}+\frac{1}{(p^2)^s}+\ldots\right)
\\=\sum_{n=1}^\infty n^{-s}$

$\zeta(s)$ is a special case of a Dirichlet series $\sum
c_nc^{-s}$

We have the following useful result concerning product of
Dirichlet series.

$$\sum_{u=1}^\infty a_uu^{-s}\sum_{v=1}^\infty
b_vv^{-s}=\sum_{n=1}^\infty c_nc^{-s}$$

where $c_n=\sum_{u,\ v\ uv=n} a_ub_v=\sum_{u|n}
a_nb_{\frac{n}{u}}$

In particular

$$\zeta(s)\sum_{u=1}^\infty a_uu^{-s}=\sum_{n=1}^\infty
c_n'n^{-s}$$

where $c_n'=\sum_{u|n}a_u$

\item[Theorem]
$\mu(n)$ is the coefficient of $n^{-s}$ in $\frac{1}{\zeta(s)}$

$d(n)$ is the coefficient of $n^{-s}$ in $\zeta^2(s)$

$\sigma(n)$ is the coefficient of $n^{-s}$ in $\zeta(s)\zeta(s-1)$

$\phi(n)$ is the coefficient of $n^{-s}$ in
$\frac{\zeta(s-1)}{\zeta(s)}$

\item[Proof]
$$\zeta(s)\sum_{n=1}^\infty \mu(n)n^{-s}=\sum_{n=1}^\infty
c_n'n^{-s}$$

$$c_n'=\sum_{d|n}\mu(d)=\left\{\begin{array}{cl}1&n=1\\0&n>1\end{array}\right.$$

Therefore $$\zeta(s)\sum_{n=1}^\infty\mu(n)u^{-s}=1$$

These calculations are only formal, and we must verify them in
some other way.

\begin{eqnarray*}
\frac{1}{\zeta(s)}&=&\prod\left(1-\frac{1}{p^s}\right)\\
&=&\left(1-\frac{1}{2^s}\right)\left(1-\frac{1}{3^s}\right)
\left(1-\frac{1}{5^s}\right)\ldots\\
&=&\sum_{n=1}^\infty\frac{\mu(n)}{n^s}
\end{eqnarray*}

$\zeta(s)\zeta(s-1)=\sum_{n=1}^\infty c_n'n^{-s},\
c_n'=\sum_{d|n}d=\sigma(n)$

The others are proved in similar ways.

Now consider $\sum_{n=1}^\infty
\sigma(n)n^{-s}=\zeta(s)\zeta(s-1)$.

Multiply by $\frac{1}{\zeta(s)}$

$$\sum_{n=1}^\infty\sum_{d|n}\left(\mu(d)\sigma
\left(\frac{n}{d}\right)\right)n^{-s}=\zeta(s-1)=
\sum_{n=1}^\infty nn^{-s}$$

Therefore

$$\sum_{d|n}\mu(d)\sigma\left(\frac{n}{d}\right)=n$$

This correspond to a M\"{o}ebius inversion, and whilst the
calculations are onlt formal, they are useful to discover
relations between the various arithmetic functions.

\item[Example]
Let $Q(x)$= the number of squarefree numbers not exceeding $x$.

$$Q(x)=\sum_{n\leq x}|\mu(n)|$$

Now

\begin{eqnarray*}
\sum{n=1}^\infty|\mu(n)|n^{-s}&=&\left(1+\frac{1}{2^s}\right)\left(1+\frac{1}{3^s}\right)\left(1+\frac{1}{5^s}\right)\ldots\\
&=&\prod_p\left(1+\frac{1}{p^s}\right)\\
&=&\frac{\prod\left(1-\frac{1}{p^s}\right)^{-1}}{\prod\left(1-\frac{1}{(p^2)^s}\right)^{-1}}\\
&=&\frac{\zeta(s)}{\zeta(2s)}\\ &=&\sum_{a=1}^\infty
a^{-s}\sum_{b=1}^\infty \mu(b)b^{-2s}\\
&=&\sum_{n=1}^\infty\left(\sum_{a,\ b\
ab^2=n}\mu(b)\right)n^{-s}\\
&=&\sum_{n=1}^\infty\left(\sum_{b^2|n}\mu(b)\right)n^{-s}
\end{eqnarray*}

Equating coefficients

$|\mu(n)|=\sum_{b\ b^2|n}\mu(b).$

The calculations are only formal and so we must prove this
relation.

Suppose $k^2$ is the largest square divisor of $n$, $n=n'k^2$
where $n'$ is squarefree then

$\sum_{b\ b^2|n}\mu(b)=\sum_{b\
b|k}\mu(b)=\begin{array}{cl}1&\textrm{ if }k=1\\0&\textrm{
otherwise }\end{array}$

$k=1\Leftrightarrow n$ is squarefree. So

\begin{eqnarray*}
Q(x)&=&\sum_{a,\ b\ ab^2\leq x}\mu(b)\\ &=&\sum_{b\leq
x^\frac{1}{2}}\mu(b)\sum_{a\leq\frac{x}{b^2}}1\\ &=&\sum_{b\leq
x^\frac{1}{2}}\mu(b)\left[\frac{x}{b^2}\right]\\ &=&x\sum_{b\leq
x^\frac{1}{2}}\frac{\mu(b)}{b^2}+O(x^\frac{1}{2})
\end{eqnarray*}

Now
$$\left|\sum_{b>x^\frac{1}{2}}\frac{\mu(b)}{b^2}\right|\leq\sum_{b\geq
x^\frac{1}{2}}\frac{1}{b^2}\leq\int_{x^\frac{1}{2}-1}^\infty
\frac{dt}{t^2}=O(x^{-\frac{1}{2}}$$

Therefore
$Q(x)=x\sum_{b=1}^\infty\frac{\mu(b)}{b^2}+O\left(x^\frac{1}{2}\right)$

$\sum\frac{\mu(b)}{b^2}=\frac{1}{\zeta(2)}$

$\zeta(2)=\sum\frac{1}{n^2}=\frac{\pi^2}{6}$

Therefore $Q(x)=\frac{6}{\pi^2}x+O\left(x^\frac{1}{2}\right)$

Every large integer can be represented as the sum of two
squarefree numbers.

\item[Example on M\"{o}ebius inversion]
Pick $a,\ b$ at random. What is the probability that $(a,\ b)=1$?
Define $N(x)=\begin{array}{c}1\leq a\leq x\\1\leq b\leq
x\end{array} (a,\ b)=1$

Total number of point $=[x]^2$

Probability $=\lim_{x\to\infty}\frac{N(x)}{[x]^2}$

Divide the points $(a,\ b), 1\leq a \leq x\ 1\leq b\leq x$ into
classes $C_n$ where $(a,\ b)\in C_n\Leftrightarrow (a,b)=n$

Each point goes into just one class therefore $[x]^2=\sum_{n\leq
x}|c_n|$

Write $a=na'\ b=nb'$ then $1\leq a'\leq \frac{x}{n}\ 1\leq b'\leq
\frac{x}{n}\ (a',b')=1$

Therefore $|C_n|=N\left(\frac{x}{n}\right)$

Therefore $[x]^2=\sum_{n\leq x}N\left(\frac{x}{n}\right)$

Using the M\"{o}ebius inversion formula we get

\begin{eqnarray*}
N(x)&=&\sum_{n\leq x}\mu(n)\left[\frac{x}{n}\right]^2\\
\left[\frac{x}{n}\right]^2&=&\left(\frac{x}{n}+O(1)\right)^2=\frac{x^2}{n^2}+O\left(\frac{x}{n}\right)+O(1)\\
\textrm{Therefore }N(x)&=&x^2\sum_{n\leq
x}\frac{\mu(n)}{n^2}+O(x\sum_{n\leq x}\frac{1}{n}\\
&=&x^2\sum_{n\leq x}\frac{\mu(n)}{n^2}+O(x\log x)\\
&=&x^2\frac{6}{\pi^2}+O(x\log x)\\ \textrm{Therefore
}\lim_{x\to\infty}\frac{N(x)}{[x]^2}&=&\lim_{x\to\infty}\frac{\frac{6}{\pi^2}x^2+O(x\log
x)}{x^2}\\ &=&\frac{6}{\pi^2}
\end{eqnarray*}

\end{description}

\end{document}