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

\subsection{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.


As we will see, arithmetic functions are also extremely useful for studying integer sequences (as we will see with \emph{perfect numbers} and \emph{Carmichael numbers}), and can even constitute as interesting integer sequences themselves!

\begin{itemize}
	\item Encoding a sequences as arithmetic functions allows connections to be made between different sequences by making use of their shared or complementary function properties.
	\item It allows the use of methods of mathematical analysis to study number theory.
\end{itemize}

\subsection{Additivity and multiplicativity}

\begin{definition}[Additive function]
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 totally additive } \iff  f(ab)=f(a)+f(b)  \]
\end{definition}



\begin{definition}[Multiplicative function]
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) \]
\end{definition}


\subsection{Examples of familiar arithmetic functions}

Many functions that we are familiar with are indeed arithmetic functions; particularly the factorial, Euler phi function, and GCD and LCM functions.

$! : \mathbb{N} \to \mathbb{N}$

$\varphi : \mathbb{N} \to \mathbb{N}$


\section{Divisor functions}

Class of arithmetic functions that relate to divisors of its input.

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

As we prove results on divisor functions, we will rely heavily of the prime power representation ensured to be unique by FTA.

\subsection{Tau function}
The specific function $ \sigma_0 =\tau $ simply counts divisors.

\[ \sigma_0 (p) = 2 \]
\[ \sigma_0 (p^n) = n+1 \]
\begin{proposition}
\[n = \prod^{k}_{i=1}p_{i}^{\alpha_{i}}\]
\[\sigma_0 (n) =\prod_{i=1}^{k} (\alpha_i + 1)\]
\end{proposition}

\begin{corollary}
\[ \sigma_0 \text{ is multiplicative} \]
\end{corollary}


