# PDF Archive

Easily share your PDF documents with your contacts, on the Web and Social Networks.

## 7BEF717Fd01 .pdf

Original filename: 7BEF717Fd01.pdf

This PDF 1.4 document has been generated by LaTeX with hyperref package / pdfeTeX-1.304, and has been sent on pdf-archive.com on 30/10/2017 at 10:10, from IP address 176.88.x.x. The current document download page has been viewed 99 times.
File size: 211 KB (9 pages).
Privacy: public file

### Download original PDF file ### Document preview

AARMS CLASSROOM NOTES
Notes 14, Draft of July 24, 2007, Pages 1–8
Centre for Number Theory Research, Sydney

INTRODUCTIONS TO NUMBER THEORY
AARMS SUMMER SCHOOL, 2007
CHAPTER 14 ARITHMETIC FUNCTIONS

ceNTRe
Sydney, Australia 2071

ALFRED J. VAN DER POORTEN

Introduction. The present notes expand the introductory remarks forming
part of the Prospectus.

1. Arithmetic Functions
It’s easy to see that indeed
ζ(s) := 1 +

−1
Y
1
1
1
1
1
+
+
+
+
+
+
·
·
·
=
.
1

2s
3s
4s
5s
ps
p

Here the product on the right is over the primes p = 2 , 3 , 5 , 7 , 11 , . . . .
We might ‘sieve’ ζ(s) as follows. First, notice that 21s ζ(s) is just the sum of the
reciprocals of the s-th power of the even integers. So (1 − 21s )ζ(s) = 11s + 31s + 51s +
1
1
1
1
1
1
1
1
1
1 1
1
7s + 9s + 11s + 13s + 15s + 17s + 19s + 21s + 23s + 25s + · · · . Just so, (1 − 2s ) 3s ζ(s)
1
is the sum of those terms of (1 − 2s )S(s) whose denominator ns has n divisible
by 3. Hence (1 − 21s )(1 − 31s )ζ(s) = 11s + 51s + 71s + 111s + 131s + 171s + 191s + 231s +
1
1
1
1
1
1
25s + 29s + 31s + 35s + 37s + · · · . We next consider 5s of that, and subtract, and
so on . . . ad infinitum. Because every integer, other than 1 , is divisible by some
prime the only term that survives the process is the leading term 1 , yielding the
assertion.
P∞
Better, certainly I prefer this argument, note that 1/(1 − p−s ) = h=0 p−hs .
P∞
−hi s
We now proceed to multiply the factors
for p1 = 2 , p2 = 3 , p3 = 5 ,
hi =0 pi
p4 = 7, . . . concluding that ζ(s) purportedly is the sum of all finite products
1 s −h2 s −h3 s
p−h
p2
p3
· · · . However, by the unique factorisation theorem these products
1
are in one to one correspondence with the quantities n−s , n a positive integer ∗ ,
confirming the claim.
It’s also not hard to see that the definition

Y
X
1
1
µ(n)
=
1 − s =:
ζ(s)
p
ns
p
n=1
implies that if n = p1 p2 · · · pm is a product of m distinct primes then µ(n) =
(−1)m ; otherwise, thus if n is divisible by some nontrivial square, µ(n) = 0 .
Typeset July 24, 2007 [ 20:59 ] .

When writing for adults, it should not be necessary to remark explicitly that (a) an empty
product is a finite product, and (b) of course it is 1 .
c
2007
Alfred J van der Poorten

1

Alf van der Poorten

2

P
1.1. The Dirichlet
Most of us recall that the product
cn X n of
P convolution.
P
n
n
two power series
an X and
bn X is given by the Cauchy convolution
X
cn =
an−h bh .
h

Just so, the product
cn /ns of a pair of formal Dirichlet series
P
s
bn /n is given by the Dirichlet convolution
X
cn =
an/d bd ;
P

P

an /ns and

d|n

