Multiplicative Number Theory [PDF]

Zitiervorschau

Art of Problem Solving

WOOT 2011–12 Multiplicative Number Theory 1

Introduction

The purpose of this document is to introduce students to basic results in multiplicative number theory. Multiplicative number theory can provide quick proofs of certain number theoretic identities, as well as give us a better understanding of arithmetic functions involving prime factorization, such as τ (n), the number of divisors of n, and σ(n), the sum of the divisors of n. Multiplicative number theory leads to deeper results as well, such as the prime number theorem, and Dirichlet’s theorem on prime numbers.

Definitions

sh is ar stu ed d vi y re aC s o ou urc rs e eH w er as o. co m

2

A function f is called arithmetic if it takes the set of positive integers to the set of complex numbers C, although all the arithmetic functions we will discuss will be integer-valued. An arithmetic function f is multiplicative if f (1) 6= 0 and f (mn) = f (m)f (n) for all relatively prime positive integers m and n. Taking m = n = 1, we get f (1) = [f (1)]2 , so f (1) = 1 for any multiplicative function f . For example, the function τ (n) is multiplicative. (We will prove this later in the handout, using the machinery that we will build.) But there are some other simpler examples of multiplicative functions. Example. The function f such that f (n) = n for all positive integers n is multiplicative. We will denote this function by id (for identity), so id(n) = n for all n. Example. The function f such that f (n) = 1 for all positive integers n is multiplicative. We will denote this function by 1, so 1(n) = 1 for all n. (It may look strange to use a number to denote a function, but this is the convention, and it will be clear from the context that we are referring to the function.) Example. The function f such that f (1) = 1 and f (n) = 0 for all positive integers n > 1 is multiplicative. We will denote this function by δ1 , so  1 if n = 1, δ1 (n) = 0 if n > 1. Given a positive integer n > 1, let the prime factorization of n be n = pe11 pe22 · · · pekk .

Th

Then for any multiplicative function f ,

f (n) = f (pe11 pe22 · · · pekk ) = f (pe11 )f (pe22 ) · · · f (pekk ).

Thus, a multiplicative function is uniquely determined by its values at the powers of primes.

An arithmetic function f is completely multiplicative if f (1) 6= 0 and f (mn) = f (m)f (n) for all positive integers m and n (m and n need not be relatively prime). A completely multiplicative function is uniquely determined by its values at the primes: If n = pe11 pe22 · · · pekk , then f (n) = [f (p1 )]e1 [f (p2 )]e2 · · · [f (pk )]ek .

https://www.coursehero.com/file/13772121/2011WOOT-mntpdf/

1

Art of Problem Solving

WOOT 2011–12 Multiplicative Number Theory For example, the functions id(n), 1(n), and δ1 (n) are all completely multiplicative. However, τ (2)τ (2) = 2 · 2 = 4 and τ (4) = 3, so the function τ (n) is not completely multiplicative. Only a few arithmetic functions of interest are completely multiplicative.

3

Convolution

If we take two polynomials, say a0 + a1 x + a2 x2 + · · · and b0 + b1 x + b2 x2 + · · · , then their product is (a0 + a1 x + a2 x2 + · · · )(b0 + b1 x + b2 x2 + · · · )

sh is ar stu ed d vi y re aC s o ou urc rs e eH w er as o. co m

= a0 b0 + (a0 b1 + a1 b0 )x + (a0 b2 + a1 b1 + a2 b0 )x2 + · · · .

If we set cn to be the coefficient of xn in this product, then cn =

n X

ai bn−i .

i=0

We can also write this sum as

cn =

X

ai bj ,

i+j=n

where the sum is taken over all ordered pairs of nonnegative integers (i, j) such that i + j = n. The sequence (cn ) is called the convolution of the sequences (an ) and (bn ). In number theory, we have a similar version of convolution. Given arithmetic functions f and g, the convolution of f and g (which is another arithmetic function), denoted by f ∗ g, is defined by n X . (f ∗ g)(n) = f (d)g d d|n

For example, for n = 6,

(f ∗ g)(6) = f (1)g(6) + f (2)g(3) + f (3)g(2) + f (6)g(1).

Th

The convolution of f and g can also be written in the symmetric form X (f ∗ g)(n) = f (a)g(b), ab=n

where the sum is taken over all ordered pairs of positive integers (a, b) such that ab = n. This convolution formula may look strange, but as we will see, many well-known arithmetic functions can be expressed naturally in terms of convolution.

https://www.coursehero.com/file/13772121/2011WOOT-mntpdf/

2

Art of Problem Solving

WOOT 2011–12 Multiplicative Number Theory Convolution satisfies the following properties: For any arithmetic functions f , g, and h, (1) f ∗ g = g ∗ f (convolution is commutative) (2) f ∗ δ1 = δ1 ∗ f = f (δ1 is the identity with respect to convolution) (3) (f ∗ g) ∗ h = f ∗ (g ∗ h) (convolution is associative) Proof. (1) This is clear from the symmetric form of convolution. (2) For any positive integer n, X

