NUMBER
THEORETIC
FUNCTIONS
PRIME FACTORIZATION
Find the prime factorization of
the following integers.
1. 27 6.243
2. 72 7. 125
3. 54 8. 180
4. 36 9. 144
5. 96 10. 243
Definition:
A number theoretic function
is a special function whose
domain covers on the set of
positive integers.
𝜏 (𝑛) – symbol for the number of
positive divisors of n
𝜎 (𝑛)– symbol for the sum of
positive divisors of n
Definition:
Given a positive integer n,
then we shall denote the number
of positive divisors of n by 𝝉(𝒏)
and the sum of divisors of n
by 𝝈 𝒏 .
I. When n = p
𝛼
II. When n = 𝑝 , where p is prime
III. When
Definition:
Let f(n) be an arithmetic
function such that
f(ab) = f(a)f(b),
for every pair a, b satisfying
(a,b)=1, then f(n) is said to be
multiplicative.
Theorem:
The functions 𝝉 and 𝜎
are both multiplicative functions.
PROBLEM SET
I. Find the canonical form of the
following integers.
1. 720
2. 2,079
3. 4,400
4. 4,408
5. 14,553
PROBLEM SET
II. Find the number of positive
divisors and the sum of the positive
divisors of the following integers.
1. 81
2. 100
3. 1,656
4. 14,553
5. 16,200
PERFECT NUMBER
An integer n is called
a perfect number
if σ(n) = 2n.
ABUNDANT NUMBER
An integer n is called
an abundant number
or excessive number
if σ(n) > 2n.
DEFICIENT NUMBER
An integer n is called
a deficient number
if σ(n) < 2n.
Definition:
Let n be a positive integer.
The Euler phi-function ϕ (n) is
defined to be the number of
positive integers not
exceeding n which are
relatively prime to n.
GROUP I
1.5
2.7
3.11
4.23
5.43
GROUP II
1.9
2.16
3.25
4. 32
5.49
GROUP III
1.6
2.15
3.24
4. 96
5.108
Case 1: p is prime
ϕ (p) = p-1
Case 2: If p is prime, then
ϕ (p α) = p α – p α -1
= (p )(p-1)
α -1
Theorem: If (a,b) = 1 then
ϕ(ab) = ϕ(a)ϕ(b).
Case 3: If n>1 has a canonical
form
n = p1 p2 ….pk k
α1 α2 α
ϕ(n) = (p1α1-1)(p1-1)•(p2α2-1)(p2-1)•••
(pkαk-1)(pk-1)
ϕ(n) = (p1α1-p1α1-1)•(p2α2-p2α2-1)•••
(pkαk-pkαk-1)
ϕ(n) = p1α1(1-1/p1)p2α2(1-1/p2)•••
pkαk(1-1/pk)
ϕ(n) = p1α1(1-1/p1)p2α2(1-1/p2)•••
pkαk(1-1/pk)
ϕ(n) = p1α1 • p2α2 • pkαk • (1-1/p1) •
(1-1/p2)•(1-1/pk)
ϕ(n) = n • (1-1/p1) • (1-1/p2)•(1-1/pk)
PROBLEM SET
Evaluate:
1. ϕ(48) 6. ϕ(147)
2. ϕ(56) 7. ϕ(152)
3. ϕ(85) 8. ϕ(200)
4. ϕ(92) 9. ϕ(324)
5. ϕ(102) 10. ϕ(16,000)