here the sum is over all positive integers d = 1 , . . . , n that happen to divide n .
1.2. M¨
obius inversion. The M¨obius ∗ function µ(n) crops up in situations that
are not a priori number theoretical at all. For example:
P∞
P∞
Fact. If G(x) = h=1 F (hx) then F (x) = h=1 µ(h)G(hx), and conversely.
An unfortunate innocent rediscovering this Fact experimentally is unlikely to
recognise the rule defining the µ(h) before expending quite as much effort as it
would have taken Em to have sat in on an introductory course in number theory.
Because ζ(s) · 1/ζ(s) is identically 1 it is obvious that
X
µ(d) = δ1n ,
d|n

where as usual the Kronecker δij vanishes, unless i = j when it is 1 . It is now an
easy matter to verify the Fact alleged above as well as to obtain the
P
P

obius inversion formula. If g(n) = d|n f (d) then f (n) = d|n µ(d)g(n/d),
and conversely.
P∞
P∞
Proof. Set F (s) = n=1 f (n)/ns and G(s) = n=1 g(n)/ns . The claim is the
somewhat obvious fact that if and only if G(s) = ζ(s)F (s) then F (s) = G(s)/ζ(s) .

1.3. The Euler totient function. The function φ(n) gives the order of the multiplicative group (Z/nZ)× , thus the
P number of positive integers less than n and
relatively prime to n . I say that
φ(d) = n . The cute argument is to declare
P d|n
that’s clear because, obviously,
#{k
: gcd(k, n) = d ; 1 ≤ k ≤ n} = n and,
d|n
plainly, #{k : gcd(k, n) = d ; 1 ≤ k ≤ n} = φ(n/d) .
Then by M¨
obius inversion we have

X
X µ(d)
Y
n
1
φ(n) =
µ(d) = n
=n
1−
.
d
d
p
d|n

d|n

p|n

Here the product is over all positive integer primes p dividing n .

By the way, one often sees ‘Moebius’ rather than ‘M¨
obius’. This is not bad spelling. It is de
rigueur in German to replace that Umlaut by a trailing ‘e’ in contexts, such as e-mail, where one
correctly fears that the Umlaut will not get printed.

AARMS Summer School 2007

Arithmetic Functions

3

1.4. Multiplicative
P∞ functions. Those functions f whose Dirichlet generating
function F (s) = n=1 f (n)/ns has an Euler product formula

X
Y

f (n) Y
f (p) f (p2 ) f (p3 )
F (s) =
=
1
+
+
+
+
·
·
·
:=
1 + Fp (s)
s
s
2s
3s
n
p
p
p
p
p
n=1
are of particular arithmetical interest. Plainly, it is necessary and sufficient that
f satisfies f (m)f (n) = f (mn) provided that m and n are relatively prime, that
is provided
Q that gcd(m, n) = 1 . If so, f is said to be multiplicative. If, in fact,
F (s) = p (1 − f (p)/ps )−1 , then f is totally multiplicative.
Theorem. Dirichlet products and Dirichlet quotients of multiplicative functions
are again multiplicative.
It’s a little tedious but straightforward to prove this by and from the (m, n) = 1
then f (m)f (n) = f (mn) criterion, but the point I wanted to make is that the claim
is obvious from the Euler product definition.
Let’s see in detail why it is immediate. For this purpose replace ps by X −1 .
Then the typical factor 1 + Fp (s) becomes a power series in X with constant
term 1. The product and quotient of two such formal power series are again such
power series. I rest my case.
1.5. Sums of divisors. Traditionally one sets
X
σk (n) :=
dk with σ := σ1 and either τ := σ0 or d := σ0 .
d|n

Now notice that the Dirichlet series belonging to nk is ζ(s − k) , so the series
belonging to σk (n) is ζ(s)ζ(s − k) . We can use this to compute, a little laboriously,
that σk (pm ) = (pk(m+1) − 1)/(pk − 1) . Happily, this is painlessly obvious from the
definition. We note that when k = 0 the relevant limit yields τ (pm ) = m + 1 .
It takes little more than a double
make divisor functions appear in fairly
P∞sum to
md
dq
is just the power series expansion of
natural contexts. For example,
d=1
1/(1 − q m )2 . Hence
∞ X