f (d)δ1

n

.

sh is ar stu ed d vi y re aC s o ou urc rs e eH w er as o. co m

(f ∗ δ1 )(n) =

d|n

d

Recall that δ1 (1) = 1 and δ1 (n) = 0 if n > 1. In particular, in the sum above, δ1 ( nd ) = 0 if d < n, so the only term that is left is the term that corresponds to d = n. Thus, the sum simplifies to (f ∗ δ1 )(n) = f (n)δ1 (1) = f (n).

Hence, f ∗ δ1 = f . By symmetry, δ1 ∗ f = f . (3) The proof is left as an exercise.



Remember that only certain arithmetic functions are multiplicative, so when we take the convolution of two multiplicative functions, do we get another multiplicative function? We return to the example (f ∗ g)(6) = f (1)g(6) + f (2)g(3) + f (3)g(2) + f (6)g(1).

If f ∗ g is multiplicative, then in particular, f ∗ g must satisfy the equation (f ∗ g)(6) = (f ∗ g)(2) × (f ∗ g)(3).

By the definition of convolution,

(f ∗ g)(2) = f (1)g(2) + f (2)g(1),

(f ∗ g)(3) = f (1)g(3) + f (3)g(1),

Th

so

(f ∗ g)(2) × (f ∗ g)(3) = [f (1)g(2) + f (2)g(1)] × [f (1)g(3) + f (3)g(1)]

= f (1)f (1)g(2)g(3) + f (1)f (2)g(1)g(3) + f (1)f (3)g(1)g(2) + f (2)f (3)g(1)g(1).

This looks a lot like our expression for (f ∗ g)(6) above, so let’s see if they are equal. First, since f and g are multiplicative, f (1) = g(1) = 1, so (f ∗ g)(2) × (f ∗ g)(3) = f (1)g(2)g(3) + f (2)g(3) + f (3)g(2) + f (2)f (3)g(1).

https://www.coursehero.com/file/13772121/2011WOOT-mntpdf/

3

Art of Problem Solving

WOOT 2011–12 Multiplicative Number Theory Next, since f and g are multiplicative, f (6) = f (2)f (3) and g(6) = g(2)g(3), so (f ∗ g)(2) × (f ∗ g)(3) = f (1)g(6) + f (2)g(3) + f (3)g(2) + f (6)g(1), which is our expression for (f ∗ g)(6) above. Therefore, (f ∗ g)(6) = (f ∗ g)(2) × (f ∗ g)(3). This example suggests that the convolution of two multiplicative functions is also multiplicative. We can prove this as follows.

sh is ar stu ed d vi y re aC s o ou urc rs e eH w er as o. co m

Theorem 1. If f and g are multiplicative, then f ∗ g is also multiplicative. Proof. Let f and g be multiplicative functions, and let m and n be relatively prime positive integers. We want to show that (f ∗ g)(mn) = (f ∗ g)(m) × (f ∗ g)(n). By definition,

(f ∗ g)(mn) =

X

f (d)g

 mn 

d|mn

d

.

Let d be a divisor of mn. Since m and n are relatively prime, we should be able to express d in the form ab, where a is a divisor of m and b is a divisor of n. To isolate these factors a and b, we can use prime factorization, but instead, we will use the gcd function. Using prime factorization may seem easier, but it goes against the general philosophy of multiplicative number theory. Resorting to prime factorization in multiplicative number theory is like resorting to coordinates in geometry: Prime factorization can work, but “native” functions, like gcd, tend to reflect, and therefore give a better sense of the main concepts underlying multiplicative number theory, especially in more complicated proofs. This is why we should try to find “coordinate-free” proofs that do not use prime factorization. Let a = gcd(d, m) and b = gcd(d, n). Then a | m and b | n, and m and n are relatively prime, so a and b are also relatively prime. Also, a | d and b | d, so ab | d. We want to prove that d = ab, so we consider the d integer ab .

Th

We know that gcd(d, m) = a. Since ab divides d and a divides m, we can write   m d gcd · ab, · a = a. ab a Taking out a factor of a, we get



gcd

It follows that

d ab

and

m a

d m · b, ab a

are relatively prime.

https://www.coursehero.com/file/13772121/2011WOOT-mntpdf/

4



= 1.

Art of Problem Solving

WOOT 2011–12 Multiplicative Number Theory Similarly, gcd(d, m) = b, so  gcd Then

n d · ab, · b ab b 

gcd It follows that

d ab

and

n b

d n · a, ab b

are relatively prime. Hence,

But d is a divisor of mn, so

d ab

is a divisor of

mn ab .

d ab

 = b.

 = 1.

and

