MULTIPLICATIVE

FUNCTIONS
GROUP 5
Castillo, Roselle
De Guzman, Kimberly
Gerente, Princess Jane
Maranan, Marineth
Mortella, Kim Jamaica
MULTIPLICATIVE FUNCTION

A multiplicative function f satisfies both f(1) = 1 and f(ab)

= f(a)f(b) for any pair of positive coprime integers a & b. A
multiplicative function is a specific type of arithmetic
function, which has natural numbers as inputs and complex
numbers as outputs. Euler’s phi function is multiplicative.
 What Is A Multiplicative Function?
A multiplicative function f:N→C satisfies the following
properties: ● f(1) = 1 ● f(ab) = f(a)f(b) when a and b are
coprime (that is, a and b share no common factor besides 1)

Multiplicative function euler's phi function. A multiplicative

function satisfies f(1) = 1 and f(ab) = f(a)f(b) for all positive
coprime pairs a and b
 A multiplicative function is a type of arithmetic function. This
means it has only positive integers (natural numbers) as inputs,
and it only has complex numbers as outputs.

Example 1: Multiplicative Function f(n) = 1

The constant function f(n) = 1 is multiplicative, since we can show that the two
properties are satisfied.
First Property: ● f(1) = 1
Second property:
● f(ab) = 1*1
● f(ab) = f(a)*1
● f(ab) = f(a)*f(b)
Example 2: Multiplicative Function f(n) = n
The identity function f(n) = n is multiplicative, since we can show that the
two properties are satisfied.

First property: ● f(1) = 1

Second property:
● f(ab) = ab
● f(ab) = f(a)*b
● f(ab) = f(a)*f(b).
Thus, both of the necessary properties are satisfied. So, the function f(n) = n
is multiplicative (in fact, it is completely multiplicative).
Example 3: Multiplicative Function f(n) = nk
The power function f(n) = nk is multiplicative, since we can show that the
two properties are satisfied.
First property: ● f(1) = 1k = 1
Second Property: ● f(ab) = (ab)k
● f(ab) = akbk
● f(ab) = f(a)*bk
● f(ab) = f(a)*f(b) .
Thus, both of the necessary properties are satisfied. So, the function f(n) =
nk is multiplicative (in fact, it is completely multiplicative).
Example 4: Non-Multiplicative Function f(n) = 2
The constant function f(n) = 2 is non-multiplicative, since we can show that
it fails the first property: ● f(1) = 2 Thus, f(1) is not equal to 1, and so the
function is not multiplicative.The same is true for any function where f(1) is
not equal to 1.

Example 5: Non-Multiplicative Function f(n) = 2n – 1

The polynomial function f(n) = 2n – 1 is non-multiplicative. It satisfies the first
property, but fails the second:
● f(1) = 2(1) – 1 = 1 while:
● f(a)f(b) = (2a – 1)(2b – 1)
● f(a)f(b) = 4ab – 2a – 2b + 1 .If these two were equal, then we would get:
 ● 2ab – 1 = 4ab – 2a – 2b + 1
● 0 = 2ab – 2a – 2b + 2
● 0 = ab – a – b + 1
● 0 = a(b – 1) – (b – 1)
● 0 = (a – 1)(b – 1)

This implies either a = 1 or b = 1 (or both). In any case, the second property
is not satisfied for any values a and b where both are not 1. So, the function
f(n) = 2n – 1 is not multiplicative.
How Do You Know If A Function Is Multiplicative?
● First of all, the graph of a multiplicative function will pass through the point
(1, 1), since it must satisfy f(1) = 1. However, this condition alone is not enough
to ensure a multiplicative function.
● This helps us to find some of the non-multiplicative functions, which do not
pass through (1, 1). However, the graph of a multiplicative function is neither
defined nor continuous on the real numbers, since we only allow natural
numbers (positive integers) as inputs.
● After testing the first property to easily rule out a function, the only way to
know for sure if a function is multiplicative is to test the second property:
● f(ab) = f(a)f(b) when a and b are coprime
● It is impossible to check this for all coprime integer pairs a and b, so we need
to prove it in general.
How To Prove A Function Is Multiplicative
● To prove a function is multiplicative, we must show that f(ab) = f(a)f(b)
for any coprime pair of integers a and b.

