MATH 361: NUMBER THEORY — THIRD LECTURE1. IntroductionThe topic of this lecture is arithmetic functions and Dirichlet series.By way of introduction, consider Euclid’s proof that there exist infinitely manyprimes: If p1through pnare prime then the numberq = 1 +nYi=1piis not divisible by any pi. According to this argument, the next prime after p1through pncould be as large as q. The overestimate is astronomical. Specifically,compute that for n ≥ 3, sincepn≤ 1 + p1· · · pn−1≤ (7/6)p1· · · pn−1,it follows thatpn≤ (7/6)p1· · · pn−1≤ (7/6)2(p1· · · pn−2)2≤ (7/6)4(p1· · · pn−3)4≤ · · ·≤ (7/6)2n−3(p1p2)2n−3= 72n−3(since p1p2= 6)< e2n−2.So, for example, the tenth prime p10satisfies p10< 1.51143 × 1011. Since in factp10= 29, we see how little Euclid’s argument tells us.By contrast, Euler argued thatXp∈P1pdiverges,and in fact his argument shows more. The argument proceeds as follows. Defineζ(s) =∞Xn=11ns, s > 1.Note thatlims→1+ζ(s) = ∞,so that alsolims→1+log ζ(s) = ∞,(The logarithm is natural, of course.)12 MATH 361: NUMBER THEORY — THIRD LECTURENow, summing over values of n with steadily more prime factors givesXn=2e2n−s=∞Xe2=0(2−s)e2= (1 − 2−s)−1,Xn=2e23e3n−s=∞Xe2=0(2−s)e2∞Xe3=0(3−s)e3= (1 − 2−s)−1(1 − 3−s)−1,...Xn=2e2···pepn−s= (1 − 2−s)−1· · · (1 − p−s)−1.And so, being very casual about convergence, it is essentially a restatement ofunique factorization that the zeta function also has an infinite product expression,ζ(s) =Xn∈Z+n−s=Yp∈P(1 − p−s)−1.From the general serieslog(1 − X)−1=∞Xn=1Xn/n, |X| < 1,we have (again being very casual about convergence)log ζ(s) = logYp∈P(1 − p−s)−1=Xp∈Plog(1 − p−s)−1=Xp∈P∞Xn=1p−ns/n=Xp∈Pp−s+Xp∈P∞Xn=2p−ns/n.From above, we know that lims→1+log ζ(s) = ∞, while one term on the right sideof the previous display isPp∈Pp−s, which we want to understand as s tends to 1.As for the other term,Xp∈P∞Xn=2p−ns/n <Xp∈P∞Xn=2p−ns=Xp∈Pp−2s(1 − p−s)−1=Xp∈P1ps(ps− 1),andXp∈P1ps(ps− 1)<∞Xn=21ns(ns− 1)<∞Xn=21n(n − 1)= 1.Thus the quantity that we want to understand is bounded on both sides by quan-tities that we do understand,log ζ(s) − 1 <Xp∈Pp−s< log ζ(s).And solims→1+Xp∈Pp−s= ∞,and more specifically,lims→1+Ppp−slog ζ(s)= 1.MATH 361: NUMBER THEORY — THIRD LECTURE 3Thus the sum of prime reciprocals grows asymptotically as the logarithm of theharmonic series. Recall that the partial sums of the harmonic series themselvesgrow logarithmically, so that the sum of prime reciprocals grows very slowly. Euler’sresult is much stronger than Euclid’s, and it illustrates analytic number theory.2. Dirichlet SeriesThe zeta function is a particular instance of a Dirichlet series.Definition 2.1. An arithmetic function is a complex-valued function of positiveintegers,f : Z+−→ C.Its associated Dirichlet series is a formal series that depends on a parameter s,F (s) =∞Xn=1f(n)ns.Using Dirichlet series to discuss arithmetic functions is not really necessary, butI think that the Dirichlet series clarify what is going on.Let F and G be the Dirichlet series associated to the arithmetic functions fand g. Compute that their product isF (s)G(s) =Xnf(n)nsXmg(m)ms=Xn,mf(n)g(m)(nm)s=XnPde=nf(d)g(e)ns.That is, if we define the convolution (or Dirichlet product) of f and g to bef ∗ g : Z+−→ C, (f ∗ g)(n) =Xde=nf(d)g(e),then the corresponding product of Dirichlet series isF (s)G(s) =∞Xn=1(f ∗ g)(n)ns.That is, for arithmetic functions f, g, and h, and for Dirichlet series F , G, and H,h = f ∗ g ⇐⇒ H = F G.Since Dirichlet series with nonzero leading term are invertible (Pann−shas inversePbnn−swhere b1= a−11and bn= −a−11P1<d|nadbn/dfor n > 1), it follows fromthe boxed equivalence that the arithmetic functions that do not vanish at 1 form agroup under convolution.3. Examples, M¨obius InversionWith the boxed equivalence in mind, we create a small catalogue of arithmeticfunctions and their Dirichlet series.• The identity arithmetic function isi(n) =(1 if n = 1,0 otherwise.The corresponding Dirichlet series is simplyI(s) = 1.4 MATH 361: NUMBER THEORY — THIRD LECTURESince I(s) is the multiplicative identity, i is the convolution identity.• The unit arithmetic function isu(n) = 1 for all n.(Ireland and Rosen call this function I.) The corresponding Dirichlet seriesis the zeta function,U(s) = ζ(s).• The reciprocal of the zeta function is the Dirichlet seriesζ(s)−1=Yp(1 − p−s) = 1 −Xpp−s+Xp,q(pq)−s−Xp,q ,r(pqr)−s+ · · · .The corresponding arithmetic function is the M¨obius function,µ(n) =1 if n = 1,(−1)kif n = p1· · · pk(distinct primes),0 otherwise.Thus we have for any arithmetic functions f and g,g = f ∗ u ⇐⇒ G(s) = F (s)ζ(s)⇐⇒ F (s) = G(s)ζ(s)−1⇐⇒ f = g ∗ µ.The equivalence g = f ∗ u ⇐⇒ f = g ∗ µ is the M¨obius Inversion Formula,g(n) =Xd|nf(d) ⇐⇒ f(n) =Xd|nµ(d)g(n/d).As a special case, let f = i so that g = u. Then we have by M¨obius inversion,i(n) =Xd|nµ(d)u(n),which is to say,Xd|nµ(d) =(1 if n = 1,0 if n > 1.4. The Euler Totient FunctionThe Euler totient function is an arithmetic function,φ : Z+−→ Z+, φ(n) = #{x ∈ {0, · · · , n − 1} : gcd(x, n) = 1} = #(Z/nZ)×.Thus φ(1) = 1 and φ(p) = p − 1 for p prime.Now we set up M¨obius inversion by counting thatn =Xd|nφ(d) for all n ∈ Z+.MATH 361: NUMBER THEORY — THIRD LECTURE 5Indeed (noting that (k(n/d), n) = (n/d)(k, d) for the second equality to follow),{0, · · · , n − 1} =Gd|n{x ∈ {0, · · · , n − 1} : (x, n) = n/d}=Gd|n{k(n/d) : 0 ≤ k < d, (k, d) = 1},and the desired counting formula follows immediately by definition of the totientfunction. (For example, if n = 20 then the disjoint union is{0} t {10} t {5, 15} t {4, 8, 12, 16}t {2, 6, 14, 18} t {1, 3, 7, 9, 11, 13, 17, 19},with, for example, {2, 6, 14, 18} being the multiples of 20/10 by factors coprimeto 10.) Consequently, M¨obius inversion givesφ(n) =Xd|nµ(d)nd.That is,φ(n) = nXd|nµ(d)d= n1 −Xp|n1p+Xp,q |n1pq− · · ·.The sum-of-sums factors to give the formula for the totient function,φ(n) = nYp|n1 −1p.(Of course, one can derive the formula directly, e.g., by an inclusion-exclusion countof the elements of {0, · · · , n − 1} that are co-prime to n.)Some consequences of the