Therefore,

m a d ab

n b

·

=

mn ab

are relatively prime.

= 1, or d = ab.

sh is ar stu ed d vi y re aC s o ou urc rs e eH w er as o. co m

Furthermore, when we write d = ab, the factors a and b are unique. Let a1 , a2 , b1 , and b2 be positive integers such that a1 | m, a2 | m, b1 | n, b2 | n, and d = a1 b1 = a2 b2 . Since m and n are relatively prime, a1 and b2 are relatively prime. Therefore, a1 divides a2 . But by the same reasoning, a2 and b1 are relatively prime, so a2 divides a1 . Hence, a1 = a2 , and b1 = b2 . Since we can write any factor d of mn uniquely in the form ab, where a divides m and b divides n, we can write the sum above as  mn   mn  X X X = f (ab)g . (f ∗ g)(mn) = f (d)g d ab a|m b|n

d|mn

Since f is multiplicative, and a and b are relatively prime, f (ab) = f (a)f (b). Similarly, g is multiplicative, n mn m n and m a and b are relatively prime, so g( ab ) = g( a )g( b ). Hence,  mn  X X m n XX f (ab)g = f (a)f (b)g g ab a b a|m b|n a|m b|n     n m X X ×  f (b)g = f (a)g a b b|n

a|m

= (f ∗ g)(m) × (f ∗ g)(n).

We conclude that f ∗ g is multiplicative.



Comment. If f and g are completely multiplicative, f ∗ g is not necessarily completely multiplicative.

Th

Corollary. If f is multiplicative, then the function F defined by X F (n) = f (d) d|n

is also multiplicative.

Proof. The given formula for F (n) looks a lot like convolution. In fact, since 1(n) = 1 for all positive integers n, we can write the sum as n X F (n) = f (d)1 . d d|n

https://www.coursehero.com/file/13772121/2011WOOT-mntpdf/

5

Art of Problem Solving

WOOT 2011–12 Multiplicative Number Theory We recognize this sum as the convolution of the functions f (n) and 1(n). Hence, F = f ∗1. We are given that the function f (n) is multiplicative, and the function 1(n) is multiplicative, so by Theorem 1, the function F (n) is also multiplicative.  We can also prove a converse of Theorem 1. Theorem 2. If g and f ∗ g are multiplicative, then f is also multiplicative. Proof. We want to prove that f (mn) = f (m)f (n)

(†)

for all relatively prime positive integers m and n. We prove this by strong induction on mn.

sh is ar stu ed d vi y re aC s o ou urc rs e eH w er as o. co m

Since g and f ∗ g are multiplicative, g(1) = 1 and (f ∗ g)(1) = 1. But (f ∗ g)(1) = f (1)g(1), so f (1) = 1. Hence, (†) holds for the base case mn = 1. Assume that (†) holds for all relatively prime positive integers m and n such that 1 ≤ mn ≤ k, for some positive integer k. Let m and n be relatively prime positive integers such that mn = k + 1. Then  mn  X (f ∗ g)(mn) = f (d)g d d|mn  mn  X f (d)g = f (mn) + . d d|mn, d 1 be pe11 pe22 · · · pekk . Since τ is multiplicative, τ (n) = τ (pe11 pe22 · · · pekk ) = τ (pe11 )τ (pe22 ) · · · τ (pekk ) = (e1 + 1)(e2 + 1) · · · (ek + 1).

6

sh is ar stu ed d vi y re aC s o ou urc rs e eH w er as o. co m

You are probably already familiar with this formula. The main point of this example is to show how multiplicative number theory can be used to derive formulas. In class, we will demonstrate how multiplicative number theory can provide quick proofs of other, more interesting formulas and identities.

Exercises

1. Prove that for any arithmetic functions f , g, and h,

(f ∗ g) ∗ h = f ∗ (g ∗ h).

2. Prove that if f is multiplicative, then f (a)f (b) = f (gcd(a, b))f (lcm(a, b)) for all positive integers a and b. 3. Prove that for any positive integers a and b,

ab = gcd(a, b)lcm(a, b),

without using prime factorization.

4. Show that for any function f , there exists a function g such that n X

f (gcd(k, n)) = (f ∗ g)(n)

k=1

for all positive integers n.

Th

5. Let f and g be two multiplicative functions. Show that the function defined by X h(n) = f (a)g(b), lcm(a,b)=n

where the sum is taken over all ordered pairs of positive integers (a, b) such that lcm(a, b) = n, is a multiplicative function.

6. Let f be an arithmetic function such that f (1) 6= 0. Show that (f ∗ f )(n) = τ (n)f (n) for all positive integers n if and only if f is completely multiplicative. (American Mathematical Monthly, E2268)

https://www.coursehero.com/file/13772121/2011WOOT-mntpdf/

9 Powered by TCPDF (www.tcpdf.org)