Chapter 2

Question 1

coprime

Answer 1

Two integers n and m are coprime in ℤ if their only common factors are 1 and -1

Question 2

multiplicative

Answer 2

The function f: ℕ -> ℂ is multiplicative if f(nm)=f(n)f(m) where n and m are coprime

Question 3

Theorem II.1.1

Answer 3

Suppose that n and m are coprime natural numbers. The the numbers de as d ranges over the +ve factors of n and e ranges over the -ve factors of m is a complete list of the factors of nm with no repetition.

Question 4

τ(n)

Answer 4

the number of positive factors of n

Question 5

σ(n)

Answer 5

the sum of the positive factors of n

Question 6

Φ(n)

Answer 6

The number of numbers in the range 1,..,n that are coprime to n

Question 7

proof τ(n) is multiplicative.

Answer 7

follows from theorem II.1.1 τ(n)τ(m) = d*e = de = τ(nm)

Question 8

You can factorise n as…

Answer 8

n = p₁ʳ¹p₂ʳ²…pₙʳⁿ where all the ps are distinct primes

Question 9

f̂

Answer 9

Let f:ℕ -> ℂ be a function and let n∈ℕ. then
Σ d|n f(d) is defined as
f(d₁) + f(d₂) + … + f(dₖ)

Question 10

Lemma II.2.1. f f̂

Answer 10

suppose that f: ℕ -> ℂ is a function. Define f̂: ℕ -> ℂ. Then if f is multiplicative so if f̂.

Question 11

Theorem II.2.2 The sigma function.

Answer 11

(i) the sigma function is multiplicative
(ii) if n=p₁ʳ¹p₂ʳ²…pₙʳⁿ with distinct ps then
σ(n)= (p₁ʳ¹⁺¹-1)/p₁ …. (pₙʳⁿ⁺¹-1)/pₙ

Question 12

Mobius function

Answer 12

The mobius function μ: ℕ -> ℂ is given by

μ(n) = {1 if n=1, 0 if p²|n for some prime p, (-1)ᵏ if n = p₁p₂…pₙ with all distinct primes

Question 13

Lemma II.3.1

Answer 13

The mobius function is multiplicative

Question 14

Lemma II.3.2

Answer 14

Suppose that n∈ℕ then Σ d|n μ(d) = {1 if n=1, 0 if n>1

Question 15

If p is prime then μ(p) is

Answer 15

-1 (only 1 distinct prime)

Question 16

Theorem II.4.1. Mobius Inversion Formula.

Answer 16

Let f : ℕ -> ℂ be a function. Then

f(n) = Σ d|n μ(d) f̂(n/d)

Question 17

Lemma II.4.2. h is multiplicative

Answer 17

Suppose that f and g:ℕ -> ℂ are multiplicative. Define h:ℕ -> ℂ by
h(n) = Σ d|n f(d) g(n/d)
Then h is multiplicative

Question 18

Euler Phi function

Answer 18

We define the Euler function Φ: ℕ -> ℂ by

Φ(n) = the number of numbers in the range 1,…,n that are coprime to n

Question 19

if p is prime then Φ(p) =

Answer 19

p-1

Question 20

Theorem II.5.1. Φ function

Answer 20

(i) Φ is multiplicative
(ii) n = Σ d|n Φ(n). Φ hat (n)=n.
(iii) Φ(n) = Σ d|n μ(d)n/d
(iv) if p is prime then Φ(pʳ) = pʳ - pʳ⁻¹ = pʳ⁻¹(p-1)
(v) if n=p₁ʳ¹p₂ʳ²…pₖʳᵏ with p distinct primes then
Φ(n)= n(1-1/p₁)(1-1/p₂)…(1-1/pₖ)