Baker A. Algebra and Number Theory

[ Pobierz całość w formacie PDF ]

Hence (AF , ") and (AF , ") are commutative groups.
Proof.
(a) For n " Z+,
(� " �) " �(n) = � " �(d)�(n/d)
d|n
= �(k)�(d/k)�(n/d)
k|d d|n
= �(k)�( )�(m),
k m=n
2. CONVOLUTION AND M�BIUS INVERSION 49
and similarly
, � " (� " �)(n) = �(k)�( )�(m).
k m=n
Hence (� " �) " �(n) = � " (� " �)(n) for all n, so (� " �) " � = � " (� " �).
(b) We have
� " �(n) = �(d)�(n/d) = �(n),
d|n
and similarly � " �(n) = �(n).
(c) Take t1 = 1. We will show by Induction that there are numbers tn for which
td�(n/d) = �(n).
d|n
Suppose that for some k > 1 we have such numbers tn for n
td�(k/d) = �(k) = 0.
d|k
Rewriting this as
tk = - td�(k/d),
d|k
d =k
� �
we see that tk is uniquely determined from this equation. Now define � by �(n) = tn. By
construction,
� �
� " �(n) = �(n/d)�(d) = �(n).
d|n
� �
By (d) we also have � " � = � " �.
(d) We have
� " �(n) = �(d)�(n/d) = �(n/d)�(d) = �(k)�(n/k) = � " �(n).
d|n d|n k|n
�
In each of the groups (AF , ") and (AF , "), the inverse of an arithmetic function � is �.
Here is an important example.
Proposition 3.5. The inverse of � is � = �, the M�bius function.
�
Proof. Recall that �(n) = 1 for all n. By Proposition 3.3 we have
1 n = 1,
�(d)�(n/d) = �(d) =
0 n > 1.
d|n d|n
Hence � = � is the inverse of � by the proof of Proposition 3.4(c).
�
Theorem 3.6 (M�bius Inversion). Let f, g : Z+ -�! R (or f, g : Z+ -�! C) be arithmetic
functions satisfying
f(n) = g(d) (n " Z+).
d|n
Then
g(n) = f(d)�(n/d) (n " Z+).
d|n
50 3. ARITHMETIC FUNCTIONS
Proof. Notice that f = g " � from which we have
g = g " � = g " (� " �) = (g " �) " � = f " �.
Hence for n " Z+,
g(n) = f(d)�(n/d).
d|n
Example 3.7. Use M�bius Inversion to find a formula for �(n), where � is the Euler
function.
Solution. By Theorem 2.24(d),
�(d) = n.
d|n
This can be rewritten as the equation � " � = id where id(n) = n. Applying M�bius Inversion
gives � = id "�, i.e.,
n
�(n) = �(d) = �(n/d)d.
d
d|n d|n
So for example, if n = pr where p is a prime and r 1,
pr
�(pr) = �(d) = �(ps)pr-s = �(1)pr + �(p)pr-1 = pr - pr-1 = (p - 1)pr-1.
d
0 s r
d|pr
Example 3.8. Show that the function � = �1 satisfies
�(d)�(n/d) = n (n " Z+).
d|n
Solution. By definition,
�(n) = d,
d|n
hence � = id "�. By M�bius Inversion,
id = id "� = id "(� " �) = (id "�) " � = � " � = � " �,
so for n " Z+,
n = �(d)�(n/d) = �(d)�(n/d).
d|n d|n
Proposition 3.9. If �, � are multiplicative arithmetic functions, then �"� is multiplicative.
Proof. If m, n be coprime positive integers,
� " �(mn) = �(d)�(mn/d)
d|mn
= �(rs)�(mn/rs)
r|m
s|n
= �(r)�(s)�((m/r)(n/s))
r|m
s|n
= �(r)�(s)�(m/r)�(n/s)
r|m
s|n
= �(r)�(m/r) �(s)�(n/s)
r|m s|n
= � " �(m)� " �(n).
2. CONVOLUTION AND M�BIUS INVERSION 51
Hence � " � is multiplicative.
Corollary 3.10. Suppose that � is a multiplicative arithmetic function, and � is the ari-
thmetic function satisfying
�(n) = �(d) (n " Z+).
d|n
Then � is multiplicative.
Proof. � = � " �, so by M�bius Inversion, � = � " �, implying that � is multiplicative.
52 3. ARITHMETIC FUNCTIONS
Problem Set 3
3-1. Let � : Z+ -�! R be the function for which �(n) is the number of positive divisors of n.
a) Show that � is an arithmetic function.
b) Suppose that n = pr1pr2 � � � prt is the prime power factorization of n, where 2 p1
1 2 t
� � � 0. Show that
�(pr1pr2 � � � prt) = (r1 + 1)(r2 + 1) � � � (rt + 1).
1 2 t
c) Is � multiplicative?
d) Show that � " � = �.
3-2. Show that each of the functions �r (r 1) of Example 3.1 are multiplicative.
3-3. For each r " N0 define the arithmetic function [r]: Z+ -�! R by
[r](n) = nr.
In particular, [0] = � and [1] = id.
a) Show that [r] is multiplicative.
b) If r > 0, show that �r = [r] " �. Deduce that �r is multiplicative.
c) Show that [r] " [r] satisfies [r] " [r](n) = nr�(n).
d) Find a general formula for [r] " [s](n) when s
3-4. For n " Z+, prove the following formul�, where the functions are defined in the text or in
earlier questions.
(a) �(d)�(n/d) = n; (b) �(d)�(n/d) = 1; (c) �r(d)�(n/d) = nr.
d|n d|n d|n
CHAPTER 4
Finite and infinite sets, cardinality and countability
The natural numbers originally arose from counting elements in sets. There are two very
different possible sizes for sets, namely finite and infinite, and in this section we discuss these
concepts in detail.
1. Finite sets and cardinality
For a positive natural number n 1, set
n = {1, 2, 3, . . . , n}.
If n = 0, let 0 = ". Then the set n has n elements and we can think of it as the standard set
of that size.
Definition 4.1. Let f : X -�! Y be a function.
" f is an injection or one-one (1-1 ) if for x1, x2 " X,
f(x1) = f(x2) =�! x1 = x2.
" f is a surjection or onto if for each y " Y , there is an x " X such that y = f(x).
" f is a bijection or 1-1 correspondence if f is both injective and surjective. Equivalently,
f is a bijection if and only if it has an inverse f-1 : Y -�! X.
Definition 4.2. A set X is finite if for some n " N0 there is a bijection n -�! X. X is
infinite if it is not finite.
The next result is a formal version of what is usually called the Pigeonhole Principle.
Theorem 4.3 (Pigeonhole Principle: first version).
a) If there is an injection m -�! n then m n.
b) If there is a surjection m -�! n then m n.
c) If there is a bijection m -�! n then m = n.
Proof.
a) We will prove this by Induction on n. Consider the statement
P (n): For m " N0, if there is a injection m -�! n then m n.
When n = 0, there is exactly one function " -�! " (the identity function) and this is a
bijection; if m > 0 then there are no functions m -�! ". So P (0) is true.
Suppose that P (k) is true for some k " N0 and let f : m -�! k + 1 be an injection. We have
two cases to consider: (i) k + 1 " im f, (ii) k + 1 " im f.
/
(i) For some r " m we have f(r) = k + 1. Consider the function g : m - 1 -�! k given by
f(j) if 0 j
g(j) =
f(j + 1) if r
Then g is an injection, so by the assumption that m - 1 k, hence m k + 1.
(ii) Consider the function h: m -�! k given by h(j) = f(j). Then h is an injection, and by the
53
54 4. FINITE AND INFINITE SETS, CARDINALITY AND COUNTABILITY
assumption that P (k) is true, m k and so m k + 1.
In either case we have established that P (k) -�! P (k + 1).
By PMI, P (n) is true for all n " N0.
b) This time we proceed by Induction on m. Consider the statement
Q(m): For n " N0, if there is a surjection m -�! n then m n.
When m = 0, there is exactly one function " -�! " (the identity function) and this is a
bijection; if n > 0 there are no surjections " -�! n. So Q(0) is true.
Suppose that Q(k) is true for some k " N0 and let f : k + 1 -�! n be a surjection. Let [ Pobierz całość w formacie PDF ]

Archiwum