1. The best way to do this is to start by looking at the left side. Figure out
what it looks like – what can you change or simplify?
2. Next, look at the right side and figure out what it looks like. What can you
change or simplify
3.Then, compare the two sides and think about how to show they are the
same?
Remember some of the methods we used in earlier examples:
- the constant value of a function for f(n) = 1
- the rules of exponents for f(n) = nk

5. Basically, use what you know about the function definition and any
operation it introduces (constant, multiplication, power, etc.)
6. Also, consider what it means for two positive integers a and b to be
relatively prime.
EULERS PHI FUNCTION OR
EULER'S TOTIENT
FUNCTION
 EULER PHI FUNCTION:

Euler's phi (or totient) function of a positive integer n

is the number of integers in {1,2,3,...,n} which are
relatively prime to n. This is usually denoted φ(n).

Euler’s φ (phi) Function counts the number of

positive integers not exceeding n and relatively prime
to n.
Ex: ϕ(5)
n=5
n= 5 —---> { 1, 2, 3, 4 }
GCD Relatively Prime

(1,5) = 1 ✓

(2,5) = 1 ✓
ϕ(5) = 4 Therefore, there are 4 positive
(3 5) = 1 ✓ integers that to 5, that are relatively prime
to 5.
(4,5) = 1 ✓
 Ex: ϕ(8)
n=8
n=8 —--> { 1, 2, 3, 4, 5, 6 and 7 }

Relatively
GCD Prime
(1,8) = 1 ✓
(2,8) = 2 ×
(3,8) = 1 ✓
(4,8) = 4 × ϕ(8) = 4 Therefore, there are 4 positive
(5,8) = 1 ✓ integers that to 8, that are relatively prime
to 8.
(6,8) = 2 ×
(7,8) = 1 ✓
 THEOREM :
If p is a prime, then ϕ(p) = (p-1)

Example 1 :
ϕ(41) = (41-1) —-> ϕ(p-1)
= 40
Therefore, there are 40 positive integers that to 41, that are
relatively prime to 41.
Example 2 :
ϕ(31) = (31-1)

= 30

Therefore, there are 30 positive integers not exceeding

31, that are relatively prime to 31.
 THEOREM : Phi function at Prime Power
Let p be a prime and a a positive integer. Then ϕ(p^n - p^n-1).

Example:
ϕ(32) = ϕ(2^5 - 2^5-1) —> ϕ(p^n - p^n-1)
= ϕ(32-16)

= 16
Therefore, there are 16 positive integers not exceeding 32, that are
relatively prime to 32.
Example:
ϕ(5³) = ϕ (5³-5^3-1)
= ϕ ( 125 - 25)
= 100
Therefore, there are 100 positive integers not exceeding 5³,
that are relatively prime to 5³.
THEOREM:
- Let n =
be the prime-power factorization of the positive integer n, then

ϕ(n)= n

Example:
ϕ(n) = n

ϕ(n) = 600

= 600×

= 160
 Example :

ϕ(1000) = (2³×5³)
ϕ(n) = n

= 400
The same answer when we use the 3 rules.
ϕ(1000) = (2³×5³) RULE 3

= ϕ(2³)×ϕ(5³). RULE 1
= ϕ(2³-2^3-1)×ϕ(5³-5^3-1) RULE 2

= 4 × 100
= 400
Therefore, there are 400 positive integers not
exceeding 1000, that are relatively prime to 1000.
The same answer when we use the 3 theorems/rules.

ϕ(600) = ϕ(2³×3×5²)
= ϕ(2³)× ϕ(3)×ϕ(5²)
= ϕ(2³-2^3-1) × ϕ(3-1)×ϕ(5²-5^2-1)
= 4×2×20
=160
Therefore, there are 160 positive integers not
exceeding 600, that are relatively prime to 600.
PROVE THE THEOREM : a^ϕ(n) = 1 mod n
1. Euler's Theorem hold true for a = 3 and n=10
Solution :
= 3^10 = 1 (mod 10)
ϕ(10) = 2×5
=(2-1)(5-1)
=4
= 3⁴ = 1 mod 10
= 81 = 1 mod 10
Therefore, Euler's Theorem holds true for a=3
and n=10
2. Does Euler's theorem hold true for a=2 and n=10?
Solution:
a^ϕ(n) = 1 mod n
2^ϕ(10) = 1 mod 10
ϕ (10) = 2×5
ϕ(2)×ϕ(5)
ϕ(2-1)×ϕ(5-1)
1×4 2⁴ = 1 mod 10
=4 16 = 1 mod 10
Remainder 6, therefore euler's theorem does not
hold true for a=2 and n=10
LET’S TRY:
1. ϕ(11)
2. ϕ(7000)
3. Does Euler's theorem hold
true for a=2 and n=12
4. ϕ(375)
5. ϕ(240)
ANSWERS:
1. ϕ(11 ) = 11-1
= 10

