\documentclass[12pt,letterpaper]{book} \usepackage{times} \usepackage{amsthm} \usepackage{makeidx} \usepackage{amsmath} \usepackage{amssymb} \usepackage{mathrsfs} \usepackage{amsfonts} \usepackage{hyperref} \newcommand{\comment}[1]{} \newtheorem{definition}{Definition} \newtheorem{claim}{Claim} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{cor}{Corollary} \newtheorem{def1}{Definition} \newtheorem{Def}{Definition} \newtheorem{prop}{Proposition} \newtheorem{remark}{Remark} \newtheorem{notation}{Notation} \newtheorem{example}{Example} \newtheorem{conjecture}{Conjecture} \newtheorem{examples}{Examples} \renewcommand{\chaptername}% {Lecture} \linespread{1.3} \title{Lecture notes "Analytic Number Theory"} \author{Dr. Mohib Ali} \date{} \makeindex \begin{document} \maketitle \begin{center}\textbf{Preface} \end{center} These notes are prepared for the course taught at Virtual Campus of COMSATS IIT. The chapters are distributed according to the contents of video lectures delivered. As discussed in the the first video lecture the main texts for this course are following \begin{itemize} \item[1] The Theory of Numbers by Adrew Adler and John Coury \item[2] Number Theory by David Burton \item[3] Introduction to Analytic Number Theory by Apostol \end{itemize} The students may consult the above mentioned texts for the course according to the following setting \begin{itemize} \item Lecture 1 to Lecture 18 consult first text \item Lecture 19 to Lecture 24 consult second text \item Lecture 25 to Lecture 32 consult third text \end{itemize} \maketitle \tableofcontents \chapter{Divisibility}Integers are the building blocks of the theory of numbers. This chapter contains somewhat very simple and obvious observations starting with properties of integers and yet the proofs behind those observations are not as simple. \section{Preliminaries} We will discuss about set of integers, well ordering principal and linear combinations first. \subsection{\textbf{The Well Ordering Principle}} \textbf{The Well Ordering Principle:} \index{Well Ordering Principle} A least element exist in any non empty set of positive integers.\\ This principle can be taken as an axiom on integers and it will be the key to proving many theorems. As a result, we see that any set of positive integers is well ordered while the set of all integers is not well ordered.\\ \subsection{Integer Divisibility} \index{Divisibility} \begin{definition} If $a$ and $b$ are integers such that $a\neq 0$, then we say "$a$ divides $b$" if there exists an integer $k$ such that $b=ka$. \end{definition} \index{factor} \index{Multiple} If $a$ divides $b$, we also say "$a$ is a factor of $b$" or "$b$ is a multiple of $a$" and we write $a\mid b$. If $a$ doesn't divide $b$, we write $a\nmid b$. For example $2\mid 4$ and $7\mid 63$, while $5\nmid 26$. \begin{example} a) Note that any even integer has the form $2k$ for some integer $k$, while any odd integer has the form $2k+1$ for some integer $k$. Thus $2|n$ if $n$ is even, while $2\nmid n$ if $n$ is odd.\\ b) $\forall a\in\mathbb{Z}$ one has that $a\mid 0$.\\ c) If $b\in\mathbb{Z}$ is such that $|b|0$, then there exist unique integers $q$ and $r$ such that $a=bq+r$ where $0\leq r< b$. \end{theorem} \begin{proof} Consider the set $A=\{a-bk\geq 0 \mid k\in \mathbb{Z}\}$. Note that $A$ is nonempty since for $k0$. By the well ordering principle, $A$ has a least element $r=a-bq$ for some $q$. Notice that $r\geq 0$ by construction. Now if $r\geq b$ then (since $b>0$) \begin{equation*} r>r-b=a-bq-b=a-b(q+1)=\geq 0. \end{equation*} This leads to a contradiction since $r$ is assumed to be the least positive integer of the form $r=a-bq$. As a result we have $0\leq r \max(r_1,r_2)$, then $r_2-r_1$ must be $0$, i.e. $r_2=r_1$. And since $bq_1+r_1=bq_2+r_2$, we also get that $q_1=q_2$. This proves uniqueness. \end{proof} \begin{example} If $a=71$ and $b=6$, then $71=6\cdot 11+5$. Here $q=11$ and $r=5$. \end{example} \textbf{Exercises} \begin{enumerate} \item{Show that $5\mid 25, 19\mid38$ and $2\mid 98$.}\item{Use the division algorithm to find the quotient and the remainder when 76 is divided by 13}. \item{Use the division algorithm to find the quotient and the remainder when -100 is divided by 13.}\item{Show that if $a,b,c$ and $d$ are integers with $a$ and $c$ nonzero, such that $a\mid b$ and $c\mid d$, then $ac\mid bd$.}\item{Show that if $a$ and $b$ are positive integers and $a\mid b$, then $a\leq b$.}\item{Prove that the sum of two even integers is even, the sum of two odd integers is even and the sum of an even integer and an odd integer is odd.}\item{Show that the product of two even integers is even, the product of two odd integers is odd and the product of an even integer and an odd integer is even.} \item{Show that if $m$ is an integer then $3$ divides $m^3-m$.} \item{Show that the square of every odd integer is of the form $8m+1$.}\item{Show that the square of any integer is of the form $3m$ or $3m+1$ but not of the form $3m+2$.}\item{Show that if $ac\mid bc$, then $a\mid b$.}\item{Show that if $a\mid b$ and $b\mid a$ then $a=\pm b$.} \end{enumerate} \section{The Greatest Common Divisor} \par In this section we define the greatest common divisor (gcd) \index{Greatest Common Divisor} of two integers and discuss its properties. We also prove that the greatest common divisor of two integers is a linear combination of these integers. Two integers $a$ and $b$, not both $0$, can have only finitely many divisors, and thus can have only finitely many common divisors. In this section, we are interested in the greatest common divisor of $a$ and $b$. Note that the divisors of $a$ and that of $\mid a \mid $ are the same. \begin{definition} The greatest common divisor of two integers $a$ and $b$ is the greatest integer that divides both $a$ and $b$. \end{definition} We denote the greatest common divisor of two integers $a$ and $b$ by $(a,b)$. We also define $(0,0)=0$. \begin{example} Note that the greatest common divisor of 24 and 18 is 6. In other words $(24,18)=6$. \end{example} There are couples of integers (e.g. 3 and 4, etc...) whose greatest common divisor is 1 so we call such integers relatively prime integers.\index{Relatively Prime} \begin{definition} Two integers $a$ and $b$ are relatively prime if $(a,b)=1$. \end{definition} \begin{example} The greatest common divisor of 9 and 16 is 1, thus they are relatively prime. \end{example} Note that every integer has positive and negative divisors. If $a$ is a positive divisor of $m$, then $-a$ is also a divisor of $m$. Therefore by our definition of the greatest common divisor, we can see that $(a,b)=(\mid a\mid, \mid b\mid)$. \par We now present a theorem about the greatest common divisor of two integers. The theorem states that if we divide two integers by their greatest common divisor, then the outcome is a couple of integers that are relatively prime. \begin{theorem} If $(a,b)=d$ then $(a/d,b/d)=1$. \end{theorem} \begin{proof} We will show that $a/d$ and $b/d$ have no common positive divisors other than $1$. Assume that $k$ is a positive common divisor such that $k\mid a/d$ and $k\mid b/d$. As a result, there are two positive integers $m$ and $n$ such that \begin{equation*} a/d=km \hspace{0.3 cm}\mbox{and} \ \ b/d=kn \end{equation*} Thus we get that \begin{equation*} a=kmd \hspace{0.3 cm}\mbox{and} \ \ b=knd. \end{equation*} Hence $kd$ is a common divisor of both $a$ and $b$. Also, $kd\geq d$. However, $d$ is the greatest common divisor of $a$ and $b$. As a result, we get that $k=1$. \end{proof} The next theorem shows that the greatest common divisor of two integers does not change when we add a multiple of one of the two integers to the other. \begin{theorem} Let $a,b$ and $c$ be integers. Then $(a,b)=(a+cb,b)$. \end{theorem} \begin{proof} We will show that every divisor of $a$ and $b$ is also a divisor of $a+cb$ and $b$ and vise versa. Hence they have exactly the same divisors. So we get that the greatest common divisor of $a$ and $b$ will also be the greatest common divisor of $a+cb$ and $b$. Let $k$ be a common divisor of $a$ and $b$. By Theorem \ref{thm4}, $k \mid (a+cb)$ and hence $k$ is a divisor of $a+cb$. Now assume that $l$ is a common divisor of $a+cb$ and $b$. Also by Theorem \ref{thm4} we have , \begin{equation*} l\mid ((a+cb)-cb)=a. \end{equation*} As a result, $l$ is a common divisor of $a$ and $b$ and the result follows. \end{proof} \begin{example} Notice that $(4,14)=(4,14-3\cdot 4)=(4,2)=2$. \end{example} We now present a theorem which proves that the greatest common divisor of two integers can be written as a linear combination of the two integers. \begin{theorem}\label{thm9} The greatest common divisor of two integers $a$ and $b$, not both $0$ is the least positive integer such that $ma+nb=d$ for some integers $m$ and $n$. \end{theorem} \begin{proof} Assume without loss of generality that $a$ and $b$ are positive integers. Consider the set of all positive integer linear combinations of $a$ and $b$. This set is non empty since $a=1\cdot a+0\cdot b$ and $b=0\cdot a+1\cdot b$ are both in this set. Thus this set has a least element $d$ by the well-ordering principle. Thus $d=ma+nb$ for some integers $m$ and $n$. We have to prove that $d$ divides both $a$ and $b$ and that it is the greatest divisor of $a$ and $b$. \par By the division algorithm, we have \begin{equation*} a=dq+r, \ \ \ 0\leq r$.} \end{enumerate} \chapter{Fundamental Theorem of Arithmetics}Prime numbers, the building blocks of integers, have been studied extensively over the centuries. Being able to present an integer uniquely as product of primes is the main reason behind the whole theory of numbers and behind the interesting results in this theory. Many interesting theorems, applications and conjectures have been formulated based on the properties of prime numbers. \par In this chapter, we present methods to determine whether a number is prime or composite using an ancient Greek method invented by Eratosthenes. We also show that there are infinitely many prime numbers. We then proceed to show that every integer can be written uniquely as a product of primes. \par We introduce as well the concept of diophantine equations where integer solutions from given equations are determined using the greatest common divisor. We then mention the Prime Number theorem without giving a proof of course in addition to other conjectures and major results related to prime numbers. \section{The infinitude of Primes} We now show that there are infinitely many primes. There are several ways to prove this result. An alternative proof to the one presented here is given as an exercise. The proof we will provide was presented by Euclid in his book the Elements. \begin{theorem} There are infinitely many primes. \end{theorem} \begin{proof} We present the proof by contradiction. Suppose there are finitely many primes $p_1, p_2, ...,p_n$, where $n$ is a positive integer. Consider the integer $Q$ such that \begin{equation*} Q=p_1p_2...p_n+1. \end{equation*} By Lemma 3, $Q$ has at least a prime divisor, say $q$. If we prove that $q$ is not one of the primes listed then we obtain a contradiction. Suppose now that $q=p_i$ for $1\leq i\leq n$. Thus $q$ divides $p_1p_2...p_n$ and as a result $q$ divides $Q-p_1p_2...p_n$. Therefore $q$ divides 1. But this is impossible since there is no prime that divides 1 and as a result $q$ is not one of the primes listed. \end{proof} The following theorem discusses the large gaps between primes. It simply states that there are arbitrary large gaps in the series of primes and that the primes are spaced irregularly. \begin{theorem} Given any positive integer $n$, there exists $n$ consecutive composite integers. \end{theorem} \begin{proof} Consider the sequence of integers \begin{equation*} (n+1)!+2, (n+1)!+3,...,(n+1)!+n, (n+1)!+n+1 \end{equation*} Notice that every integer in the above sequence is composite because $k$ divides $(n+1)!+k$ if $2\leq k\leq n+1$ by \ref{thm4}. \end{proof} \textbf{Exercises} \begin{enumerate} \item{Show that the integer $Q_n=n!+1$, where $n$ is a positive integer, has a prime divisor greater than $n$. Conclude that there are infinitely many primes. Notice that this exercise is another proof of the infinitude of primes.} \item{Find the smallest five consecutive composite integers.}\item{Find one million consecutive composite integers.}\item{Show that there are no prime triplets other than 3,5,7.} \end{enumerate} \section{The Fundamental Theorem of Arithmetic} The Fundamental Theorem of Arithmetic is one of the most important results in this chapter. It simply says that every positive integer can be written uniquely as a product of primes. The unique factorization is needed to establish much of what comes later. There are systems where unique factorization fails to hold. Many of these examples come from algebraic number theory. We can actually list an easy example where unique factorization fails. \par Consider the class $C$ of positive even integers. Note that $C$ is closed under multiplication, which means that the product of any two elements in $C$ is again in $C$. Suppose now that the only number we know are the members of $C$. Then we have $12=2.6$ is composite where as $14$ is prime since it is not the product of two numbers in $C$. Now notice that $60=2.30=6.10$ and thus the factorization is not unique. \par We now give examples of the unique factorization of integers. \index{Factorization} \begin{example} $99=3\cdot 3\cdot 11=3^2\cdot 11$, \ \ \ $32=2\cdot 2\cdot 2\cdot 2\cdot 2=2^5$ \end{example} \subsection{The Fundamental Theorem of Arithmetic} To prove the fundamental theorem of arithmetic, we need to prove some lemmas about divisibility. \begin{lemma}\label{lemma4} If a,b,c are positive integers such that $(a,b)=1$ and $a \mid bc$, then $a\mid c$. \end{lemma} \begin{proof} Since $(a,b)=1$, then there exists integers $x,y$ such that $ax+by=1$. As a result, $cax+cby=c$. Notice that since $a \mid bc$, then by Theorem 4, $a$ divides $cax+cby$ and hence $a$ divides $c$. \end{proof} We can generalize the above lemma as such: If $(a_,n_i)=1$ for every $i=1,2,\cdots,n$ and $a\mid n_1n_2\cdots n_{k+1}$, then $a\mid n_{k+1}$. We next prove a case of this generalization and use this to prove the fundamental theorem of arithmetic. \begin{lemma}\label{lemma5} If $p$ divides $n_1n_2n_3...n_k$, where p is a prime and $n_i >0$ for all $1\leq i\leq k$, then there is an integer $j$ with $1\leq j\leq k$ such that $p \mid n_j$. \end{lemma} \begin{proof} We present the proof of this result by induction. For $k=1$, the result is trivial. Assume now that the result is true for $k$. Consider $n_1n_2...n_{k+1}$ that is divisible by $p$. Notice that either \begin{equation*} (p,n_1n_2...n_k)=1\ \ \mbox{or} \ \ (p,n_1n_2...n_{k})=p. \end{equation*} Now if $(p,n_1n_2...n_k)=1$ then by Lemma 4, $p \mid n_{k+1}$. Now if $p\mid n_1n_2...n_k$, then by the induction hypothesis, there exists an integer $i$ such that $p\mid n_i$. \end{proof} We now state the fundamental theorem of arithmetic and present the proof using Lemma 5. \index{Fundamental Theorem of Arithmetic} \begin{theorem}\label{fta} \textbf{The Fundamental Theorem of Arithmetic} Every positive integer different from 1 can be written uniquely as a product of primes. \end{theorem} \begin{proof} If $n$ is a prime integer, then $n$ itself stands as a product of primes with a single factor. If $n$ is composite, we use proof by contradiction. Suppose now that there is some positive integer that cannot be written as the product of primes. Let $n$ be the smallest such integer. Let $n=ab$, with $10$.} \item{If $a\equiv b(mod\ m)$ and $c \equiv d (mod \ m)$ then $a+c \equiv (b+d) (mod \ m)$.} \item{If $a\equiv b(mod\ m)$ and $c \equiv d (mod \ m)$ then $a-c \equiv (b-d) (mod \ m)$.} \item{If $a\equiv b(mod\ m)$ and $c \equiv d (mod \ m)$ then $ac \equiv bd (mod \ m)$.} \end{enumerate} \end{theorem} \begin{proof} \begin{enumerate} \item{If $a \equiv b(mod \ m)$, then $m\mid (a-b)$. Thus there exists integer $k$ such that $a-b=mk$, this implies $b-a=m(-k)$ and thus $m\mid (b-a)$. Consequently $b\equiv a (mod \ m)$.} \item{Since $a\equiv b(mod \ m)$, then $m\mid (a-b)$. Also, $b\equiv c(mod \ m)$, then $m\mid (b-c)$. As a result, there exit two integers $k$ and $l$ such that $a=b+mk$ and $b=c+ml$, which imply that $a=c+m(k+l)$ giving that $a=c (mod \ m)$.} \item{Since $a\equiv b (mod \ m)$, then $m \mid (a-b)$. So if we add and subtract $c$ we get \begin{equation*} m\mid ((a+c)-(b+c)) \end{equation*} and as a result \begin{equation*} a+c\equiv b+c (mod \ m). \end{equation*}} \item{Since $a\equiv b (mod \ m)$, then $m \mid (a-b)$ so we can subtract and add $c$ and we get \begin{equation*} m\mid ((a-c)-(b-c)) \end{equation*} and as a result \begin{equation*} a-c\equiv b-c (mod \ m). \end{equation*}} \item{If $a \equiv b(mod \ m)$, then $m\mid (a-b)$. Thus there exists integer $k$ such that $a-b=mk$ and as a result $ac-bc=m(kc)$. Thus \begin{equation*} m\mid (ac-bc) \end{equation*} and hence \begin{equation*} ac\equiv bc (mod \ m). \end{equation*}} \item{If $a \equiv b(mod \ m)$, then $m\mid (a-b)$. Thus there exists integer $k$ such that $a-b=mk$ and as a result \begin{equation*} ac-bc=mc(k). \end{equation*} Thus \begin{equation*} mc\mid (ac-bc) \end{equation*} and hence \begin{equation*} ac\equiv bc (mod \ mc). \end{equation*}} \item{Since $a\equiv b(mod \ m)$, then $m\mid (a-b)$. Also, $c\equiv d(mod \ m)$, then $m\mid (c-d)$. As a result, there exits two integers $k$ and $l$ such that $a-b=mk$ and $c-d=ml$. Note that \begin{equation*} (a-b)+(c-d)=(a+c)-(b+d)=m(k+l). \end{equation*} As a result, \begin{equation*} m\mid ((a+c)-(b+d)), \end{equation*} hence \begin{equation*} a+c\equiv b+d(mod \ m).\end{equation*}} \item{If $a=b+mk$ and $c=d+ml$ where $k$ and $l$ are integers, then \begin{equation*} (a-b)-(c-d)=(a-c)-(b-d)=m(k-l). \end{equation*} As a result, \begin{equation*} m\mid ((a-c)-(b-d)), \end{equation*} hence \begin{equation*} a-c\equiv b-d(mod \ m). \end{equation*}} \item{There exit two integers $k$ and $l$ such that $a-b=mk$ and $c-d=ml$ and thus $ca-cb=m(ck)$ and $bc-bd=m(bl)$. Note that \begin{equation*} (ca-cb)+(bc-bd)=ac-bd=m(kc-lb). \end{equation*} As a result, \begin{equation*}m\mid (ac-bd), \end{equation*}hence \begin{equation*} ac\equiv bd(mod \ m). \end{equation*}} \end{enumerate} \end{proof} \begin{examples} \begin{enumerate} \item{Because $ 14\equiv 8(mod\ 6)$ then $8 \equiv 14 (mod\ 6)$.} \item{Because $22\equiv 10(mod \ 6)$ and $10 \equiv 4(mod \ 6)$. Notice that $22\equiv 4(mod \ 6)$.}\item{Because $50\equiv 20 (mod\ 15)$, then $50+5=55\equiv 20+5=25(mod\ 15)$.}\item{Because $50\equiv 20 (mod\ 15)$, then $50-5=45\equiv 20-5=15(mod\ 15)$.}\item{Because $19\equiv 16(mod3)$, then $2(19)=38\equiv 2(16)=32(mod \ 3).$}\item{Because $19\equiv 16(mod3)$, then $2(19)=38\equiv 2(16)=32(mod \ 2(3)=6).$}\item{Because $19\equiv 3 (mod \ 8)$ and $17\equiv 9(mod \ 8)$, then $19+17=36\equiv 3+9=12(mod \ 8)$}.\item{Because $19\equiv 3 (mod \ 8)$ and $17\equiv 9(mod \ 8)$, then $19-17=2\equiv 3-9=-6(mod \ 8)$}.\item{Because $19\equiv 3 (mod \ 8)$ and $17\equiv 9(mod \ 8)$, then $19(17)=323\equiv 3(9)=27(mod \ 8)$}. \end{enumerate} \end{examples} We now present a theorem that will show one difference between equations and congruences. In equations, if we divide both sides of the equation by a non-zero number, equality holds. While in congruences, it is not necessarily true. In other words, dividing both sides of the congruence by the same integer doesn't preserve the congruence. \begin{theorem} \begin{enumerate} \item {If $a,b, c$ and $m$ are integers such that $m>0$, $d=(m,c)$ and $ac\equiv bc(mod \ m)$, then $a\equiv b (mod \ m/d)$.} \item {If $(m,c)=1$ then $a=b(mod \ m)$ if $ac\equiv bc(mod \ m)$.} \end{enumerate} \end{theorem} \begin{proof} Part 2 follows immediately from Part 1. For Part 1, if $ac\equiv bc(mod \ m)$, then \begin{equation*} m\mid (ac-bc)=c(a-b). \end{equation*} Hence there exists $k$ such that $c(a-b)=mk$. Dividing both sides by $d$, we get $(c/d)(a-b)=k(m/d)$. Since $(m/d,c/d)=1$, it follows that $m/d \mid (a-b)$. Hence $a\equiv b (mod \ m/d)$. \end{proof} \begin{example} $38 \equiv 10 (mod\ 7)$. Since $(2,7)=1$ then $19\equiv 5 (mod \ 7).$ \end{example} The following theorem combines several congruences of two numbers with different moduli. \begin{theorem} If \begin{equation*} a\equiv b(mod \ m_1), a\equiv b(mod \ m_2),...,a\equiv b(mod \ m_t) \end{equation*} where $a,b,m_1,m_2,...,m_t$ are integers and $m_1,m_2,...,m_t$ are positive, then \begin{equation*} a\equiv b(mod \ \langle m_1,m_2,...m_t\rangle) \end{equation*} \end{theorem} \begin{proof} Since $a\equiv b (mod \ m_i)$ for all $1\leq i\leq t$. Thus $m_i \mid (a-b)$. As a result, \begin{equation*} \langle m_1,m_2,...,m_t\rangle \mid (a-b) \end{equation*} (prove this as an exercise). Thus \begin{equation*} a\equiv b(mod \ \langle m_1,m_2,...m_t\rangle). \end{equation*} \end{proof} \textbf{Exercises} \begin{enumerate} \item{Determine whether 3 and 99 are congruent modulo 7 or not.} \item{Show that if $x$ is an odd integer, then $x^2\equiv 1(mod \ 8)$} \item{Show that if $a,b, m$ and $n$ are integers such that $m$ and $n$ are positive, $n \mid m$ and $a\equiv b (mod \ m)$, then $a\equiv b (mod \ n).$}\item{Show that if $a_i\equiv b_i(mod \ m)$ for $i=1,2,...,n$, where $m$ is a positive integer and $a_i,b_i$ are integers for $j=1,2,...,n$, then $\sum_{i=1}^na_i\equiv \sum_{i=1}^nb_i(mod \ m)$}\item{For which $n$ does the expression $1+2+...+(n-1)\equiv 0(mod \ n)$ holds.} \end{enumerate} \chapter{Divisibility Test} \chapter{Linear congruences and solutions} \section{Linear Congruences} Because congruences are analogous to equations, it is natural to ask about solutions of linear equations. In this section, we will be discussing linear congruences of one variable and their solutions. We start by defining linear congruences. \index{Linear Congruence} \begin{definition} A congruence of the form $ax\equiv b(mod\ m)$ where $x$ is an unknown integer is called a linear congruence in one variable. \end{definition} It is important to know that if $x_0$ is a solution for a linear congruence, then all integers $x_i$ such that $x_i\equiv x_0 (mod \ m)$ are solutions of the linear congruence. Notice also that $ax\equiv b (mod\ m)$ is equivalent to a linear Diophantine equation i.e. there exists $y$ such that $ax-my=b$. We now prove theorems about the solutions of linear congruences. \begin{theorem} Let $a,b$ and $m$ be integers such that $m>0$ and let $c=(a,m)$. If $c$ does not divide $b$, then the congruence $ax\equiv b(mod \ m)$ has no solutions. If $c\mid b$, then \begin{equation*} ax\equiv b(mod \ m) \end{equation*} has exactly $c$ incongruent solutions modulo $m$. \end{theorem} \begin{proof} As we mentioned earlier, $ax\equiv b(mod \ m)$ is equivalent to $ax-my=b$. By Theorem 19 on Diophantine equations, we know that if $c$ does not divide $b$, then the equation, $ax-my=b$ has no solutions. Notice also that if $c\mid b$, then there are infinitely many solutions whose variable $x$ is given by \begin{equation*} x=x_0+(m/c)t \end{equation*} Thus the above values of $x$ are solutions of the congruence $ax\equiv b(mod \ m)$. Now we have to determine the number of incongruent solutions that we have. Suppose that two solutions are congruent, i.e. \begin{equation*} x_0+(m/c)t_1\equiv x_0+(m/c)t_2(mod \ m). \end{equation*} Thus we get \begin{equation*} (m/c)t_1\equiv (m/c)t_2(mod \ m). \end{equation*} Now notice that $(m,m/c)=m/c$ and thus \begin{equation*} t_1\equiv t_2(mod \ c). \end{equation*} Thus we get a set of incongruent solutions given by $x=x_0+(m/c)t$, where $t$ is taken modulo $c$. \end{proof} \begin{remark} Notice that if $c=(a,m)=1$, then there is a unique solution modulo m for the equation $ax\equiv b(mod \ m)$. \end{remark} \begin{example} Let us find all the solutions of the congruence $3x\equiv 12 (mod \ 6)$. Notice that $(3,6)=3$ and $3\mid 12$. Thus there are three incongruent solutions modulo $6$. We use the Euclidean algorithm to find the solution of the equation $3x-6y=12$ as described in chapter 2. As a result, we get $x_0=6$. Thus the three incongruent solutions are given by $x_1=6(mod \ 6)$, $x_1=6+2=2(mod \ 6)$ and $x_2=6+4=4(mod \ 6)$. \end{example} As we mentioned earlier in Remark 2, the congruence $ax\equiv b(mod \ m)$ has a unique solution if $(a,m)=1$. This will allow us to talk about modular inverses. \begin{definition} A solution for the congruence $ax\equiv 1 (mod\ m)$ for $(a,m)=1$ is called the modular inverse of $a$ modulo m. We denote such a solution by $\bar{a}$. \end{definition} \index{Modular Inverse} \index{Inverse} \begin{example} The modular inverse of 7 modulo 48 is 7. Notice that a solution for $7x\equiv 1(mod \ 48)$ is $x\equiv 7 (mod \ 48)$. \end{example} \textbf{Exercises} \begin{enumerate} \item{Find all solutions of $3x\equiv 6(mod \ 9)$.}\item{Find all solutions of $3x\equiv 2(mod \ 7)$.}\item{Find an inverse modulo 13 of 2 and of 11.}\item{Show that if $\bar{a}$ is the inverse of $a$ modulo $m$ and $\bar{b}$ is the inverse of $b$ modulo $m$, then $\bar{a}\bar{b}$ is the inverse of $ab$ modulo $m$.} \end{enumerate} \chapter{Algorithm for Linear congruences} \chapter{Chinese Remainder Theorem} \section{The Chinese Remainder Theorem} In this section, we discuss the solution of a system of congruences having different moduli. An example of this kind of systems is the following; find a number that leaves a remainder of 1 when divided by 2, a remainder of 2 when divided by three and a remainder of 3 when divided by 5. This kind of question can be translated into the language of congruences. As a result, in this chapter, we present a systematic way of solving this system of congruences. \index{Chinese Remainder Theorem} \begin{theorem} The system of congruences \begin{eqnarray*} && x\equiv b_1(mod \ n_1),\\&&x\equiv b_2(mod \ n_2),\\&&.\\&&.\\&&.\\&& x\equiv b_t(mod \ n_t), \end{eqnarray*} has a unique solution modulo $N=n_1n_2...n_t$ if $n_1,n_2,...,n_t$ are pairwise relatively prime positive integers. \end{theorem} \begin{proof} Let $N_k=N/n_k$. Since $(n_i,n_j)=1$ for all $i\neq j$, then $(N_k,n_k)=1$. Hence by Theorem 26 , we can find an inverse $y_k$ of $N_k$ modulo $n_k$ such that $N_ky_k\equiv 1(mod \ n_k)$. Consider now \begin{equation*} x=\sum_{i=1}^tb_iN_iy_i \end{equation*} Since \begin{equation*} N_j\equiv 0(mod \ n_k) \ \ \mbox{for all} \ \ j\neq k, \end{equation*} thus we see that \begin{equation*} x\equiv b_kN_ky_k(mod \ n_k). \end{equation*} Also notice that $N_ky_k\equiv 1(mod \ n_k)$. Hence $x$ is a solution to the system of t congruences. We have to show now that any two solutions are congruent modulo $N$. Suppose now that you have two solutions $x_0,x_1$ to the system of congruences. Then \begin{equation*} x_0\equiv x_1(mod \ n_k) \end{equation*} for all $1\leq k\leq t$. Thus by Theorem 23, we see that \begin{equation*} x_0\equiv x_1(mod \ N). \end{equation*} Thus the solution of the system is unique modulo $N$. \end{proof} We now present an example that will show how the Chinese remainder theorem is used to determine the solution of a given system of congruences. \begin{example} Solve the system \begin{eqnarray*} && x\equiv 1(mod \ 2)\\&& x\equiv 2(mod \ 3)\\&& x\equiv 3(mod \ 5). \end{eqnarray*} We have $N=2.3.5=30$. Also \begin{equation*} N_1=30/2=15, N_2=30/3=10 \mbox{and} \ \ N_3=30/5=6. \end{equation*} So we have to solve now $15y_1\equiv 1(mod \ 2)$. Thus \begin{equation*} y_1\equiv 1(mod \ 2). \end{equation*} In the same way, we find that \begin{equation*} y_2\equiv 1(mod \ 3) \mbox{and} \ \ y_3\equiv 1(mod \ 5). \end{equation*} As a result, we get \begin{equation*} x\equiv 1.15.1+2.10.1+3.6.1\equiv 53\equiv 23 (mod \ 30). \end{equation*} \end{example} \textbf{Exercises} \begin{enumerate} \item{Find an integer that leaves a remainder of 2 when divided by either 3 or 5, but that is divisible by 4.}\item{Find all integers that leave a remainder of 4 when divided by 11 and leaves a remainder of 3 when divided by 17.}\item{Find all integers that leave a remainder of 1 when divided by 2, a remainder of 2 when divided by 3 and a remainder of 3 when divided by 5. } \end{enumerate} \chapter{Dirichlet, Wilson's Theorems} \begin{lemma} Let $p$ be an odd prime and suppose $ p \nmid a.$ If there exists a number $b$ such that $b^2=a (mod \ p)$ then the congruence $x^2 \equiv a (mod \ p)$ has precisely two incongruent solutions modulo $p$. \end{lemma} \begin{proof} There are at least two incongruent solutions of the congruence since $(-b)^2 \equiv a (mod \ p)$ and $b \not\equiv (-b) ( mod \ p)$ as $p\neq 2$. To show there are only these two solutions we consider $x^2-b^2 \equiv 0 (mod \ p) $, it means that $ p \mid (x-b)(x+b)$. As $p$ is a prime number so it must divide at least one of them, hence the result. \end{proof} \begin{theorem} \textbf{Dirichlet Theorem} Let $p$ be a prime and $1 \leq a \leq p-1 $. If the congruence $ x^2 \equiv a (mod \ p) $ does not have solution then $ p-1 ! \equiv a^{(p-1)/2} (mod \ p) $ and if the congruence have the solution then $p-1 ! \equiv -a^{(p-1)/2} (mod \ p) $ \end{theorem} \begin{proof} The result is obvious for the $p=2$ , so assume that $p$ is an odd prime. If $ 1 \leq m \leq p-1$ then there exists a unique $n$ such that $ 1 \leq n \leq p-1 $ and $mn \equiv a (mod \ p).$ Call $m$ and $n$ are corresponding numbers. If $x^2 \equiv a (mod \ p)$ does not have a solution then $m \neq n$ for the corresponding numbers $m$ and $n$. Therefore the numbers from $1$ to $p-1$ can be paired off into $(p-1)/2$ corresponding pairs. The product of all the corresponding pairs is congruent to $a^ {(p-1)/2} (mod / p)$ but it is clearly also equal to $(p-1) !$. Therefore, $(p-1)! \equiv a^{(p-1)/2} (mod \ p)$.\\ If $ x^2 \equiv a (mod \ p) $ is solvable, it has a solution $b$ such that $ 1 \leq b \leq p-1$. The only other solution in the range is $p-b$. Arrange the remaining $p-3$ numbers from $1$ to $p-1$ into corresponding pairs, their product is then congruent to $a^ {(p-3)/2} (mod \ p)$. The product of the two remaining numbers $b$ and $p-b$ is congruent to $-a (mod \ p)$. Hence $(p-1) ! \equiv (-a)a^{(p-3)/2}=-a^{(p-1)/2} (mod \ p)$. \end{proof} One of the significance of this result is Wilson Theorem. \begin{theorem} \textbf{Wilson's Theorem} If $p$ is prime then $(p-1)! \equiv -1 ( mod \ p)$ \end{theorem} \begin{proof} Apply the Dirichlet theorem for $a=1$. It is obvious that the congruence $x^2 \equiv 1 (mod \ p)$ has a solution namely $x=1$. Which implies that $(p-1)!\equiv -1^{(p-1)/2} = (-1) (mod \ p)$. \end{proof} \subsection{Euler Criterion} \begin{theorem} \textbf{Euler's Criterion} Let $p$ be an odd prime and suppose $ p \nmid a$. Then $ x^2 \equiv a (mod \ p)$ is solvable or not solvable according as $a^{(p-1)/2} \equiv 1 (mod \ p)$ or $ a^{(p-1)/2} \equiv -1 (mod \ p)$. \end{theorem} \begin{proof} Suppose the congruence has a solution, then by the Dirichlet theorem and Wilson's theorem $-1 \equiv - a^{(p-1)/2} (mod \ p)$ and multiplication by $-1$ gives the result. The argument when the congruence has no solution is essentially the same. \end{proof} \begin{lemma} Let $a,u,v$ be integers with $u$ and $v$ an positive and $d=(u,v)$ and let $m > 0$. If $a^u \equiv 1 (mod \ m)$ and $ a^v \equiv 1 (mod \ m)$ then $a^d \equiv 1 (mod \ m).$ \end{lemma} \begin{proof} We know that $d$ can be written as the linear combination of the integers $u$ and $v$ i.e. $d=su + tv$. As $d$ is positive, one of the $s$ or $t$ must be positive. With out loss of generality assume that it is $t$. Then $(a^u)^s = a^d (a^v)^t $. Since $a^u \equiv a^v \equiv 1 (mod \ m)$, it follows that $a^d \equiv 1 (mod m).$ \end{proof} \chapter{Fermat Little Theorem, Euler $\phi$ function} \begin{theorem} \textbf{Fermat's Theorem} Let $p$ be a prime and suppose $ p \nmid a$. then $ a^{p-1} \equiv 1 (mod \ p).$ Equivalently, if $a$ is any integer, then $a^p \equiv a (mod \ p)$. \end{theorem} \begin{proof} We know by Euler's criterion $a^{(p-1)/2} \equiv \pm 1 (mod \ p)$. Square both sides of the congruence and we will get the theorem. \end{proof} Note also that the converse of Wilson's theorem also holds. The converse tells us whether an integer is prime or not. \begin{theorem} If $m$ is a positive integer with $m\geq 2$ such that \begin{equation*} (m-1)!+1\equiv 0 \ (mod \ m) \end{equation*} then $m$ is prime. \end{theorem} \begin{proof} Suppose that $m$ has a proper divisor $c_1$ and that \begin{equation*} (m-1)!+1\equiv 0(mod \ m). \end{equation*} That is $m=c_1c_2$ where $1p/2$ for all $i$ and let $n_1,n_2,...,n_t$ be those integers where $n_i

py. \end{equation*} Note that these pairs are precisely those where \begin{equation*} 1\leq x\leq (p-1)/2 \mbox{and} \ \ 1\leq y\leq qx/p. \end{equation*} For each fixed value of $x$ with $1\leq x\leq (p-1)/2$, there are $[qx/p]$ integers satisfying $1\leq y\leq qx/p$. Consequently, the total number of pairs with are \begin{equation*} 1\leq x\leq (p-1)/2, \ \ 1\leq y\leq qx/p, \mbox{and} \ \ qx>py \end{equation*} is \begin{equation*} \sum_{i=1}^{(p-1)/2}[qi/p]. \end{equation*} \par Consider now the pair of integers $(x,y)$ with \begin{equation*} 1\leq x\leq (p-1)/2, \ \ 1\leq y\leq (q-1)/2, \mbox{and} \ \ qx\sqrt{n}$, then \begin{equation*} \sqrt{n}\sqrt{n}\sqrt{n}=n. \end{equation*} Therefore $a\leq \sqrt{n}$. Also, by Lemma 3, $a$ must have a prime divisor $a_1$ which is also a prime divisor of $n$ and thus this divisor is less than $a_1 \leq a\leq \sqrt{n}$. \end{proof} We now present the algorithm of the Sieve of Eratosthenes that is used to determine prime numbers up to a given integer.\\ \textbf{The Algorithm of the Sieve of Eratosthenes} \begin{enumerate} \item{Write a list of numbers from 2 to the largest number $n$ you want to test. Note that every composite integer less than $n$ must have a prime factor less than $\sqrt{n}$. Hence you need to strike off the multiples of the primes that are less than $\sqrt{n}$} \item{Strike off all multiples of 2 greater than 2 from the list . The first remaining number in the list is a prime number.} \item{Strike off all multiples of this number from the list.} \item{Repeat the above steps until no more multiples are found of the prime integers that are less than $\sqrt{n}$} \end{enumerate} \textbf{Exercises} \begin{enumerate} \item{Use the Sieve of Eratosthenes to find all primes less than 100.} \item{Use the Sieve of Eratosthenes to find all primes less than 200.}\item{Show that no integer of the form $a^3+1$ is a prime except for $2=1^3+1$.}\item{Show that if $2^n-1$ is prime, then $n$ is prime. \\Hint: Use the identity $(a^{kl}-1)=(a^{k}-1)(a^{k(l-1)}+a^{k(l-2)}+...+a^k+1)$}. \end{enumerate} \chapter{Fermat, Mersenne primes and perfect numbers} \section{Perfect, Mersenne, and Fermat Numbers} Integers with certain properties were studied extensively over the centuries. We present some examples of such integers and prove theorems related to these integers and their properties. \par We start by defining perfect numbers. \index{Perfect Numbers} \begin{definition} A positive integer $n$ is called a perfect number if $\sigma(n)=2n$. \end{definition} In other words, a perfect number is a positive integer which is the sum of its proper divisors. \begin{example} The first perfect number is 6, since $\sigma(6)=12$. You can also view this as $6=1+2+3$. The second perfect number is 28, since $\sigma(28)=56$ or $28=1+2+4+7+14$. \end{example} The following theorem tells us which even positive integers are perfect. \begin{theorem} The positive integer $n$ is an even perfect number if and only if \begin{equation*} n=2^{l-1}(2^l-1), \end{equation*} where $l$ is an integer such that $l\geq 2$ and $2^l-1$ is prime. \end{theorem} \begin{proof} We show first that if $n=2^{l-1}(2^l-1)$ where $l$ is an integer such that $l\geq 2$ and $2^l-1$ is prime then $n$ is perfect. Notice that $2^l-1$ is odd and thus $(2^{l-1},2^l-1)=1$. Also, notice that $\sigma$ is a multiplicative function and thus \begin{equation*} \sigma(n)=\sigma(2^{l-1})\sigma(2^l-1). \end{equation*} Notice that $\sigma(2^{l-1})=2^l-1$ and since $ 2^l-1$ is prime we get $\sigma(2^l-1)=2^l$. Thus \begin{equation*} \sigma(n)=2n. \end{equation*} We now prove the converse. Suppose that $n$ is a perfect number. Let $n=2^rs$, where $r$ and $s$ are positive integers and $s$ is odd. Since $(2^r,s)=1$, we get \begin{equation*} \sigma(n)=\sigma(2^r)\sigma(s)=(2^{r+1}-1)\sigma(s). \end{equation*} Since $n$ is perfect, we get \begin{equation*} (2^{r+1}-1)\sigma(s)=2^{r+1}s. \end{equation*} Notice now that $(2^{r+1}-1, 2^{r+1})=1$ and thus $2^{r+1}\mid \sigma(s)$. Therefore there exists an integer $q$ such that $\sigma(s)=2^{r+1}q$. As a result, we have \begin{equation*} (2^{r+1}-1)2^{r+1}q=2^{r+1}s \end{equation*} and thus we get \begin{equation*} (2^{r+1}-1)q=s \end{equation*} So we get that $q\mid s$. We add $q$ to both sides of the above equation and we get \begin{equation*} s+q=(2^{r+1}-1)q+q=2^{r+1}q=\sigma(s). \end{equation*} We have to show now that $q=1$. Notice that if $q\neq 1$, then $s$ will have three divisors and thus $\sigma(s)\geq 1+s+q$. Hence $q=1$ and as a result $s=2^{r+1}-1$. Also notice that $\sigma(s)=s+1$. This shows that $s$ is prime since the only divisors of $s$ are $1$ and $s$. As a result, \begin{equation*} n=2^r(2^{r+1}-1), \end{equation*} where $(2^{r+1}-1)$ is prime. \end{proof} In theorem 50, we see that to determine even perfect numbers, we need to find primes of the form $2^l-1$. It is still unknown whether there are odd perfect numbers or not. \begin{theorem} If $2^l-1$ is prime where $l$ is a positive integer, then $l$ must be prime. \end{theorem} \begin{proof} Suppose that $l$ is composite, that is $l=rs$ where $12n$. Prove that if $n=2^{m-1}(2^m-1)$ where $m$ is a positive integer such that $2^m-1$ is composite, then $n$ is abundant.}\item{Show that there are infinitely many even abundant numbers.}\item{Show that there are infinitely many odd abundant numbers.}\item{Determine whether $M_{11}$ is prime.}\item{Determine whether $M_{29}$ is prime.}\item{Find all primes of the form $2^{2^n}+5$ where $n$ is a nonnegative integer.} \end{enumerate} \chapter{Arithmetic functions and Dirichlet product} sdfsdfsadf \section{Definitions and Properties} \index{Arithmetic Function} \begin{definition} An arithmetic function is a function whose domain of definition is the set $\mathbb{N}$ of positive integers. \end{definition} \index{Multiplicative Function} \begin{definition} An arithmetic function $f$ is called multiplicative if $f(ab)=f(a)f(b)$ for all $a,b\in\mathbb{N}$ such that $(a,b)=1$. \end{definition} \begin{definition} An arithmetic function $f$ is called completely multiplicative if \begin{equation} f(ab)=f(a)f(b) \end{equation} for all positive integers $a,b$. \end{definition} \index{Completely Multiplicative} \begin{example} The function $f(a)=1$ where $k$ is a completely multiplicative function since \begin{equation*} f(ab)=1=f(a)f(b). \end{equation*} Notice also that a completely multiplicative function is a multiplicative function but not otherwise. \end{example} We now prove a theorem about multiplicative functions. We will be interested in studying the properties of multiplicative functions rather than the completely multiplicative ones. \begin{theorem} Given a multiplicative function $f$. Let $n=\prod_{k=1}^sp_k^{a_k}$ be the prime factorization of $n$. Then \begin{equation*} f(n)=\prod_{k=1}^sf(p_k^{a_k}). \end{equation*} \end{theorem} \begin{proof} We prove this theorem by induction on the number of primes in the factorization of $n$. Suppose that $n=p_1^{a_1}$. Thus the result follow easily. Suppose now that for \begin{equation*} n=\prod_{k=1}^sp_k^{a_k}, \end{equation*} we have \begin{equation*} f(n)=\prod_{k=1}^sf(p_k^{a_k}). \end{equation*} So we have to prove that if \begin{equation*} n=\prod_{k=1}^{s+1}p_k^{a_k}, \end{equation*} then \begin{equation*} f(n)=\prod_{k=1}^{s+1}f(p_k^{a_k}). \end{equation*} Notice that for \begin{equation*} n=\prod_{k=1}^{s+1}p_k^{a_k}, \end{equation*} we have $(\prod_{k=1}^{s}p_k^{a_k},p_{s+1}^{a_{s+1}})=1$. Thus we have get \begin{equation*} f(n)=f(\prod_{k=1}^{s+1}p_k^{a_k})=f(\prod_{k=1}^{s}p_k^{a_k})f(p_{s+1}^{a_{s+1}}) \end{equation*} which by the inductive step gives \begin{equation*} f(\prod_{k=1}^{s+1}p_k^{a_k})=f(n)=\prod_{k=1}^{s+1}f(p_k^{a_k}). \end{equation*} \end{proof} From the above theorem, we can see that to evaluate a multiplicative function at an integer, it will be enough to know the value of the function at the primes that are in the prime factorization of the number. \par We now define summatory functions which represents the sum of the values of a given function at the divisors of a given number. \begin{definition} Let $f$ be an arithmetic function. Define \begin{equation*} F(n)=\sum_{d\mid n}f(d) \end{equation*} Then $F$ is called the summatory function of $f$. \index{Summatory Function} \end{definition} This function determines the sum of the values of the arithmetic function at the divisors of a given integer. \begin{example} If $f(n)$ is an arithmetic function, then \begin{equation*} F(18)=\sum_{d\mid 18}f(d)=f(1)+f(2)+f(3)+f(6)+f(9)+f(18). \end{equation*} \end{example} \begin{theorem} If $f$ is a multiplicative function, then the summatory function of $f$ denoted by $F(n)=\sum_{d\mid n}f(d)$ is also multiplicative. \end{theorem} \begin{proof} We have to prove that $F(mn)=F(m)F(n)$ whenever $(m,n)=1$. We have \begin{equation*} F(mn)=\sum_{d\mid mn}f(d). \end{equation*} Notice that by Lemma 6, each divisor of $mn$ can be written uniquely as a product of relatively prime divisors $d_1$ of $m$ and $d_2$ of $n$, moreover the product of any two divisors of $m$ and $n$ is a divisor of $mn$. Thus we get \begin{equation*} F(mn)=\sum_{d_1\mid m, d_2\mid n}f(d_1d_2) \end{equation*} Notice that since $f$ is multiplicative, we have \begin{eqnarray*} F(mn)&=& \sum_{d_1\mid m, d_2\mid n}f(d_1d_2)\\&=&\sum_{d_1\mid m, d_2\mid n}f(d_1)f(d_2)\\&=&\sum_{d_1\mid m}f(d_1)\sum_{d_2\mid n} f(d_2)=F(m)F(n) \end{eqnarray*} \end{proof} \textbf{Exercises} \begin{enumerate} \item{Determine whether the arithmetic functions $f(n)=n!$ and $g(n)=n/2$ are completely multiplicative or not.} \item{Define the arithmetic function $g(n)$ by the following. g(n)=1 if $n=1$ and 0 for $n>1$. Prove that $g(n)$ is multiplicative.} \end{enumerate} \section{Multiplicative Number Theoretic Functions} \par We now present several multiplicative number theoretic functions which will play a crucial role in many number theoretic results. We start by discussing the Euler phi-function which was defined in an earlier chapter. We then define the sum-of-divisors function and the number-of-divisors function along with their properties. \subsection{\textbf{The Euler $\phi$-Function}} As defined earlier, the Euler $\phi$-function counts the number of integers smaller than and relatively prime to a given integer. We first calculate the value of the $phi$-function at primes and prime powers. \begin{theorem} If $p$ is prime, then $\phi(p)=p-1$. Conversely, if $p$ is an integer such that $\phi(p)=p-1$, then $p$ is prime. \end{theorem} \begin{proof} The first part is obvious since every positive integer less than $p$ is relatively prime to $p$. Conversely, suppose that $p$ is not prime. Then $p=1$ or $p$ is a composite number. If $p=1$, then $\phi(p)\neq p-1$. Now if $p$ is composite, then $p$ has a positive divisor. Thus $\phi(p)\neq p-1$. We have a contradiction and thus $p$ is prime. \end{proof} We now find the value of $\phi$ at prime powers. \begin{theorem} Let $p$ be a prime and $m$ a positive integer, then $\phi(p^m)=p^m-p^{m-1}$. \end{theorem} \begin{proof} Note that all integers that are relatively prime to $p^m$ and that are less than $p^m$ are those that are not multiple of $p$. Those integers are $p,2p,3p,...,p^{m-1}p$. There are $p^{m-1}$ of those integers that are not relatively prime to $p^m$ and that are less than $p^m$. Thus \begin{equation*} \phi(p^m)=p^m-p^{m-1}. \end{equation*} \end{proof} \begin{example} $\phi(7^3)=7^3-7^2=343-49=294$. Also $\phi(2^{10})=2^{10}-2^9=512.$ \end{example} We now prove that $\phi$ is a multiplicative function. \begin{theorem} Let $m$ and $n$ be two relatively prime positive integers. Then $\phi(mn)=\phi(m)\phi(n)$. \end{theorem} \begin{proof} Denote $\phi(m)$ by $s$ and let $k_1,k_2,...,k_s$ be a reduced residue system modulo $m$. Similarly, denote $\phi(n)$ by $t$ and let $k_1',k_2',...,k_t'$ be a reduced residue system modulo $n$. Notice that if $x$ belongs to a reduced residue system modulo $mn$, then \begin{equation*} (x,m)=(x,n)=1. \end{equation*} Thus \begin{equation*} x\equiv k_i(mod\ m) \mbox{and} \ \ x\equiv k_j'(mod \ n) \end{equation*} for some $i,j$. Conversely, if \begin{equation*} x\equiv k_i(mod\ m) \mbox{and} \ \ x\equiv k_j'(mod \ n) \end{equation*} some $i,j$ then $(x,mn)=1$ and thus $x$ belongs to a reduced residue system modulo $mn$. Thus a reduced residue system modulo $mn$ can be obtained by by determining all $x$ that are congruent to $k_i$ and $k_j'$ modulo $m$ and $n$ respectively. By the Chinese remainder theorem, the system of equations \begin{equation*} x\equiv k_i(mod\ m) \mbox{and} \ \ x\equiv k_j'(mod \ n) \end{equation*} has a unique solution. Thus different $i$ and $j$ will yield different answers. Thus $\phi(mn)=st$. \end{proof} We now derive a formula for $\phi(n)$. \begin{theorem} Let $n=p_1^{a_1}p_2^{a_2}...p_s^{a_s}$ be the prime factorization of $n$. Then \begin{equation*} \phi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)...\left(1-\frac{1}{p_s}\right). \end{equation*} \end{theorem} \begin{proof} By Theorem 37, we can see that for all $1\leq i\leq k$ \begin{equation*} \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). \end{equation*} Thus by Theorem 38, \begin{eqnarray*} \phi(n)&=&\phi(p_1^{a_1}p_2^{a_2}...p_s^{a_s})\\&=& \phi(p_1^{a_1})\phi(p_2^{a_2})...\phi(p_s^{a_s})\\&=&p_1^{a_1}\left(1-\frac{1}{p_1}\right) p_2^{a_2}\left(1-\frac{1}{p_2}\right)...p_s^{a_s}\left(1-\frac{1}{p_s}\right)\\&=& p_1^{a_1}p_2^{a_2}...p_k^{a_k}\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)... \left(1-\frac{1}{p_s}\right)\\&=& n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)...\left(1-\frac{1}{p_s}\right). \end{eqnarray*} \end{proof} \begin{example} Note that \begin{equation*} \phi(200)=\phi(2^35^2)=200\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right)=80. \end{equation*} \end{example} \begin{theorem} Let $n$ be a positive integer greater than 2. Then $\phi(n)$ is even. \end{theorem} \begin{proof} Let $n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$. Since $\phi$ is multiplicative, then \begin{equation*} \phi(n)=\prod_{j=1}^k\phi(p_j^{a_j}). \end{equation*} Thus by Theorem 39, we have \begin{equation*} \phi(p_j^{a_j})=p_j^{a_j-1-1}(p_j-1). \end{equation*} We see then $\phi(p_j^{a_j})$is even if $p_j$ is an odd prime. Notice also that if $p_j=2$, then it follows that $\phi(p_j^{a_j})$ is even. Hence $\phi(n)$ is even. \end{proof} \begin{theorem} Let $n$ be a positive integer. Then \begin{equation*} \sum_{d\mid n}\phi(d)=n. \end{equation*} \end{theorem} \begin{proof} Split the integers from 1 to $n$ into classes. Put an integer $m$ in the class $C_d$ if the greatest common divisor of $m$ and $n$ is $d$. Thus the number of integers in the $C_d$ class is the number of positive integers not exceeding $n/d$ that are relatively prime to n/d. Thus we have $\phi(n/d)$ integers in $C_d$. Thus we see that \begin{equation*} n=\sum_{d\mid n}\phi(n/d). \end{equation*} As $d$ runs over all divisors of $n$, so does $n/d$. Hence \begin{equation*} n=\sum_{d\mid n}\phi(n/d)=\sum_{d\mid n}\phi(d). \end{equation*} \end{proof} \subsection{\textbf{The Sum-of-Divisors Function}} The sum of divisors function, denoted by $\sigma(n)$, is the sum of all positive divisors of $n$. \index{The Sum of Divisors Function} \begin{example} $\sigma(12)=1+2+3+4+6+12=28.$ \end{example} Note that we can express $\sigma(n)$ as $\sigma(n)=\sum_{d\mid n}d$. \par We now prove that $\sigma(n)$ is a multiplicative function. \begin{theorem} The sum of divisors function $\sigma(n)$ is multiplicative. \end{theorem} \begin{proof} We have proved in Theorem 35 that the summatory function is multiplicative once $f$ is multiplicative. Thus let $f(n)=n$ and notice that $f(n)$ is multiplicative. As a result, $\sigma(n)$ is multiplicative. \end{proof} Once we found out that $\sigma(n)$ is multiplicative, it remains to evaluate $\sigma(n)$ at powers of primes and hence we can derive a formula for its values at any positive integer. \begin{theorem} Let $p$ be a prime and let $n=p_1^{a_1}p_2^{a_2}...p_t^{a_t}$ be a positive integer. Then \begin{equation*} \sigma(p^a)=\frac{p^{a+1}-1}{p-1}, \end{equation*} and as a result, \begin{equation*} \sigma(n)=\prod_{j=1}^{t}\frac{p_j^{a_j+1}-1}{p_j-1} \end{equation*} \end{theorem} \begin{proof} Notice that the divisors of $p^{a}$ are $1,p,p^2,...,p^a$. Thus \begin{equation*} \sigma(p^a)=1+p+p^2+...+p^a=\frac{p^{a+1}-1}{p-1}. \end{equation*} where the above sum is the sum of the terms of a geometric progression. \par Now since $\sigma(n)$ is multiplicative, we have \begin{eqnarray*} \sigma(n)&=&\sigma(p^{a_1})\sigma(p^{a_2})...\sigma(p^{a_t})\\&=& \frac{p_1^{a_1+1}-1}{p_1-1}.\frac{p_2^{a_2+1}-1}{p_2-1}...\frac{p_t^{a_t+1}-1}{p_t-1}\\ &=&\prod_{j=1}^{t}\frac{p_j^{a_j+1}-1}{p_j-1} \end{eqnarray*} \end{proof} \begin{example} $\sigma(200)=\sigma(2^35^2)=\frac{2^4-1}{2-1}\frac{5^3-1}{5-1}=15.31=465.$ \end{example} \subsection{\textbf{The Number-of-Divisors Function}} The number of divisors function, denoted by $\tau(n)$, is the sum of all positive divisors of $n$. \index{The Number of Divisor Function} \begin{example} $\tau(8)=4.$ \end{example} We can also express $\tau(n)$ as $\tau(n)=\sum_{d\mid n}1$. \par We can also prove that $\tau(n)$ is a multiplicative function. \begin{theorem} The number of divisors function $\tau(n)$ is multiplicative. \end{theorem} \begin{proof} By Theorem 36, with $f(n)=1$, $\tau(n)$ is multiplicative. \end{proof} We also find a formula that evaluates $\tau(n)$ for any integer $n$. \begin{theorem} Let $p$ be a prime and let $n=p_1^{a_1}p_2^{a_2}...p_t^{a_t}$ be a positive integer. Then \begin{equation*} \tau(p^a)=a+1, \end{equation*} and as a result, \begin{equation*} \tau(n)=\prod_{j=1}^{t}(a_j+1). \end{equation*} \end{theorem} \begin{proof} The divisors of $p^{a}$ as mentioned before are $1,p,p^2,...,p^a$. Thus \begin{equation*} \tau(p^a)=a+1 \end{equation*} \par Now since $\tau(n)$ is multiplicative, we have \begin{eqnarray*} \tau(n)&=&\tau(p^{a_1})\tau(p^{a_2})...\tau(p^{a_t})\\&=& (a_1+1)(a_2+1)...(a_t+1)\\ &=&\prod_{j=1}^{t}(a_j+1). \end{eqnarray*} \end{proof} \begin{example} $\tau(200)=\tau(2^35^2)=(3+1)(2+1)=12$. \end{example} \textbf{Exercises} \begin{enumerate} \item{Find $\phi(256)$ and $\phi(2.3.5.7.11)$.} \item{Show that $\phi(5186)=\phi(5187)$.}\item{Find all positive integers $n$ such that $\phi(n)=6$.}\item{Show that if $n$ is a positive integer, then $\phi(2n)=\phi(n)$ if $n$ is odd.} \item{Show that if $n$ is a positive integer, then $\phi(2n)=2\phi(n)$ if $n$ is even.}\item{Show that if $n$ is an odd integer, then $\phi(4n)=2\phi(n)$.}\item{Find the sum of positive integer divisors and the number of positive integer divisors of 35}\item{Find the sum of positive integer divisors and the number of positive integer divisors of $2^53^45^37^313$}.\item{Which positive integers have an odd number of positive divisors.}\item{Which positive integers have exactly two positive divisors.} \end{enumerate} \chapter{Abelian group of arithmetic functions} \begin{theorem} If $f$ and $g$ are multiplicative functions then their Dirichlet product $f \ast g$ is also muliplicative. \end{theorem} \begin{proof} Let $h= f \ast g $ and choose relatively prime integers $m$ and $n$. Then $$h(mn) = \sum_{c \mid mn} f(c) g \left( \frac{mn}{c} \right) $$ Now every divisor $c$ of $mn$ be expressed in the form $c=ab$ where $ a \mid m$ and $ b \mid n$. Moreover, $(a,b)=1$ and $(m/a, n/b) =1$ and there is one one correspondence between the set of products $ab$ and the divisors $c$ of $mn$.\\ Hence $$h(mn)=\sum_{a \mid m , b \mid n} f(ab) g \left( \frac{mn}{ab} \right)= \sum_{a \mid m , b \mid n} f(a)f(b) g \left( \frac{m}{a} \right) g \left( \frac{n}{b} \right)$$ $$ \sum_{ a \mid m } f(a) g \left( \frac{m}{a} \right)\sum_{b \mid n} f(b) g \left( \frac{n}{b} \right) = h(m) h(n)$$ Which completes the proof. \end{proof} We now want to show that the inverse of a multiplicative function is again multiplicative. We prove this fact undirectly, first proving the following result and then concluding it as a corollary. \begin{theorem} If both $g$ and $ f \ast g$ are multiplicative, then $f$ is also multiplicative. \end{theorem} \begin{proof} We shall assume that $f$ is not multiplicative and deduce that $f \ast g$ is also not multiplicative. Let $ h = f \ast g$. Since $f$ is not multiplicative there exist positive integers $m$ and $n$ with $(m,n)=1$ such that $$ f(mn) \neq f(m) f(n) .$$ We choose such a pair $m$ and $n$ for which the product $mn$ is as small as possible. If $mn=1$ then $f(1) \neq f(1)f(1) $ so $f(1) \neq 1 $. Since $ h(1) =f(1)g(1)=f(1) \neq 1$ this shows that $h$ is not multiplicative.\\ If $mn > 1$ then we have $f(ab) =f(a)f(b)$ for all positive integers $a, b$ with $(a,b)=1$ and $ab < mn$. $$h(mn)= \sum_{ a \mid m , b \mid n , ab 1.\\ \end{array}\right .\ \end{equation*} \end{theorem} \begin{proof} For $n=1$, we have $F(1)=\mu(1)=1$. Let us now find $\mu(p^k)$ for any integer $k>0$. Notice that \begin{equation*} F(p^k)=\mu(1)+\mu(p)+...+\mu(p^k)=1+(-1)+0+...+0=0 \end{equation*} Thus by Theorem 36, for any integer $n=p_1^{a_1}p_2^{a_2}...p_t^{a_t}>1$ we have, \begin{equation*} F(n)=F(p_1^{a_1})F(p_2^{a_2})...F(p_t^{a_t})=0 \end{equation*} \end{proof} We now define the Mobius inversion formula. The Mobius inversion formula expresses the values of $f$ in terms of its summatory function of $f$. \index{Mobius Inversion Formula} \begin{theorem} Suppose that $f$ is an arithmetic function and suppose that $F$ is its summatory function, then for all positive integers $n$ we have \begin{equation*} f(n)=\sum_{d\mid n}\mu(d)F(n/d). \end{equation*} \end{theorem} \begin{proof} We have \begin{eqnarray*} \sum_{d\mid n}\mu(d)F(n/d)&=&\sum_{d\mid n}\mu(d)\sum_{e\mid (n/d)}f(e)\\ &=& \sum_{d\mid n}\sum_{e\mid (n/d)}\mu(d)f(e)\\&=&\sum_{e\mid n}\sum_{d\mid (n/e)}\mu(d)f(e)\\&=&\sum_{e\mid n}f(e)\sum_{d\mid (n/d)}\mu(d)\\ \end{eqnarray*} Notice that $\sum_{d\mid (n/e)}\mu(d)=0$ unless $n/e=1$ and thus $e=n$. Consequently we get \begin{equation*} \sum_{e\mid n}f(e)\sum_{d\mid (n/d)}\mu(d)=f(n).1=f(n). \end{equation*} \end{proof} \begin{example} A good example of a Mobius inversion formula would be the inversion of $\sigma(n)$ and $\tau(n)$. These two functions are the summatory functions of $f(n)=n$ and $f(n)=1$ respectively. Thus we get \begin{equation*} n=\sum_{d\mid n}\mu(n/d)\sigma(d) \end{equation*} and \begin{equation*} 1=\sum_{d\mid n}\mu(n/d)\tau(d). \end{equation*} \end{example} \textbf{Exercises} \begin{enumerate} \item{Find $\mu(12)$, $\mu(10!)$ and $\mu(105)$.}\item{Find the value of $\mu(n)$ for each integer $n$ with $100\leq n\leq 110$.}\item{Use the Mobius inversion formula and the identity $n=\sum_{d\mid n}\phi(n/d)$ to show that $\phi(p^t)=p^t-p^{t-1}$ where $p$ is a prime and $t$ is a positive integer.} \end{enumerate} \chapter{Bell Series of Arithmetic Functions} E. T. Bell use formal power series to study the properties of multiplicative arithmetical functioins \begin{definition} Given an arithmetical function $f$ and a prime $p$, we denote by $f_p(x)$ the formal power series $$ f_{p}(x) = \sum_{n=0}^{\infty} f(p^n) x ^n $$ and call this the Bell series of $f$. \end{definition} \begin{theorem} \textbf{Uniqueness Theorem} Let $f$ and $g $ be multiplicative functions. Then $f =g$ if and only if $$f_p(x) = g_p(x)$$ \end{theorem} \begin{proof} If $f=g$ then they must agree on all the integers and in particular to the prime powers, i,e, $f(p^n)=g(p^n)$ for all $p$ and all $n \geq 0$ so $f_p(x)=g_p(x)$.\\ Conversely, if $f_p(x)=g_p(x)$j for all $p$ then $f(p^n)=g(p^n)$ for all $n \geq 0$. Since $f$ and $g$ are multiplicative and agree at all prime powers they agree at all the positive integers by using the Fundamentel Theorem of Arithemtics. so $f=g$. \end{proof} Consider some examples. \begin{example} The Bell series of Mobius function is very simple as the $\mu (p^n) =0 $ for $n \geq 2$. So we have $$ \mu_p(x) = 1-x$$ \end{example} \begin{example} Consider the Euler $\phi$ function. we know that for the prime powers we have $\phi(p^k) = p^k - p^{k-1}$. $$\phi_p(x)= 1 + \sum_{n=1}^{\infty} (p^n - p^{n-1})x^n= (1-x) \sum_{n=0}^{\infty}p^n x^n= \frac{1-x}{1-px}$$ \end{example} \begin{example} \textbf{Completely multiplicative functions} If $f$ is completely multiplicative function then $f(p^a)=f(p)^a$ for all $a \geq 0$ so the Bell series is a geometric series of the following form. $$ f_p(x)= \sum_{n=0}^{\infty} f(p)^n x^n= \frac{1}{1-f(p)x}$$ \end{example} \section{Bell series and Dirichlet product} \begin{theorem} For any two arithmetical functions $f$ and $g$ and for every prime $p$ we have $$ (f \ast g)_p(x)= f_p(x) g_p(x)$$ \end{theorem} \begin{proof} Since the divisors of $p^n$ are $1,p,p^2,\ldots,p^n$ we have $$(f \ast g)(p^n) = \sum_{d \mid p^n} f(d) g\left( \frac{p^{n}}{d} \right) = \sum_{k = 0}^{ \infty} f(p^{k}) g(p^{n-k})$$ The last term above is exactly the coefficient of $n$th term when two series are multiplied, this simple fact conclude the theorem. \end{proof} \begin{example} Let $f(n)=2 ^{v(n)}$ where $v(1)=1$ and $v(n)=k$ if $ n=p_{1}^{\alpha_1} p_{2}^{\alpha_2} \ldots p_{k}^{\alpha_k}.$ Now we consider the Bell series of the function $f$ and try to construct the relation with Dirichlet product. $$f_p(x)= 1 + \sum_{n=1}^{\infty} 2^{v(p^n)}x^n =1 + \sum_{n=1}^{\infty}2x^n= 1 + \frac{2x}{1-x}=\frac{1+x}{1-x}$$ Hence $$f_p(x)= \mu_{P}^{2}(x)u_p(x)$$ which implies $f= \mu^{2} \ast u$ or $$ 2^{v(n)}= \sum_{ d \mid n} \mu^2(d) $$ \end{example} \chapter{Derivation of Arithmetic functions} \begin{definition} For any arithmetical function $f$ we define its derivative $f^{'}$ to be the arithmetical function given by the equation $$ f^{'}(n)=f(n) \log n$$ for $n \geq 1$ \end{definition} \begin{example} Since $I(n)\log n =0$ for all $n$ we have $ I^{'} =0$. Since $u(n)=1$ for all $n$ we have $ u^{'}(n)= \log n$. Hence the formula $ \sum_{d \mid n} \Lambda(d) = \log n$ can be written as $$ \Lambda \ast u = u^{'} $$ \end{example} This definition of derivation is not as we discussed in Calculus, which is the rate of change but still it share many properties of the derivation as the sum and product rule which we discussed in our next result. \begin{theorem} If $f$ and $g$ are arithmetical functions we have \begin{enumerate} \item $(f+g)^{'}=f^{'}+g^{'}$ \item $(g \ast g)^{'} = f^{'} \ast g + f \ast g^{'}$ \end{enumerate} \end{theorem} \begin{proof} The first part is very simple and the following shows it $$(f+g)^{'}=(f+g)(n) \log n =f(n) \log n + g(n) \log n = f^{'} + g^{'}$$ To prove the second we use the identity $ \log n = \log d + \log (n/d)$ and write $$ (f \ast g)^{'}= \sum_{d \mid n} f(d) g \left( \frac{n}{d} \right) \log n$$ $$= \sum_{d \mid n} f(d) \log d g \left( \frac{n}{d} \right) + \sum_{d \mid n} f(d) g \left( \frac{n}{d} \right) \log \left( \frac{n}{d} \right)$$ $$= (f^{'} \ast g) + (f \ast g^{'})$$ \end{proof} \section{Selberg Identity} Using the concept if derivative we can quickly derive the Selberg identity which is very important for the modern proof of prime number theorem. \begin{theorem} for $n \geq 1$ we have $$ \Lambda(n) \log n + \sum_{d \mid n} \Lambda(d) \Lambda \left( \frac{n}{d} \right)= \sum_{d \mid n} \mu(d) \log^{2} \frac{n}{d} $$ \end{theorem} \begin{proof} We know some identities which are $\Lambda \ast u = u ^{'}$ and $ \mu = u^{-1}$. We start with the first identity and differentiate both sides by using the previous theorem. $$\Lambda^{'} \ast u + \Lambda \ast u^{'} = u^{''}$$ Again put $\Lambda \ast u = u ^{'}$ in the above identity $$\Lambda^{'} \ast u + \Lambda \ast (\Lambda \ast u) = u^{''}$$ Now we multiply on both sides $\mu$ which is the inverse of $u$ and get $$ \Lambda^{'} + \Lambda \ast \Lambda = u^{''} \ast \mu $$ which is the required identity. \end{proof} \chapter{Big O and small o notations} We will explain the definitions and some examples of the notations. \section{The function $[x]$ , the symbols "O", "o" and "$\sim$"} We start this section by introducing an important number theoretic function. We proceed in defining some convenient symbols that will be used in connection with the growth and behavior of some functions that will be defined in later chapters. \\ \subsection{The Function $[x]$}. \index{The Function [x]} \begin{definition} The function $[x]$ represents the largest integer not exceeding $x$. In other words, for real $x$, $[x]$ is the unique integer such that \begin{equation*} x-1<[x]\leq x<[x]+1. \end{equation*} \end{definition} We also define $((x))$ to be the fractional part of $x$. In other words $((x))=x-[x]$. \\ We now list some properties of $[x]$ that will be used in later or in more advanced courses in number theory. \begin{enumerate} \item{$[x+n]=[x]+n$, if $n$ is an integer.} \item{$[x]+[y]\leq [x+y]$.} \item{$[x]+[-x]$ is 0 if $x$ is an integer and -1 otherwise.} \item{The number of integers $m$ for which $x 0$ then $$\sum_{y < n \leq x} f(n) = \int_{y}^{x} f(t) dt + \int_{y}^{x} (t- [t]) f^{'}(t)dt+f(x)([x]-x)-f(y)([y]-y)$$ \end{theorem} \begin{proof} Let $m=[y]$ and $k=[y]$. For integers $n$ and $n-1$ in $[y,x]$ we have $$ \int_{n-1}^{n} f^{'}(t) dt= \int_{n-1}^{n} (n-1) f^{'}(t) dt= (n-1) \{ f(n) - f(n-1) \}$$ $$ = \{ n f(n) - (n-1) f(n-1) \} -f(n) \}$$ Summing from $n=m+1$ to $n=k$ we have $$\int_{m}{k} [t] f^{'}(t)dt= \sum_{n=m+1}^{k} \{ n f(n) - (n-1) f(n-1) \} - \sum_{y < n \leq x} f(n) $$ $$ = kf(k) -mf(m) - \sum_{y < n \leq x} f(n) $$ Which implies $$\sum_{y < n \leq x} f(n) = - \int_{m}^{k} f^{'}(t)dt + k f(k) -m f(m)$$ \begin{equation} = - \int_{m}^{k} f^{'}(t)dt + k f(x) -m f(y) \end{equation} Now simply integerate the integral by parts and get \begin{equation} \int_{y}^{x} f(t) dt= xf(x) -yf(y) - \int_{y}^{x} t f^{'}(t) dt \end{equation} Now subtracting the above two equations we get the desired result. \end{proof} \subsection{ sum of the form $\sum_{n \leq x}$} We normally apply the Euler summation formula for the sum of type $\sum_{n \leq x}$ where $n$ runs on the integers. Obviously $n$ takes the value $1$. If we revisit the statement of Euler summation formula, the interval $[y,x]$ can be replace with $[1,x]$. In this case we have $$\sum_{n \leq x} f(n) = \sum_{ 1 < n \leq x} f(n) + f(1) $$. \begin{cor} If $f$ has continuous derivative $f^{'}$ on the interval $[1,x]$ then $$\sum_{1 < n \leq x} f(n) = \int_{1}^{x} f(t) dt + \int_{1}^{x} (t- [t]) f^{'}(t)dt+f(x)([x]-x)$$ \end{cor} \begin{proof} It is obvious when $y=1$ the term $[y]-y$ will vanish from the Euler Summation formula. \end{proof} \chapter{Applications of Euler Summation Formula} Before applying the Euler summation formula for finding the arithmetical functions in terms of well know functions we Euler constant and the Riemann Zeta function. \begin{definition} \textbf{Euler Constant} We define the Euler constant $C$ defined by the following equation $$ C = \lim_{n \rightarrow \infty} \left( 1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n} - \log n \right)$$ \end{definition} \begin{definition} \textbf{Riemann Zeta Function} The Reimann Zeta function $\xi(s)$ is defined as $$\xi(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} \hspace{.8 cm} s >1$$ $$ \xi(s) = \lim_{x \rightarrow \infty} \left( \sum_{n \leq x} \frac{1}{n^s} - \frac{x^{1-s}}{1-s} \right) \hspace{ .5 cm} 0 < s<1$$ \end{definition} \begin{theorem} If $x \geq 1$ we have \begin{enumerate} \item $\sum_{n\leq x} \frac{1}{n} = \log x +C+ O\left( \frac{1}{x} \right)$ \item $\sum_{n\leq x} \frac{1}{n^s}= \frac{x^{1-s}}{1-s}+\xi(s)+O(x^{-s})$ if $s > 0$ \item $\sum_{n > x} \frac{1}{n^s} = O(x^{1-s})$ if $s >1 $ \end{enumerate} \end{theorem} \begin{proof} \textbf{1} We apply the Euler summation formula for the function $f(t)-\frac{1}{t}$ for the sum $\sum_{n \leq x}$ $$ \sum_{n\leq x} \frac{1}{n}= \int_{1}^{x} \frac{dt}{t} - \int_{1}^{x} \frac{t- [t]}{t^2} dt - \frac{x-[x]}{x}+ f(1)$$ $$ = \log x - \int_{1}^{x} \frac{t- [t]}{t^2} dt + O\left( \frac{1}{x} \right) +1$$ $$ = \log x +1- \int_{1}^{\infty} \frac{t- [t]}{t^2} dt + \int_{x}^{\infty} \frac{t- [t]}{t^2} dt +O\left( \frac{1}{x} \right)$$ The improper integral $\int_{1}^{\infty} \frac{t- [t]}{t^2} dt$ exists since it is dominated by $ \int_{1}^{\infty} \frac{1}{t^2} dt$. Also $$ 0 \leq \int_{x}^{\infty} \frac{t-[t]}{t^2} dt \leq \int_{x}^{\infty} \frac{1}{t^2} dt = \frac{1}{x}$$ So the equation become $$\sum_{n \leq x} \frac{1}{n} = \log x +1 - \int_{1}^{\infty} \frac{t- [t]}{t^2} dt + O\left( \frac{1}{x} \right)$$ This proves the first with $ C = 1 - \int_{1}^{\infty} \frac{t- [t]}{t^2} dt$ because $$C= \lim_{x \rightarrow \infty} \left( \sum_{n \leq x} \frac{1}{n} - \log x \right) = 1 - \int_{1}^{\infty} \frac{t- [t]}{t^2} dt$$ \textbf{2} \hspace{ .3 cm} For the second part we apply the Euler summation formula for the function $f(t)= t^{-s}$ where $s > 0$ $$ \sum_{n \leq x} \frac{1}{n^s} = \int_{1}^{x}\frac{dt}{t^s} -s \int_{1}^{x} \frac{t-[t]}{t^{s+1}} dt - \frac{x - [x]}{x^s} + 1 $$ $$ = \frac{x^{1-s}}{1-s} - \frac{1} { 1-s} +1 -s \int_{1}^{\infty} \frac{t - [t]}{t^{s+1}} dt + O(x^{-s}) $$ Therefore $$ \sum_{n \leq x} \frac{1}{n^s} = \frac{x^{1-s}}{1-s}+C(s) + O(x^{-s})$$ where $$C(s) = 1 - \frac{1}{1-s} -s \int_{1}^{\infty} \frac{t-[t]}{t^{s+1}} dt $$ If $s >1 $ the left hand side of the previous equation will approach to $\xi(s)$ as the terms $ x^{1-s}$ and $x^{-s}$ both approaches to $0$. Hence $C(s) = \xi(s)$.\\ If $ 0 < s<1$ $x^{-s} \rightarrow 0$ and the equation becomes $$ \lim_{x \rightarrow \infty} \left(\sum_{n \leq x} \frac{1}{n^s} - \frac{x^{1-s}}{1-s} \right) = C(s)$$ Therefore we have proved the second part as well.\\ \textbf{3} \hspace{ .3 cm} For the third part, we will use the second part with $s >1$ to obtain $$ \sum_{n >x} \frac{1}{n^{s}} = \xi(s) - \sum_{n \leq x} \frac{1}{n^s} = \frac{x^{1-s}}{s-1} + O(x^{-s})=O(x^{1-s})$$ since $x^{-s} \leq x ^{1-s} $. \end{proof} \chapter{Average order of divisor and Euler function} We need one more result in continuation of the previous results about the sum of harmonic type terms. \begin{theorem} If $x \geq 1$ $$\sum_{n \leq x}= \frac{x^{\alpha+1}}{\alpha+1} + O(x^{\alpha})$$ for $\alpha \geq 0$. \end{theorem} \begin{proof} Apply the Euler summation formula for the function $f(t)=t^{\alpha}$ to obtain $$\sum_{n \leq x} = \int_{1}^{x} t^{\alpha} dt + \alpha \int_{1}^{x} t^{\alpha -1} (t - [t]) dt+1 - (x-[x]) x^{\alpha}$$ $$= \frac{x^{\alpha+1}}{\alpha +1} - \frac{1}{\alpha+1} + O \left( \alpha \int_{1}^{x} t^{\alpha -1} dt \right) + O(x^{\alpha})$$ $$=\frac{\alpha+1}{\alpha+1} + O(x^{\alpha +1})$$ \end{proof} \section{Average order of divisor function} \begin{theorem} $\sum_{n \leq x} d(n) = x \log x +O(x)$ \end{theorem} \begin{proof} $$\sum_{n \leq x } d(n) = \sum_{n \leq x} \sum_{d \mid n} 1$$ $$= \sum_{q,d \leq x } 1 $$ $$= \sum{d \leq x} \sum_{q \leq \frac{x}{d}} 1 $$ Now we apply the previous theorem for $\alpha=0$ which will be of the form $$ =\sum_{n \leq \frac{x}{d}} n^{0}= \frac{x}{d} +O(1)$$ $$= x \sum_{d \leq x} \frac{1}{d} +O(1)$$ $$= x \{ \log x +C + O\left( \frac{1}{x} \right) \} +O(x)$$ $$= x \log x +O(x)$$ \end{proof} \section{Average order of Euler $\phi$ function} Before finding the average order of $\phi $ function we will prove an identity which we will use in the proof of average order. \begin{theorem} $$\sum_{\mu(n)}{n^2} = \frac{6}{\pi^2}$$ \end{theorem} \begin{proof} We know that $I(n)=0$ for all $n > 1$, so we can write $$ 1 = \sum_{n=1}{\infty} \frac{I(n)}{n^2} $$ Now we apply the identity $ I(n) = \sum_{d \mid n} \mu(d) $ and get $$1= \sum_{n=1}^{\infty} \frac{\sum_{d \mid n} \mu(d)}{n^2} = \sum_{d=1}^{\infty} \sum_{m=1}{\infty} \frac{\mu(d)}{(dm)^2}$$ $$ 1= \sum_{d=1}^{\infty} \frac{\mu(d)}{d^2} \sum_{m=1}^{\infty} \frac{1}{m^2}$$ $$ \sum_{d=1}^{\infty} \frac{\mu(d)}{d^2} = \left( \sum_{m=1}^{\infty} \frac{1}{m^2} \right)^{-1}=\left( \frac{\pi^2}{6} \right)^{-1}$$ $$\sum_{d=1}^{\infty} \frac{\mu(d)}{d^2} = \left( \frac{6}{\pi^2} \right)$$ \end{proof} \begin{theorem} $$ \sum_{n \leq x} \phi(n) = \frac{3 x^2}{\pi^2} +O(x \log x) $$ \end{theorem} \begin{proof} $$\sum_{n \leq x} \phi(n) = \sum_{n \leq x} {d \mid n} \mu(d) \frac{n}{d}$$ $$= \sum_{q,d \leq x} \mu(d) q $$ $$ = \sum_{d \leq x} \sum_{q \leq {x}{d}} \mu(d) q$$ $$ = \sum_{d \leq x} \mu(d) \sum_{q \leq frac{x}{d}} q$$ Now using the previous results for harmonic type functions we have $$ =\sum_{d \leq x} \mu(d) \left\{\frac{1}{2} \left(\frac{s}{d} \right)^2+O \left( \frac{x}{d} \right) \right\}$$ $$=\frac{x^2}{2} \sum_{d \leq x} \frac{\mu(d)}{d^2} + O\left( x \sum_{d \leq x} \frac{1}{d} \right)$$ Now using the previous identity which we proved we have the following $$= \frac{3x^6}{\pi^2} +O(x \log x)$$%% \end{proof} % 1 z q a Q A Z \cleardoublepage \phantomsection \pdfbookmark[0]{Index}{Index} \printindex \end{document}