X
X
1
md
=
dq
=
σ(n)q n .
m )2
(1

q
m=1
n=1
m=1

X

d=1

1.6. Recreational mathematics. Now, behold 6 = 1 + 2 + 3 ; six is the sum of its
own divisors! No wonder this ‘perfect’ number is the number of days of the working
week. And, aha! A ‘moonth’ is twenty-eight days, where 28 = 1 + 2 + 4 + 7 + 14 .
Whatever, an integer is said to be perfect if it is the sum of its aliquot divisors,
those different from itself. In our language, therefore, n is perfect if σ(n) = 2n .
Way back, Euclid showed (proof eventually by Euler) that if an even integer n
is perfect then n = 2m−1 (2m − 1) where 2m − 1 is prime. The examples above are
m = 2 and m = 3. The smallest odd perfect number is ∗ very large.
Exercise. (a) Prove Euclid’s claim. (b) Show that if 2m − 1 is prime then m
is prime. (c) Show that p prime does not suffice to guarantee that the Mersenne
number Mp := 2p −1 is in fact a prime. (d) A pair of integers m and n is said to be

I started to add ‘if there is one’. But then I realised that if there are none the allegation
remains formally unfalsifiable.

Alf van der Poorten

4

amicable if σ(m) = σ(n) = m + n ; allegedly this notion goes back to Pythagoras.
Find the amicable pairs with at least one of m and n less than a thousand.
1.7. Some other arithmetic functions. The Mangoldt function Λ(n) , is a weighted
characteristic function of the prime powers. For n not the power of a prime, Λ(n)
vanishes, otherwise Λ(pk ) = log p . Better, the function is defined by
X
X
log n =
Λ(d) , or, equivalently, by Λ(d) = −
µ(d) log d .
d|n

d|n

Liouville’s function λ(n) notes the parity
of the prime powers appearing in the
P
factorisation of n in such a way that d|n λ(n) is the characteristic function of the
squares; it is 1 if n is a square, and vanishes otherwise. In fact, if n = pk11 pk22 · · · pkmm
then λ(n) = (−1)k1 +k2 +···+km . Its Dirichlet inverse λ−1 is |µ(n)|. Indeed, λ is
totally multiplicative so λ belongs to the Dirichlet series
Y
Y
Y
(1 − λ(p)/ps )−1 =
(1 + 1/ps )−1 , with reciprocal
(1 + 1/ps ) .
p

p

p

The function ν(n) counts the number of distinct primes dividing n . Plainly
X
2ν(n) =
|µ(d)| .
d|n

It can be convenient to define the function u as belonging to the Dirichlet series
ζ(s), thus u(n) = 1 for all positive integers n . If so, one might also want the trival
function I , defined by I(1) = 1 and I(n) = 0 for other n .
1.8. The ring of arithmetic functions. Amusingly, the map f (n) 7→ f (n) log n
is a derivation on the ring of arithmetic functions. Here, the addition is ‘pointwise’,
thus (f + g)(n) = f (n) + g(n) for all positive integers n , and the multiplication
f ∗ g is the Dirichlet convolution. Until now, I have carefully avoided defining
the notion ‘arithmetic function’. I now have to come clean and admit that any
function defined on the positive integers may insist on the title. The claim that
f 0 (n) = f (n) log n defines a derivation is the assertion that both (f + g)0 = f 0 + g 0 ,
which is trivial, and (f ∗ g)0 = f 0 ∗ g + f ∗ g 0 , which is fun. To allow for Dirichlet
division, we also need I 0 = 0; fortunately, that’s a consequence of log 1 = 0 .
1.9. Lambert series. Notice that if
F (x) =

X

an

n=1

then F (x) =

P∞

X

xnm

equivalently

F (x) =

m=1

k
k=1 bk x

an

n=1

with bk =
ζ(s)

X

X
n=1

P

n|k

an . So

an n−s =

X

bn n−s

n=1

For example

X
n=1

d(n)xn =

x
x2
x3
+
+
+ ···
1 − x 1 − x2
1 − x3

xn
,
1 − xn

AARMS Summer School 2007

Arithmetic Functions

5

and, see Chapter I, if r2 (n) denotes the number of formally distinct representations
of n as a sum of two squares, then

X
x5
x
x3
n
+
··· .
r2 (n)x = 4

1 − x 1 − x3
1 − x5
n=1
That yields the pleasant identity, due to Jacobi,

X
2
x5
x
x3
n2
x
+
··· .
=1+4

1 − x 1 − x3
1 − x5
n=−∞
In this context one should meet Jacobi’s celebrated triple-product identity

Y
X
2
(∗)
(1 − x2n )(1 + x2n−1 z)(1 + x2n−1 z −1 ) =
xn z n .
n=−∞

n=1

Given the wide application of the identity its proof is surprisingly simple. First,
call the product P
P (x, z) and observe that xzP (x, zx2 ) = P (x, z) . Write the sum

n
on the right as
and set a(x) = a0 (x) . One sees immediately
n=−∞ an (x)z
n2
that an (x) = x a(x). A little less immediately, one can confirm with a teeny
bit of ingenuity ∗ that P (x, i) = P (x, −1) . It follows that a(x) = a(x4 ) and so
a(x) = a(0) = 1.
Among the many interesting special cases, a highlight is obtained by noticing
that

X
Y
1
n
n
n −1
1/2
1/2
−1
(ζ m +ζ −m )x 2 m(m+1)
(1−x )(1+x ζ)(1+x ζ ) =
P (x , x ζ) = (1+ζ )
m=0

n=1

Taking ζ → −1 yields

Y
X
1
(1 − xn )3 =
(−1)m (2m + 1)x 2 m(m+1) .
n=1

m=0

Exercise 1. The preceding subsections are full of unproved or only partially proved
allegations. Detail the required arguments.
References
 Tom M. Apostol, Introduction to Analytic Number Theory, Undergraduate Texts in Mathematics, Springer-Verlag, New York-Heidelberg, 1976.
 G. H. Hardy and E. M. Wright, ‘An Introduction to the Theory of Numbers’, OUP, 4th
edition, 1960.

Observe, for example, that

Q∞

n=1 (1

− xn ) =

Q∞

n=1 (1

− x2n−1 )(1 − x2n ) .

Alf van der Poorten

6

2. The Circle Problem
Gauss showed that the the number N (t) of lattice points in a circle of radius
t centered at the origin is the area, πt , up
√ to a tolerance of order at most the
circumference, that is, the square root, O( t) . Sierpinski in 1904, following work
of Voronoi on the Dirichlet Divisor Problem, lowered the exponent in Gauss’s result
to 1/3. Further improvements have been obtained since then, not least the proofs
by Hardy and by Landau that the lower bound for the exponent is 1/4 .
A recent submission to the arXiv by Sylvain E. Cappell and Julius L. Shaneson
1
claims to provide a proof of the conjectured optimal error bound, O(t 4 +ε ) ; at first,
even second, glance one comes to the view that their claim is not necessarily false.
Dirichlet’s divisor problem asks for the error term in the sum
n
X
d(h) = n ln n + (2γ − 1)n + O(nα )
h=1

where, similarly, Dirichlet originally had given α = 1/2 , Voronoi had proved α =
1/3, Hardy and independently Landau showed that 1/4 is a lower bound, and Van
der Corput had improved meaningfully on that 1/3 . Incidentally, the best proved
bound 23/73 was obtained by Martin Huxley, who provides me with all the best
mathematical limericks. Cappell and Shaneson imply that their methods will yield
the optimal bound for this question as well.
The circle problem certainly relates to my discussion on the number r2 (n) = r(n)
of representations of n as a sum of two squares because plainly
2

N (t) =

t
X

r(n) .

n=0

3. More on Mersenne and Fermat numbers
Mersenne’s allegation that 267 − 1 is prime was disproved ∗ by
Cole † , who displayed 267 − 1 = 193707721 × 761838257287 after
working “three years of Sundays” to discover the fact. The story
goes that Cole’s lecture reporting the factorisation consisted of him
evaluating 267 − 1, and then laboriously multiplying 193707721 by
761838257287; et voil`
a!
Suppose some prime q divides Mp = 2p − 1 , with p prime of course (otherwise I
would not have called it p ). Then we have 2p = 1 (mod q) so 2 has order p in F∗q
which entails p (q − 1) (if you prefer, by Fermat’s Theorem . . . ). Thus q is of the
shape kp + 1 some positive integer k .
n
In similar spirit, if p is a prime divisor of Fn = 22 + 1 then 2 must have
order 2n+1 in F∗p so certainly p is of the shape p = 2n+1 k + 1 . Using this useful
fact, Fermat could test the primality (or otherwise) of F5 by checking sequentially
whether the primes in the sequence (64k + 1)k≥1 divide F5 . This required Fermat
to test 193, F3 = 257, 449, 577 , 641 , . . . .
Exercise 2. (a) Join Fermat in realising that distinct Fermat numbers are prime
to one another and avoid having to test the case k = 4.

Well, it had been known for some time that it’s composite, but the present sentence reads
more nicely.

F. N. Cole, Bull. AMS 10 (1903), 134–137.

AARMS Summer School 2007
n−2

Arithmetic Functions

7

n−1

(b) Better yet, square 22 22
− 1) modulo Fn and deduce that if p divides
Fn then p is of the shape p = 2n+2 k + 1 (in other words, above, Fermat may
assume that k is even). Thus the first putative divisor of F5 that Fermat
actually needs to test is 641 .
(c) Apply greater care than Fermat did to show that 5 · 27 + 1 = 29 + 27 + 1 of
course divides F5 = 232 + 1 . A nine-step long division of polynomials evaluated
at 2, equivalently of binary numbers, does the trick. To my surprise I got it
right the first time I tried it. It turns out that
232 + 1 = (29 + 27 + 1)(223 − 221 + 219 − 217 + 214 − 210 + 29 − 27 + 1) .
Mind you, one can of course know in advance of actually finding a factor that
a number is composite. Proving that it is prime is usually more problematic.
Mersenne and Fermat numbers are special in that there are straightforward tests
both necessary and sufficient to prove primality. The test for Mersenne primes
is due to Lucas ∗ , sharpened by Dick Lehmer. The trick is, in effect, to apply a
generalisation of Fermat’s Theorem
for quadratic irrationals.

p−1
Specifically, set α = 2 + 3 . Then Mp is prime if and only if α2
= −1
(mod Mp ).

Let q be a prime distinct from 2 or 3 and consider the finite field Fq ( 3) ,
noting that its multiplicative group contains exactly q 2 − 1 elements. Suppose that
p−1
p−1
q divides Mp . Then α2
= −1 (mod Mp ) entails α2
= −1 (mod q) and it
2
p
follows
that
necessarily
q

1

2
.
So
every
prime
factor
of
Mp is greater than
p
Mp , which is absurd.
Conversely, suppose that Mp is prime and, for convenience set q = Mp = 2p −
√ 1
1. We need to compute (2 + 3) 2 (q+1) mod q . Now it’s easy to compute q -th
powers because
by Fermat’s Theorem the primality of q entails that the binomial
coefficients kq vanish mod q if 0 &lt; k &lt; q . So certainly (a+b)q = aq +bq (mod q) ,
regardless of the nature of a and b . But we want a 12 (q + 1) th power so will need
1
2 (q−1) is given mod q by the Legendre
a cute trick.
We’ll also need to recall that c
c
symbol q when gcd(c, q) = 1 .

Hence notice that if τ 2 = 1 + 3 then τ 2 = α . Accordingly, we observe that,
modulo q of course,

1
1
τ q ( 2)q = 1 + ( 3)q so τ q 2 2 (q−1) 2 = 1 + ( 3)3 2 (q−1)
becomes

2 √
3 √
τ
2=1+
3.
q
q

But q ≡ −1 (mod 8) so 2q = 1 , and 3q and 3q have opposite sign by quadratic

reciprocity. Because, obviously, q ≡ 1 (mod 3) , it follows that 3q = −1 . Hence

τ q 2 = 1 − 3 and thus τ q+1 = −1 ,
q

1

confirming that q = Mp prime entails α 2 (q+1) = −1 (mod q) .
The Lucas–Lehmer test is a reformulation of the remarks above.
Rather than

computing directly with quadratic irrationals one writes α = 2− 3 and notes that

´
See the very nice book Edouard
Lucas and Primality Testing by Hugh C. Williams; Canadian Mathematical Society Series of Monographs and Advanced Texts, 22. A Wiley-Interscience
Publication. John Wiley &amp; Sons, Inc., New York, 1998. x+525 pp. ISBN: 0-471-14852-0.

Alf van der Poorten

8

the rational integers
n

n

Sn = α 2 + α 2
satisfy the straightforward recursion Sn+1 = Sn2 − 2 , where S0 = 4 . Moreover,
n+1
because αα = 1, S(n) = 0 (mod q) is equivalent to α2
= −1 (mod q) . Thus
Mp is prime if and only if Mp divides Sp−2 .
Obviously α may be replaced by many other quadratic irrationals yielding seemingly different tests for the primality of Mersenne numbers.
4. Yet More on Fermat Numbers
Primes of the shape N = k · 2n + 1 , with k &lt; 2n , are known as Proth primes.
1

Exercise 3. (a) Show that if there exists an integer a such that a 2 (N −1) = −1
(mod N ) then N = k · 2n + 1 is prime.
1
(b) Confirm P´epin’s Test that Fn is prime if and only if 3 2 (Fn −1 = −1 (mod Fn ) .
(c) Explain why P´epin’s Test is not all that useful in practice.
5. Constructions with Straight-edge and Compass
The Fermat numbers do arise in another interesting context. It was an old
problem, essentially completely solved by Gauss, to determine all regular polygons
that can be constructed using straight-edge and compass alone. For example, every
child knows that having drawn a circle, one can use one’s compass with radius
unchanged to mark all six vertices of a regular hexagon. It turns out that the
only possibilities for constructible regular n -gons are with n = 2m F , where F is a
product of distinct Fermat primes. The point is that these are the only numbers n
having the property that ϕ(n) is a power of 2 . This is relevant because, as is not
too difficult to see, points that can be reached by the classical construction method
must have their coordinates in a number field obtainable from Q by a sequence of
quadratic extensions.
6. Cyclotomic Polynomials
Consider the n -th roots of unity ζnk where ζn = e2πi/n and k = 1 , 2 , . . . , n . Of
course if gcd(k, n) = d then ζnk is an n/d -th root of unity. Indeed, only ϕ(n) of
the n -zeros of X n − 1 are primitive n -th roots of unity, that is not also m -th roots
of unity for some m less than n .
Denote by Φn (X) the polynomial with the ϕ(n) primitive n -th roots of unity as
its zeros. I suggest that it is obvious that the cyclotomic polynomial Φn is monic
and defined over Z but in any case we are about to see that explicitly.
Indeed, we plainly must have
Y
Xn − 1 =
Φd (X)
d|n

P

once again showing that necessarily
obius
d|n ϕ(d) = n . More, we can apply M¨
inversion to obtain
Y
Φn (X) =
(X n/d − 1)µ(d) .
d|n

Example.
Φ10 (X) = (X 10 − 1)(X − 1)/(X 5 − 1)(X 2 − 1) = X 4 − X 3 + X 2 − X + 1 .

AARMS Summer School 2007

Arithmetic Functions

9

Exercise 4. At first glance, the cyclotomic polynomials have coefficients 0 , ±1
only. Show that is not so by computing Φ105 (X).