\documentclass{article} % Bringing in some standard packages with standard commands \usepackage{amsmath, amsthm,amssymb, amsfonts, stmaryrd} % Setting the margin size \usepackage[margin=1in]{geometry} % Defining different theorem environments that we will use \theoremstyle{break} \newtheorem{thm}{Theorem}[section] \newtheorem{prop}[thm]{Proposition} \newtheorem{cor}[thm]{Corollary} \newtheorem{lemma}[thm]{Lemma} \newtheorem{fact}[thm]{Fact} \newtheorem{conj}[thm]{Conjecture} \newtheorem{exercise}[thm]{Exercise} \theoremstyle{definition} \newtheorem{example}[thm]{Example} \newtheorem{dfn}[thm]{Definition} \newtheorem{question}[thm]{Question} \theoremstyle{remark} \newtheorem{rmk}[thm]{Remark} %Giving author data \title{ Multiplicative Functions and Summatory Functions} \author{Jay Daigle\\ Occidental College} \date{} \begin{document} \maketitle \begin{abstract} Much of number theory attemps to understand the multiplicative structure of the natural numbers and the prime numbers. Multiplicative functions, which commute with multiplication of relatively prime integers, are often useful to tease apart these relationships. In this paper we will define multiplicative functions, discuss their relationship with summatory functions, and look at a few examples that have interesting number-theoretic consequences. \end{abstract} \section{Multiplicative Functions} \label{sec:mult-funct} \nocite{DaigleNTlectures} The material in this section follows \cite{rosen2011elementary} section 7.1 and \cite{stein2008elementary} section 2.2. \begin{dfn} An \emph{arithmetic function} is a function defined for all natural numbers. A function is \emph{multiplicative} if it has the property that $f(mn) = f(m) f(n)$ whenever $(m,n) = 1$. It is \emph{completely multiplicative} if $f(mn) = f(m) f(n)$ for all natural numbers $m,n$. \end{dfn} \begin{example} The functions $f(n) = 1$ and $g(n) = n$ are completely multiplicative. We will see that $\phi(n)$ is multiplicative but not completely multiplicative. (Example: $\phi(4) = 2 \neq 1 \cdot 1 = \phi(2) \cdot \phi(2)$). \end{example} Completely multiplicative functions are easy to understand, but we can get a good grasp even of regularly multiplicative functions. \begin{prop} \label{prop:3} If $f$ is multiplicative and $n = p_1^{a_1} p_2^{a_2} \dots p_s^{a_s} = \prod_{i=1}^s p_i^{a_i}$ is the prime factorization of $n$, then $f(n) = f(p_1^{a_1}) f(p_2^{a_2}) \dots f(p_s^{a_s}) = \prod_{i=1}^s f(p_i^{a_i}).$ \end{prop} \begin{proof} We prove by induction on $s$, the number of distinct prime factors of $n$. If $s=1$ then $n = p_1^{a_1}$ and then $f(n) = f(p_1^{a_1})$ is trivially true. Suppose the proposition is true for all integers with $k$ distinct prime factors, and suppose $n$ has $k+1$ distinct prime factors, say $n = \prod_{i=1}^{k+1} p_i^{a_i}$. We observe that $\left( \prod_{i=1}^k p_i^{a_i}, p_{k+1}^{a_{k+1}} \right) = 1$, and thus by definition of a multiplicative function we know that $f \left( \prod_{i=1}^{k+1} p_i^{a_i} \right) = f \left(\prod_{i=1}^k p_i^{a_i} \right) f( p_{k+1}^{a_{k+1}}).$ And by inductive hypothesis we know that $f \left( \prod_{i=1}^{k} p_i^{a_i} \right) = \prod_{i=1}^{k} f(p_i^{a_i})$ and thus we have $f \left( \prod_{i=1}^{k+1} p_i^{a_i} \right) = \prod_{i=1}^{k} f(p_i^{a_i}) f(p_{k+1}^{a_{k+1}}) = \prod_{i=1}^{k+1} f(p_i^{a_i}).$ \end{proof} Thus for any multiplicative function, if we can compute its value for prime powers, we can easily compute its value for any number. \subsection{The Euler $\phi$-function} \label{sec:euler-phi-function} The material in this section follows \cite{rosen2011elementary} section 7.1 and \cite{stein2008elementary} section 2.2. We want to understand the Euler $\phi$-function much better. We will prove that it is a multiplicative function (though, as we observed earlier, it is not completely multiplicative). After that we'll figure out how to compute $\phi$ of prime powers, which will allow us to easily compute $\phi(n)$ for any positive integer $n$. \begin{prop} Let $m,n$ be relative prime natural numbers. Then $\phi(mn) = \phi(m) \phi(n)$. In other words, the function $\phi(n)$ is multiplicative. \end{prop} \begin{proof} Write the numbers $\leq mn$ as follows: $\begin{array}[h!]{ccccc} 1 & m+1 & 2m+1 & \dots & (n-1)m+1 \\ 2 & m+2 & 2m+2 & \dots & (n-1)m+2 \\ 3 & m+3 & 2m+3 & \dots & (n-1)m+3 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ r & m+r & 2m+r & \dots & (n-1)m+r \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ m & 2m & 3m & \dots & nm \\ \end{array}$ Note that $(km + r, m) = (r,m)$, thus the first element of a given row is relatively prime to $m$ if and only if \emph{every} element of that row is. Since $(r,m) > 1$ implies that $(r,mn) > 1$, we only need to consider elements in rows $r$ where $(r,m) = 1$. There are, of course, $\phi(m)$ such rows. Now suppose $(r,m) = 1$ and consider the elements of this row, which are $km+r$ for $0 \leq k \leq n-1$. We claim this is a complete system of residues modulo $n$. It's enough to prove that no two elements are congruent to each other, by HW 4 problem 2. But if $im+r \equiv jm +r \mod n$ then $n | m(i-j)$, and since $(n,m) = 1$, by Euclid's lemma this implies $n | i-j$. But $i,j < n$, so $i=j$. Since this is a complete system of residues, exactly $\phi(n)$ of these integers are relatively prime to $n$. Since these integers are also relatively prime to $m$, they are relatively prime to $mn$. Thus there are $\phi(m)$ rows that contain any elements relatively prime to $mn$; each such row contains $\phi(n)$ such elements. Thus there are in total $\phi(m) \phi(n)$ natural numbers relatively prime to $mn$ and $\leq mn$; but this is the definition of $\phi(mn)$. \end{proof} Now that we know $\phi(n)$ is a multiplicative function, we know we can compute it purely by computing its value at prime powers. So we turn our attention to computing $\phi(p^k)$. First, recall from homework that $\phi(n) = n-1$ if and only if $n$ is prime. \begin{lemma} \label{lemma:8} Let $p$ be a prime number, and let $k$ be a positive integer. Then $\phi(p^k) = p^k - p^{k-1}$. \end{lemma} \begin{proof} An integer is relatively prime to $p^k$ if and only if it is divisible by $p$. Thus the integers $n \leq p^k$ which are \emph{not} relatively prime to $p^k$ are the integers $\ell p$ for $1 \leq \ell \leq p^{k-1}$. There are of course $p^{k-1}$ such integers, and there are $p^k$ total integers $n \leq p^k$; thus there are $p^k - p^{k-1}$ integers $n \leq p^k$ such that $(n,p^k) = 1$. \end{proof} \begin{example} $\phi(2^{10}) = 2^{10} - 2^9 = 1024 - 512 = 512.$ $\phi(7^3) = 7^3 - 7^2 = 343 - 49 = 298$. \end{example} \begin{thm} \label{thm:4} Let $n = \prod_{i=1}^k p_i^{a_i}$ be the prime factorization of a natural number. Then $\phi(n) = n \left(1 - \frac{1}{p_1} \right) \left( 1 - \frac{1}{p_2} \right) \dots \left( 1 - \frac{1}{p_k} \right) = n \prod_{i=1}^k \left( 1 - \frac{1}{p_i} \right).$ \end{thm} \begin{proof} By proposition \ref{prop:3}, we know that $\phi(n) = \prod_{i=1}^k \phi(p_i^{a_i}).$ But by lemma \ref{lemma:8} we know that $\phi(p_i^{a_i}) = p_i^{a_i} - p_i^{a_i - 1} = p_i^{a_i} \left( 1 - \frac{1}{p_i} \right).$ Thus \begin{align*} \phi(n) &= \prod_{i=1}^k \phi(p_i^{a_i}) = \prod_{i=1}^k p_i^{a_i} \left( 1 - \frac{1}{p_i} \right) \\ & = \left( \prod_{i=1}^k p_i^{a_i} \right) \left( \prod_{i=1}^k \left( 1 - \frac{1}{p_i} \right) \right) \\ & = n \prod_{i=1}^k \left( 1 - \frac{1}{p_i} \right) . \end{align*} \end{proof} \begin{example} $\phi(100) = \phi(2^2 \cdot 5^2) = 100 ( 1 - 1/2) (1 - 1/5) = 100 \cdot \frac{1}{2} \cdot \frac{4}{5} = 40.$ $\phi(360) = \phi(2^3 \cdot 3^2 \cdot 5) = 360 (1-1/2) (1-1/3)(1-1/5) = 360 \frac{8}{30} = 96.$ \end{example} \begin{cor} If $n > 2$ then $\phi(n)$ is even. \end{cor} \begin{proof} Let $n = \prod_{i=1}^k p_i^{a_i}$. Then $\phi(n) = \prod_{i=1}^k \phi(p_i^{a_i}).$ Suppose $n$ has an odd prime factor $p_k$. Then since $p_k^{a_k}$ and $p_k^{a_k -1}$ are both odd, $2 | p_k^{a_k} - p_k^{a_k -1} = \phi(p_k) | \phi(n)$. Now suppose $n$ has no odd prime factors. Then $n = 2^r$ and $r > 1$. Then $\phi(n) = 2^r - 2^{r-1} = 2^{r-1}$ is even. \end{proof} This opens up an additional question: given an integer $m$, for what $n$ is $\phi(n) = m$? \begin{example} What are the solutions to the equation $\phi(n) = 8$? Suppose $n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$. Then we have the equation $\phi(n) = \prod_{j=1}^k p_j^{a_j-1} (p_j - 1)$ which is just a restatement of theorem \ref{thm:4}. Then the only primes that can divide $n$ are 2, 3, and 5, since we know that $p_i-1 | n$. Further, if $a_i > 1$ then $p_i | n$, so we know that 3 and 5 can each divide $n$ at most once. Thus we have $n = 2^{a_2} 3^{a_3} 5^{a_5}$, and $a_3,a_5$ are either 0 or 1. Suppose $a_3=a_5 = 0$ so that $n = 2^{a_2}$. Then $\phi(n) = \phi(2^{a_2}) = 2^{a_2-1}(2-1)$, which impiles that $a_2 = 4, n = 16$. Suppose $a_3 = 1,a_5 = 0$, so that $n = 2^{a_2} \cdot 3$. Then $\phi(n) = \phi(2^{a_2} \cdot 3) = 2^{a_2-1} (2-1) 3^0(3-1) = 2^{a_2}$. This implies that $a_2 = 3, n = 8 \cdot 3 = 24$. Suppose $a_3 = 0,a_5 = 1$, so that $n = 2^{a_2} \cdot 5$. Then $\phi(n) = \phi(2^{a_2} \cdot 5) = 2^{a_2-1} (2-1) 5^0(5-1) = 2^{a_2+1}$. This implies that $a_2 = 2, n = 4 \cdot 5 = 20$. Suppose $a_3 = 1,a_5 = 1$, so that $n = 2^{a_2} \cdot 3 \cdot 5$. If $a_2 > 0$ then $\phi(n) = \phi(2^{a_2} \cdot 3 \cdot 5) = 2^{a_2-1} (2-1) 3^0(3-1) 5^0 (5-1) = 2^{a_2+2}$. This implies that $a_2 = 1, n = 2 \cdot 3 \cdot 5 = 30$. If $a_2 = 0$ then instead $\phi(n) = \phi(3\cdot 5) = 2 \cdot 4 = 8$ does in fact work, so $n = 15$. Thus the possibilities are $n= 15,16,20,24,30$. \end{example} \subsection{Summatory functions} \label{sec:summatory-functions} The material in this section follows \cite{rosen2011elementary} section 7.2 and \cite{shoup2009computational} section 2.9. In this section we'll discuss another class of multiplicative functions, known as summatory functions. Though these do not look like they should be multiplicative, they often are. \begin{dfn} If $f$ is an arithmetic function, we define the \emph{summatory function of $f$} to be $F(n) = \sum_{d | n} f(d)$ where the sum is over all numbers $d$ which divide $n$. \end{dfn} \begin{dfn} We define the \emph{number of divisors function} $\tau(n)$ to be the number of natural numbers $\leq n$ which divide $n$. We can write $\tau(n) = \sum_{d |n}1$ so $\tau$ is a summatory function. We define the \emph{sum of divisors function} $\sigma(n) = \sum_{d|n} d$ to be the sum of the divisors of $n$. From the definition we see that $\sigma$ is also a summatory function. \end{dfn} \begin{prop} \label{prop:4} If $f$ is a multiplicative function, then the summatory function of $f$, $F(n) = \sum_{d |n} f(d)$, is also multiplicative. \end{prop} This result seems quite surprising at first, since addition and multiplication don't always play well together. Our basic strategy is to write each divisor of $mn$ as a divisor of $m$ times a divisor of $n$--and this is unique since $m$ and $n$ share no common factors. Thus we can split our sum of divisors of $mn$ into a product of sums of divisors of $m$ and sums of divisors of $n$. \begin{proof} Suppose $(m,n) = 1$. We wish to prove that $F(mn) = F(m)F(n)$. We know that $F(mn) = \sum_{d | mn} f(d)$. We can write any factor of $mn$ uniquely as a product of a factor $d_1$ of $m$, and a factor $d_2$ of $n$, and we have $(d_1,d_2) = 1$. Thus we have $F(mn) = \sum_{d | mn} f(d) = \sum_{d_1|m, d_2|n} f(d_1 d_2) = \sum_{d_1 |m, d_2|n} f(d_1) f(d_2).$ But this sum factors, since we can write \begin{align*} \sum_{d_1 |m, d_2|n} f(d_1) f(d_2) &= \sum_{d_1 |m} \sum_{d_2 |n} f(d_1) f(d_2) = \sum_{d_1 |m} \left( f(d_1) \sum_{d_2 |n} f(d_2) \right)\\ &= \left( \sum_{d_1|m} f(d_1) \right) \left( \sum_{d_2 |n} f(d_2) \right) = F(m) F(n). \end{align*} \end{proof} \begin{cor} $\sigma(n)$ and $\tau(n)$ are multiplicative functions. \end{cor} \begin{lemma} Let $p$ be prime and $a \in \mathbb{N}$. Then $\tau(p^a) = a +1$ and $\sigma(p^a) = 1 + p + p^2 + \dots + p^a = \frac{p^{a+1}-1}{p-1}.$ \end{lemma} \begin{proof} The divisors of $p^a$ are $1,p,p^2, \dots, p^a$. Thus there are $a+1$ and the result for $\tau$ follows. The first formula for $\sigma$ also follows; the second comes from the geometric series formula, or from the difference of $a+1$st powers formula. \end{proof} \begin{cor} Let $n = \prod_{i=1}^k p_i^{a_i}$. Then \begin{align*} \sigma(n) & = \prod_{i=1}^k \frac{p_i^{a_i+1} -1}{p_i -1}\\ \tau(n) & \prod_{i=1}^k (a_i + 1). \end{align*} \end{cor} \begin{thm} Let $n$ be a positive integer. Then $\sum_{d |n} \phi(d) = n$. That is, the summatory function of the Euler $\phi$-function is the identity function. \end{thm} \begin{proof} We're going to turn this into a counting/combinatorial argument. We're going to divide the integers $\leq n$ into classes $C_d$, where each class will contain exactly one number $d$ which divides $n$, and the class will have $\phi(n/d)$ elements. Thus $\sum_{d | n} \phi(n/d) = \sum_{d|n} \#C_d$, and the latter sum must be $n$ since it sums the sizes of a collection of sets whose union is $\{1,\dots, n\}$. Say the integer $m$ is in the class $C_d$ if $1 \leq m \leq n$ and $(m,n) = d$. We see that $m|n$ if and only if $(m,n) = m$, so $C_d$ contains exactly one element, $d$, which divides $n$. Further, we see that $m \in C_d$ if and only if $(m,n) =d$, which happens if and only if $(m/d,n/d) = 1$. Thus the number of integers in $C_d$ is the number of integers $\leq n/d$ which are relatively prime to $n/d$--that is, the size of $C_d$ is $\phi(n/d)$. And this proves what we wanted. \end{proof} \subsection{Perfect Numbers and Mersenne Primes} \label{sec:perf-numb-mers} The material in this section follows \cite{rosen2011elementary} section 7.3. \begin{dfn} We say a positive integer $n$ is a \emph{perfect number} if $\sigma(n) = 2n$. \end{dfn} \begin{example} Famously 6 is perfect, since $\sigma(6) = 1+2+3+6 = 12$. 28 is perfect since $\sigma(28) = 1+2+4+7+14+28 = 56$. \end{example} \begin{thm} The positive even integer $n$ is perfect if and only if $n=2^{m-1} (2^m-1)$ where $m \geq 2$ and $2^m-1$ is prime. \end{thm} \begin{proof} First we show that if $2^m-1$ is prime then $n = 2^{m-1} (2^m - 1)$ is perfect. Because $\sigma$ is multiplicative and we have a formula for it, we have \begin{align*} \sigma(n) & = \sigma( 2^{m-1} (2^m-1) ) = \sigma(2^{m-1}) \sigma(2^m -1) \\ & = \frac{2^m -1}{2-1} \cdot (1 + 2^{m}-1) = (2^m-1) 2^m = 2n. \end{align*} Now we want to show that if $\sigma(n) = 2n$ and $n$ is even, then $n = 2^{m-1} (2^m-1)$ for some $m$. So write $n = 2^s t$ where $t$ is odd. Then \begin{align*} \sigma(n) &= \sigma(2^s) \sigma(t) = \frac{2^{s+1}-1}{2-1} \cdot \sigma(t) = (2^{s+1} - 1) \sigma(t). \end{align*} But since $n$ is perfect, we know $\sigma(n) = 2n = 2^{s+1} t$ and thus we have \begin{align*} 2^{s+1} t & = (2^{s+1} - 1) \sigma(t) \end{align*} and thus $2^{s+1}$ divides $(2^{s+1} -1) \sigma(t)$. But we can see that $(2^{s+1}, 2^{s+1}-1) = 1$, so by Euclid's Lemma $2^{s+1} | \sigma(t)$. So let $\sigma(t) = 2^{s+1} q$ for some integer $q$, and we have \begin{align*} 2^{s+1} t &= (2^{s+1} -1) 2^{s+1} q \\ t & = (2^{s+1} -1) q = 2^{s+1}q - q. \end{align*} Thus $q |t$ and $q \neq t$. Adding $q$ to both sides gives $t+q = 2^{s+1} q = \sigma(t)$. But if $q>1$ then, since $q | t$ and $q \neq t$, we have (at least) three distinct positive divisors of $t$: $1,q$, and $t$. Thus $1 + q + t \leq \sigma(t) = q +t$ which is a contradiction. Thus $q = 1$, and $\sigma(t) = t+1$. But if $\sigma(t) = t+1$ this implies the only positive factors of $t$ are $1$ and $t$, and thus by definition $t$ is prime. Further $t = (2^{s+1}-1)q = 2^{s+1} - 1$. \end{proof} Thus to find all (even) perfect numbers, we just need to find primes of the form $2^m-1$. This brings us to a famous old category of primes, called the Mersenne primes. \begin{dfn} If $m \in \mathbb{N}$, then $M_m = 2^m-1$ is called the \emph{$m$th Mersenne number}. If $M_m$ is prime, it is called a Mersenne prime. \end{dfn} \begin{prop} If $m \in \mathbb{N}$ and $M_m = 2^m-1$ is prime, then $m$ is prime. \end{prop} Suppose $m = ab$ for $1 < a,b < m$. Then $2^m -1 = 2^{ab} -1 = (2^a-1)(1 + 2^a + 2^{2a} + \dots + 2^{(b-2)a} + 2^{(b-1)a} ).$ Since $a,b> 1$, both of these factors are $>1$, so $2^m - 1$ is not prime, which is a contradiction. \begin{rmk} Note that it is \emph{not} true that if $p$ is prime, then $M_p$ is as well. The smallest pernicious Mersenne number''--that is, $M_p$ where $p$ is prime but $M_p$ is not-- is $M_{11} = 2^{11} - 1 = 2047$, which we have discussed in class before. Mersenne primes provide a relatively easy way to find large primes; the largest known prime is $2^{74,207,281}-1$, which is a Mersenne prime. The GIMPS (Great Internet Mersenne Prime Search) is a large distributed computing project to test larger candidate Mersenne primes. It was for a long time inaccurately believed that $M_{67}$ was prime (after Marin Mersenne wrongly included it on his list of Mersenne primes in the 17th century; he also wrongly included $M_{257}$ and excluded $M_{61}, M_{89},$ and $M_{107}$. Edouard Lucas showed in 1876 that $M_{67}$ was composite, but did not find a factor. In 1903, Frank Nelson Cole gave a completely silent talk'' in which he computed $2^{67} - 1$ and $193,707,721 \times 761,838,257,287$ on the blackboard and got the same number both ways (a result which he said took him three years of Sundays'' to find). He returned to his seat without speaking, to applause from the audience. \end{rmk} Though $M_p$ is not always prime for $p$ prime, we have a number of theorems that will help us decide of $M_p$ is in fact prime. \begin{thm} \label{thm:5} If $p$ is an odd prime, then any divisor of $M_p = 2^p-1$ is of the form $2kp + 1$ where $k \in \mathbb{N}$. \end{thm} \begin{proof} Let $q$ be a prime dividing $M_p = 2^p -1$. By Fermat's little theorem we know that $2^{q-1} \equiv 1 \mod q$ and thus $q | 2^{q-1} -1$. We can compute that $(2^p-1, 2^{q-1}-1) = 2^{(p,q-1)} -1$. But since $q | 2^p-1, 2^{q-1} -1$, we know that $q | 2^{(p,q-1)} -1$ and thus $(p,q-1) > 1$. But $p$ is prime, so $(p,q-1) = p$. Thus $p | q-1$ so there is a natural number $m$ such that $mp = q-1$. Since $q,p$ are odd, we know that $m$ is even, so write $m = 2k$ for $k \in \mathbb{N}$. Thus $q = 2kp + 1$, and any prime divisor of $M_p$ has the form $2kp + 1$. But the product of two numbers of this form is still a number of this form, and any divisor of $M_p$ is the product of prime divisors, so any divisor has the form $2kp + 1$. \end{proof} \begin{cor} There are infinitely many primes. \end{cor} \begin{proof} Suppose there are finitely many primes, and let $p$ be the largest. Then $M_p > p$ is not prime, and it has some prime factor. But by theorem \ref{thm:5}, the prime factor must have the form $2kp+1 > p$, which is a contradiction. \end{proof} \begin{example} Let us decide whether $M_{13}=2^{13} -1 = 8191$ is prime. We only need to check for factors less than $\sqrt{8191} \approx 90$. Further, any factor must have the form $2\cdot k \cdot 13 + = 26k+1$, so we just have to check $27, 53, 79$. 27 isn't prime so we just need to check $53$ and $79$. But $8191/53 = 154.547$ and $8191/79 =103.684$. Thus $M_{13}$ must be prime. Now let's decide if $M_{23} = 2^{23}-1 = 8,388,607$ is prime. We only need to check primes of the form $46k+1$. The first of these is 47, and we see $8,388,607/47=178,481$. Thus $M_{23}$ is not prime. \end{example} \begin{rmk} There is a more efficient test to determine whether a Mersenne number is prime, called the \emph{Lucas-Lehmer Test}. This could make a good paper topic for someone familiar with group theory. \end{rmk} Two last comments on this topic: first, all our work on Mersenne primes was specific to the base 2. We can't actually extend this work to other bases. Or rather, we can, but it's very brief. \begin{exercise} Suppose $a^p -1$ is prime. Then either $a \leq 2$ or $p=1$. \end{exercise} Second, we've only addressed even perfect numbers. It's actually an open question whether odd perfect numbers exist, and commonly conjectured that they do not. We do know a large number of conditions that odd perfet numbers must satisfy: \begin{fact} Suppose $N$ is an odd perfect number. Then \begin{itemize} \item $N$ is not divisible by 105 \item $N$ satisfies one of $N \equiv 1 \mod 12$, $N \equiv 117 \mod 468$, or $N \equiv 81 \mod 324$ \item $N = q^a p_1^{2e_1} \dots p_k^{2e_k}$ where \begin{itemize} \item $q,p_1,\dots,p_k$ are distinct primes \item $q \equiv a \equiv 1 \mod 4$ \item The smallest prime factor of $N$ is less than $(2k+8)/3$ \item Either $q^a > 10^{62}$, or $p_j^{2e_j} > 10^{62}$ for some $j$ \item $N < 2^{4^{k+1}}$ \end{itemize} \item The largest prime factor of $N$ is greater than $10^8$, the second largest prime factor is greater than $10^4$, and the third largest is greater than 100 \item $N$ has at least 101 prime factors and at least 10 distinct prime factors, and if $3 {\not | N}$ then $N$ has at least 12 distincct prime factors. \item $N > 10^{1500}$ \end{itemize} \end{fact} This list of restrictions is sufficiently long that James Joseph Sylvester commented in 1888 that: ...a prolonged meditation on the subject has satisfied me that the existence of any one such [odd perfect number] -- its escape, so to say, from the complex web of conditions which hem it in on all sides -- would be little short of a miracle.'' \subsection{Mobius Inversion} \label{sec:mobius-inversion} The material in this section follows \cite{rosen2011elementary} section 7.4. We earlier discussed summatory functions, where we write $F(n) = \sum_{d |n} f(n)$ for some function $f$; we proved that if $f$ is multiplicative, then so is $F$. In this section we'd like to reverse the summatory function process. That is, if we have $F(n)$ can we use that to compute $f(n)$? Well, we'll start by exploring. We notice that \begin{align*} F(1) &= f(1)\\ F(2) &= f(1) + f(2) \\ F(3) & = f(1) + f(3) \\ F(4) & = f(1) + f(2) + f(4) \\ F(5) & = f(1) + f(5) \\ F(6) & = f(1) + f(2) + f(3) + f(6) \end{align*} and thus \begin{align*} f(1) & = F(1) \\ f(2) & = F(2) - f(1) = F(2) - F(1) \\ f(3) & = F(3) - f(1) = F(3) - F(1) \\ f(4) & = F(4) - f(2) - f(1) = F(4) - (F(2) - F(1)) - F(1) \\ & = F(4) - F(2) \\ f(5) & = F(5) - f(1) = F(5) - F(1) \\ f(6) & = F(6) - f(3) - f(2) - f(1) = F(6) - (F(3) - F(1)) - (F(2) - F(1)) - F(1) \\ & = F(6) -F(3) - F(2) + F(1). \end{align*} We might notice that we seem to always be able to write $f(n)$ as a sum of $\pm F(n/d)$ for $d|n$. So we might hope we can find an arithmetic function $\mu$ that gives a formula $f(n) = \sum_{d |n} \mu(d) F(n/d).$ Let's figure out what this function would have to look like. $f(1) = F(1)$ so $\mu(1) = 1$. If $p$ is a prime, then $F(p) = f(1) + f(p)$ so $f(p) = F(p) - F(1)$. Thus we must have $\mu(p) = -1$. (Recall that we have $\mu(d)F(n/d)$ so $\mu(p)$ is the coefficient of $F(1)$). By the same logic, we see that $F(p^2) = f(1) + f(p) + f(p^2)$ so $f(p^2) = F(p^2) - F(p)$. Thus if $\mu(1) = 1$ and $\mu(p) = -1$, we have $\mu(p^2) = 0$. We can follow the same argument to show that $\mu(p^k) = 0$ for every $k > 1$. If we assume that $\mu$ is multiplicative, this completely nails down the values of $\mu$ at every number, since we can compute'' it at any prime power. This leads us to the following definition: \begin{dfn} We define the \emph{M\"obius function} $\mu(n)$ by $\mu(n) = \left\{ \begin{array}[h]{cc} 1 & n = 1 \\ (-1)^r & n = p_1 p_2 \dots p_r \text{ are distinct primes} \\ 0 & \text{otherwise} % p^2 | n \text{ for some prime } p \end{array} \right.$ In particular, if $p^2 |n$ for any prime $p$ then $\mu(n) = 0$. $\mu(n) \neq 0$ if and only if $n$ is \emph{square-free}. \end{dfn} \begin{rmk} If we think of 1 as the empty product, then we don't need to define $\mu(1)$ separately, since $1 = \prod_{k=1}^0 p_i$ and then $\mu(1) = (-1)^0$. \end{rmk} \begin{example} \begin{align*} \mu(1) & = 1 & \mu(4) & = 0 \\ \mu(2) & = -1 & \mu(5) & = -1 \\ \mu(3) & = -1 & \mu(6) & = 1. \end{align*} We can compute that \begin{align*} \mu(330) &= \mu(2 \cdot 3 \cdot 5 \cdot 11) =(-1)^4 = 1 \\ \mu(660) &= \mu(2^2 \cdot 3 \cdot 5 \cdot 11) = 0 \\ \mu(2310) & = \mu( 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11) = (-1)^5 = -1. \end{align*} \end{example} \begin{lemma} The M\"obius function $\mu(n)$ is multiplicative. \end{lemma} \begin{proof} Suppose $m,n$ are relatively prime positive integers. We want to show that $\mu(mn) = \mu(m) \mu(n)$. We need to check this case-by-case. If $m = 1$ then $\mu(m) = 1$, so $\mu(mn) = \mu(n) = \mu(m) \mu(n)$. Similarly if $n = 1$ then $\mu(mn) = \mu(m) = \mu(m) \mu(n)$. If $m$ is divisible by a square of a prime, then so is $mn$, so $\mu(mn) = 0 = 0 \cdot \mu(n) = \mu(m) \mu(n)$. Similarly, if $n$ is divisible by a square of a prime, then so is $mn$, so $\mu(mn) = 0 = \mu(m) \cdot 0 = \mu(m) \mu(n)$. Finally, suppose $m,n \neq 1$ and neither is divisible by a square of a prime. Then we we can write $m = p_1 \dots p_k$ and $n= q_1, \dots, q_\ell$ where the $p_i$ and the $q_i$ are all distinct. Then we have $\mu(m) = (-1)^k, \mu(n) = (-1)^\ell$. We also have $mn = p_1 \dots p_k q_1 \dots q_\ell$ all distinct factors, so $\mu(mn) = (-1)^{k+\ell} = (-1)^k (-1)^\ell = \mu(m) \mu(n)$. \end{proof} \begin{rmk} The M\"obius function is not completely multiplicative, since $\mu(2) = -1$ but $\mu(4) = 0$. \end{rmk} Since we have a multiplicative function, the next step is to study its summatory function. Fortunately, the M\"obius function has a particularly simple summatory function: \begin{lemma} The summatory function of the M\"obius function satisfies the formula $F(n) = \sum_{d |n} \mu(d) = \left\{ \begin{array}[h]{cc} 1 & n=1 \\ 0 & n > 1. \end{array} \right.$ \end{lemma} \begin{proof} When $n=1$, we have $F(1) = \sum_{d |1} \mu(d) = \mu(1) =1.$ Now suppose $n > 1$. We know that $F$ is multiplicative, so we just need to evaluate it at prime powers. But \begin{align*} F(p^k) &= \sum_{d | p^k} \mu(d) = \mu(1) + \mu(p) + \dots + \mu(p^k)\\ & = 1 -1 + 0 + 0 + \dots + 0 =0 \end{align*} as long as $k > 0$. Suppose $n = p_1^{a_1} \dots p_k^{a_k}$. Then $F(n) = \prod_{i=1}^k F(p_i^{a_i}) = \prod_{i=1}^k 0 = 0.$ \end{proof} So far we've studied some properties of our M\"obius function, but we haven't actually proven that it does the thing we want it to do. Recall we were hoping to find an inversion formula'' that allows us to recapture a function from its summative function. If such a function exists and is multiplicative, it must be the M\"obius function; but now we're ready to prove that the M\"obius function does in fact have this property. \begin{thm}[M\"obius Invrsion Formula] Suppose $f$ is an arithmetic function (which need not be multiplicative!), and $F$ is the summatory function of $f$, given by $F(n) = \sum_{d|n} f(d).$ Then, for any natural number $n$, we have $f(n) = \sum_{d |n} \mu(d) F(n/d).$ \end{thm} \begin{proof} The proof of this is a fairly straightforward exercise in manipulation of sums, but we must be careful of our indices. Fix an integer $n$. We have \begin{align*} \sum_{d |n} \mu(d) F(n/d) & = \sum_{d |n} \left( \mu(d) \sum_{e | (n/d)} f(e) \right) \\ & = \sum_{d |n} \sum_{e | (n/d)} \mu(d) f(e). \end{align*} Now we think about the indices. We're summing over all pairs of integers $d,e$ such that $d|n$ and $e | n/d$. But this is the same as summing over all pairs of integers $d,e$ such that $e|n$ and $d| (n/e)$. (Suppose $d|n$ and $em = n/d$. Then $emd = n$ so $e|n$, and $md = n/e$ so $d | n/e$. We can do the same argument in the opposite direction). Thus we have \begin{align*} \sum_{d |n} \sum_{e | (n/d)} \mu(d) f(e) & = \sum_{e|n} \sum_{d | (n/e)} \mu(d) f(e) \\ & = \sum_{e|n} f(e) \left( \sum_{d|(n/e)} \mu(d) \right). \end{align*} But recall that $\sum_{d | (n/e)} \mu(d) = 0$ unless $n/e =1$, which happens precisely when $e = n$, and in this case the sum is equal to 1. So every term of this sum is 0 except the term corresponding to $e = n$, which gives us $\sum_{e|n} f(e) \sum_{d|(n/e)} \mu(d) = f(e) \cdot 1 = f(e).$ \end{proof} This is all an example of a process called \emph{Dirichlet convolution}, which you will see more about on the homework. \begin{cor} If $n$ is a natural number, we have \begin{align*} n &= \sum_{d |n} \mu(d) \sigma(n/d) = \sum_{d|n} \mu(n/d) \sigma(d) \\ 1 & = \sum_{d |n} \mu(d) \tau(n/d) = \sum_{d |n} \mu(n/d) \tau(d). \end{align*} \end{cor} \begin{cor} Let $f$ be an arithmetic function and $F(n) = \sum_{d |n} f(n)$ be the summatory function of $f$. If $F$ is multiplicative, then so is $f$. \end{cor} \begin{rmk} Notice this is the converse of proposition \ref{prop:4}, which said that if $f$ is multiplicative, then so is its summatory function. \end{rmk} \begin{proof} Suppose $m,n$ are relatively prime natural numbers. We want to show that $f(mn) = f(m) f(n)$. First recall that if $d | mn$ then we can uniquely write $d = d_1 d_2$ with $d_1 | m, d_2|n$ (since $m,n$ share no factors in common), and $(d_1,d_2) = 1$. Then \begin{align*} f(mn) & = \sum_{d | mn} \mu(d) F \left(\frac{mn}{d} \right) \\ & = \sum_{d_1 | m, d_2 |n} \mu(d_1 d_2) F\left(\frac{mn}{d_1 d_2} \right) \\ & = \sum_{d_1 | m, d_2 | n} \mu(d_1) \mu(d_2) F \left( \frac{m}{d_1} \right) \left( \frac{n}{d_2} \right) \\ & = \left( \sum_{d_1 | m} \mu(d_1) F(m/d_1) \right) \left( \sum_{d_2 | n} \mu(d_2) F(n/d_2) \right) \\ & = f(m) f(n). \end{align*} \end{proof} \nocite{pommersheim2010number} \bibliographystyle{amsalpha} \bibliography{sample} \end{document}