\part{Elementary arithmetic functions}
\chapter{Arithmetic function}

\section{Arithmetic function}
We have been implicitly using functions to aid our analysis of the integers, notably the GCD, LCM, and Euler's totient function. 
These are called \emph{arithmetic functions}, and are used to characterize and relate integers in various contexts and through various means. It's often a way that inherently algebraic or combinatoric concepts are manifested in the realm of elementary probability theory.

An \emph{arithmetic function} is a function $f : \mathbb{N} \setminus \{0\} \to \mathbb{C}$ with a domain of the positive integers and its image being a subset of the complex numbers.


\section{Additivity and multiplicativity}

An \emph{additive function} is an arithmetic function where multiplication of coprime domain elements corresponds to addition of image elements.
\[f \text{ is additive } \iff [  \gcd (a,b)=1 \implies f(ab)=f(a)+f(b) ]  \]
A \emph{totally additive function} drops the requirement for coprimality.
\[f \text{ is completely additive } \iff  f(ab)=f(a)+f(b)  \]



A \emph{multiplicative function} is an arithmetic function where multiplication of coprime domain elements corresponds to multiplication of image elements.
\[f \text{ is multiplicative } \iff [  \gcd (a,b)=1 \implies f(ab)=f(a)f(b) ]  \]
A \emph{totally multiplicative function} drops the requirement for coprimality.
\[f \text{ is totally multiplicative } \iff  f(ab)=f(a)f(b) \]


\section{Examples of familiar arithmetic functions}



\chapter{Divisor functions}

\section{Divisor functions}
\[ \sigma_z (n) = \sum_{d|n} d^z \]

\section{Tau function}
The specific function $ \sigma_0 =\tau $ simply counts divisors.
\[ \sigma_0 \text{ is multiplicative} \]

\[ \sigma_0 (p) = 2 \]
\[ \sigma_0 (p^n) = n+1 \]
\[ \sigma_0 (n\#) = 2^n \]

\section{Higher order divisor function}
The function $\sigma_1 = \sigma$ is the sum of divisors.
\[ \sigma_1 (p) = p+1 \]
\[ \sigma_1 \text{ is multiplicative} \]

- pentagonal number theorem
-  proper divisor
divisor of a number that isn't the number itself.
- perfect number
A \emph{perfect number} is an integer that equals the sum of its propee divisoes.
\[n \text{ is perfect} \iff n= \sigma_1 (n) -n \]
\chapter{Totient functions}
- what does totient mean
\section{Euler's totient function}
-multiplicative
-prime powers
\[\varphi (p^n) = p^n -p^{n-1}\]
\[\varphi (n^k) = n^{k-1} \varphi (n) \]
- euler product form
- number equals sum of euler phis for each divisor (see Group Theory)
- non coprime multiples in argument
\section{Jordan's totient function}
- Clash with Bessel function notation
\section{Carmichael function}

\begin{definition}
The \emph{Carmichael function} $\lambda : \mathbb{N} \to \mathbb{N} $ is the totient function returning the smallest power that all integers coprime to $n$ are congruent to $1 \mod n$.
	\[ \lambda (n) = \min \{ m : \forall a \in \{ a :\gcd(a,n)=1 \} [ a^m \equiv 1 \mod n ] \} \]
\end{definition}


- Carmichael numbers

\chapter{Multiplicative function}
\section{Möbius function}
$\mu$
- Möbius inversion formula
\section{Liouville function}
$\lambda$
- Clash with Carmichael function notation
\section{Partition function}
$p$
\section{Von Mangoldt function}
$\Lambda$