2. ϕ(7000) = 2³×5³×7
= 7000×(1-½)(1-⅕)(1-1/7)
= 7000×(½)(⅘)(6/7)
= 2700
3. a^ϕ(n) = 1 (mod n)
2⁶= 1 (mod 12)
64 = 1 (mod 12)

4. ϕ(375) = 3×5³
= 375 ×(1-⅓)(1-⅕)
= 375 ×(⅔)(⅘)
= 200
5. ϕ(240) = 2⁴×3×5
= 240 × (1-½)(1-⅓)(1-⅕)
= 240 × (½)(⅔)(⅘)
= 64
The Sum of Divisors Function
The sum of divisors function, denoted by σ(n), is the sum
of all positive divisors of n.
σ(n)= sum of divisors function
σ(n)= sum of the divisors of n
Example:
σ(12)=1,2,3,4,6,12= 28
σ(12)=1+2+3+4+6+12= 28
Definition
The sum of divisors function is given by
𝑛 𝑎+1
𝑃 −1
σ(n)= ∏ 𝑖
𝑃 1 −1
𝑖=1
Example 1:
σ(n) = 180
σ(180)= 𝟐𝟐 𝐱 𝟑𝟐 𝐱 𝟓
σ(180)=
σ(180)=
σ(180)= 7 x 13 x 6
P1= 2
σ(180)= 546
P2= 3
P3= 5
Example 2:
σ(n)= 360
σ(360)= 𝟐𝟑 𝐱 𝟑𝟐 𝐱 𝟓
σ(360)=
𝟏𝟓 𝟐𝟔 𝟐𝟒
σ(360)= 𝟏 𝒙 𝟐 𝒙 𝟒
σ(360)= 15 x 13 x 6
P1= 2
σ(360)= 1170
P2= 3
P3= 5
Let’s Try
𝟏 .𝟏𝟎𝟎=𝟓𝟐 𝐱 𝟐𝟐
𝟐.𝟑𝟔𝟎𝟎=𝟐𝟒 𝒙 𝟑𝟒 𝒙 𝟓𝟐
𝟏 .𝟏𝟎𝟎=𝟓𝟐 𝐱 𝟐𝟐
Sum of divisors =

𝟓 𝟑 −𝟏 𝟐 𝟑 −𝟏
¿ 𝒙
𝟒 𝟏
𝟏𝟐𝟒 𝟕
¿ 𝒙
𝟒 𝟏
= 217
𝟐.𝟑𝟔𝟎𝟎=𝟐𝟒 𝒙 𝟑𝟒 𝒙 𝟓𝟐
Sum of divisors = x

𝟐 𝟓 −𝟏 𝟑𝟓 − 𝟏 𝟓 𝟑 −𝟏
¿ 𝐱 𝐱
𝟏 𝟐 𝟒
𝟑𝟏 𝟐𝟔 𝟏𝟐𝟒
¿ 𝐱 𝐱
𝟏 𝟐 𝟒
= 12, 493
Number of Divisors Function
The number of divisors function, denoted by (n), is the
counts of the number positive divisors of n.
or d= number of divisors function
(n)= number of the divisors of n
Example:
(8)
d: or (8)= 1,2,4,8
(8)=4
 (1)=1; (2)=2; (3)=2; (4)=3; (5)=2; (6)=4
Remark:

If p is prime (p)=2
()= 1,2, ,……
()= n+1
 n= ……..
(n)=(+1)(+1)……..(+1)

In general

(n)= +1)
Example:
(n) = 180
(180) = x x 5
(180) = (2+1)(2+1)(1+1)
(180) = (3)(3)(2)
(180)= 18
Let’s Try
1. (360)
2. (540)
3. (120)
Answer:
1. (360)= x x 5
(360)=(3+1)(2+1)(1+1)

(360)=(4)(3)(2)

(360)= 24
Answer:
2. (540) = x x 5
(540) = (2+1)(3+1)(1+1)

(540) = (3)(4)(2)

(540) = 24
Answer:
3. (120) = x 3 x 5

(120) = (3+1)(1+1)(1+1)
(120) = (4)(2)(2)

(120) = 16
THANK
YOU!