\[ \sigma_0 (n\#) = 2^n \]


Recall our previous use of FTA to count divisors; this can be applied to find a more explicit description of $\tau$.

\subsection{Higher order divisor function}
The function $\sigma_1 = \sigma$ is the sum of divisors.
\[ \sigma_1 (p) = p+1 \]
\[ \sigma_1 (p^n) = \sum^{n}_{k=0} p^{k} = \frac{p^{n+1}-1}{p-1} \]
\begin{proposition}
\[n = \prod^{k}_{i=1}p_{i}^{\alpha_{i}}\]
\[\sigma_1 (n) =\prod_{i=1}^{k} \frac{p^{\alpha_i +1}_{i}-1}{p_{i}-1}\]
\end{proposition}

Similarly, such a product representation can be used to demonstrate the function's multiplicity.
\begin{corollary}
\[ \sigma_1 \text{ is multiplicative} \]
\end{corollary}



- pentagonal number theorem
\subsection{Perfect numbers}




$\sigma_1$ is intimately related to the inteeger sequence of \emph{perfect numbers}.


First, we clarify the term proper divisor.
\begin{definition}
A \emph{proper divisor of $n$} is a divisor $n$ that isn't $n$.
\end{definition}

\begin{definition}
A \emph{perfect number} is an integer that equals the sum of its proper divisors.
\[n \text{ is perfect} \iff n= \sigma_1 (n) -n \]
\end{definition}

The multiplicative nature of $\sigma_1$ admits an elegant prood of the following.
\begin{theorem}[Euclid-Euler theorem]
\[ n \text{ is perfect} \iff n=2^{p-1}(2^{p}-1) \land 2^{p}-1 \text{ is prime}\]
\end{theorem}




\section{Totient functions}

The totient of a number is the count of numbers less than and coprime to that number. There have been many arithmetic functions related to this notion, however none as fundamental as Euler's.

\subsection{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)
\[n = \sum_{d\in \mathbb{N} : d|n} \varphi(d) \]
- non coprime multiples in argument
\subsection{Jordan's totient function}

There exists a generalization of Euler's totient function 
\[J_k (n) = n^k \prod_{p|n}(1- \frac{1}{p^k}) \]
Note that there is a clash of notation with Bessel function notation, howeve3 Beaswl functions almost never appear in number theory.

This function has combinatorial applications in finding the ordee of particular finite general linear groups.
\subsection{Carmichael function}

Ferma's little theorem is a curious result, and Euler's theorem is a powerful generalization. One may be tempted to ask however if $\varphi(n)$ is truly the smallest exponent such that $a^{\varphi(n)}\equiv 1 \mod n$ for any $a$ where $a,n$ are coprime. 

We define an arithmetic function to characterize this.

\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}

One can use basic group theory relating to cyclic groups to prove the following.
\begin{proposition}
	\[ \lambda (n) = \begin{cases} \varphi(n) & n \in \{ p^k : p \text{ is an odd prime } \land k \in \mathbb{N} \}\cup \{1,2,4\} \\ \frac{\varphi(n)}{2} & n=2^r,r\geq 3  \\ \mathrm{lcm}( \lambda(n_1), \hdots , \lambda(n_k)  ) & n=\prod^{k}_{i=1}n_i ,n_i \text{ are distinct prime powers} \end{cases} \]
\end{proposition}

Note that this first case of the Carmichael function is essentially when we have a primitive root!

Why should one care about the smallest exponent? Any exponent $m$ with $a^m\equiv 1 \mod n$  ($a,n$ coprime) divides $\lambda(n)$; this result doesn't necessarily hold for $\varphi(n)$.

It finds use in the study of Carmichael numbers and Korselt's theorem.

\begin{definition}
A \emph{Carmichael number} is a composite number that satisfies the following, where $\mathrm{gcd}(a,n)=1$.
\[ a^{n-1} \equiv 1\mod n\]
\[ n \text{ is a Carmichael number } \iff n \text{ is composite } \land \forall a \in \mathbb{N} [ \gcd(a,n) = 1, a^{n-1} \equiv 1 \mod n \]
\end{definition}

\begin{definition}
A number is square-free iff each prime divisor has a multiplicity of 1.
\[n \text{ is square-free } \iff n=\prod^{k}_{i=1}p_i \land p_i \text{are distinct primes}\]
\end{definition}

The following theorem gives an alternative characterization of Carmichael numbers, which relies on the minimal exponent given by the Carmichael function.
\begin{theorem}[Korselt's theorem]
	$n$ is a Carmichael number iff it is square-free, and for each prime divisor of $n$ (denoted $p$), $p-1$ divides $n-1$
	\[ n \text{ is a Carmichael number } \iff n=\prod_{i=1}^{k} p_i \land p_i\text{are distinct primes } \land p_i -1 | n-1 \]
\end{theorem}
Carmichael numbers with a factor $p^k$ have a factor $p$, so $a^{p-1}\equiv 1\mod p$ as well as $a^{n-1} \equiv 1 \mod p$. Since $p-1$ is the smallest value with such a property, $p-1|n-1$.
Carmichael numbers with factor $p^k$ need to obey $a^{\lambda(p^k)} \equiv a^{p^{k-1}(p-1)} \equiv 1\mod p^k$ as well as $a^{n-1} \equiv 1 \mod p^k$. $p^{k-1}(p-1) | n-1$. Since $p^{k-1}$ can't divide $n-1$ since $p^{k-1}$ divides $n$, $k=1$ so $n$ must be square free.


\section{Multiplicative function}
\subsection{Möbius function}

Appears in the fields of elemwntaryband analytic number theory with applications to combinatorics.

The arithmetic function is primarily of interest due to its role in the Möbius inversion formula.

$\mu$


\begin{definition}[Möbius function]
The \emph{Möbius function} is an arithmetic function $\mu : \mathbb{N} \to \{-1,-0,1\}$ defined in the following manner.
$\mu(n) = \begin{cases}  1 & n=1 \\ (-1)^k & n \text{ is the product of } k \text{ distinct primes} \\ 0 & n \text{ is divisible by a square number other than 1} \end{cases}$
\end{definition}

\subsection{Liouville function}
$\lambda$
- Clash with Carmichael function notation
\subsection{Partition function}
$p$
\subsection{Von Mangoldt function}

\begin{definition}[Von Mangoldt function]
The \emph{Von Mangoldt function} is an arithmetic function $\Lambda : \mathbb{N} \to \mathbb{R}$ defined in the following manner.
$\Lambda (n) = \begin{cases}  \ln (p) & n=p^k \land p \text{ is prime } \land k \geq 1& \text{otherwise} \\ 0 & \text{otherwise} \end{cases}$
\end{definition}

Since FTA ensures a unique prime power factorization, this arithmetic function is well defined.

\[ \sum_{ d \in \{ d' \in \mathbb{N} : d' | n \} } =\sum_{d|n} \]

\begin{proposition}
	\[\ln (n) = \sum_{d | n } \Lambda(d)\]
\end{proposition}



\section{Dirichlet convolution}