Download Elementary Number Theory
Transcript
4
20 October
4.1
Arithmetic Functions
An arithmetic function is just a function from N into R (or even more generally, into the complex
numbers C). Equivalently, it can be pictured as an infinite sequence in R or C, indexed by the
natural numbers.
We say that an arithmetic function f : N → R is multiplicative iff, for all coprime m, n ∈ N,
we have
(52)
f (mn) = f (m)f (n).
We say that f is totally multiplicative iff (52) holds even without the assumption that m and
n are coprime. In general, we really only ever care about arithmetic functions when they’re
multiplicative or totally multiplicative.
Example 4.1. Here is a bestiary of multplicative arithmetic functions in number theory:
1. The constant function that sends every natural number to 1.
2. The Euler totient function ϕ defined by
(53)
ϕ(n) = #{a ∈ N : a ≤ n and gcd(a, n) = 1}.
By Exercise 15,
(54)
ϕ(n) = #(Z/nZ)× ,
so ϕ is multiplicative by Cor. 3.3 of the Chinese Remainder Theorem. It is not totally
multiplicative because ϕ(4) = 2 but ϕ(2) = 1.
3. Fix k ≥ 0. The kth-power divisor function σk is defined by
X
(55)
σk (n) =
dk ,
d|n
where the sum runs over positive divisors of n. For example, σ0 computes the number of
positive divisors of n, whereas σ1 computes their sum. For this reason, σ0 is called the
divisor-counting function, whereas σ1 is called simply the divisor function and alternatively
denoted σ.
4. Fix a prime p. If a ∈ Z, then we say that a is a quadratic residue (QR) modulo p if a ≡ b2
(mod p) for some b ∈ Z, and we say that a is a quadratic non-residue (QNR)
modulo p
otherwise. We define the Legendre symbol of conductor p to be the function
·
p
such that:
+1 a 6≡ 0 and a is a QR modulo p
a
−1 a 6≡ 0 and a is a QNR modulo p
(56)
=
p
0
a ≡ 0 (mod p)
Despite the awful notation, ap does not mean the rational number a/p. When we discuss
the Legendre symbol in person, we usually pronounce ap as “the Legendre symbol of a
over p” or “a on p.” In Exercise 24, we’ll show that it is totally multiplicative as a function
of a.
18