SMA3043 ELEMENTARY NUMBER THEORY
SEMESTER 1 2022/2023
NUMBER-THEORETIC FUNCTIONS
PROF. MADYA DR ROHAIDAH MASRI
DR. NOR HAFIZAH MD HUSIN
NUMBER-THEORETIC FUNCTIONS
The function and σ
Definition 1
Given a positive integer n, let (n) denote the number of positive divisor of n
and σ(n) denote the sum of these divisor.
Definition 2 (number-theoretic function)
Any function whose domain of definition is the set of positive integers is
said to be a number-theoretic function (or arithmetic function).
2
NUMBER-THEORETIC FUNCTIONS
The function and σ
Example
Let n =12.
Positive divisor of 12: 1, 2, 3, 4, 6, 12,
Then,
(12) = 6 & (12) = 1 + 2 + 3 + 4 + 6 + 12 = 28
Example
Let n =15.
Positive divisor of 15: 1, 3, 5, 15
Then,
(15) = 4 & (15) = 1 + 3 + 5 + 15 = 24
3
NUMBER-THEORETIC FUNCTIONS
The function and σ
Example.
4
NUMBER-THEORETIC FUNCTIONS
Note:
1. (n) = 2 if and only if n is a prime number.
Example: (for the first few integers)
(1) = 2 ; (2) = 2 ; (3) = 2 ; (4) = 3 ; (5) = 2 ; (6) = 4 ; .........
2. (n) = n + 1 if and only if n is a prime number.
Example: (for the first few integers)
(1) = 1 ; (2) = 3 ; (3) = 4 ; (4) = 7 ; (5) = 6 ; (6) = 12 ; .........
5
NUMBER-THEORETIC FUNCTIONS
Summation & Product
Some interpretation of the symbols:
(i) Sum the values f(d) as d runs over all the positive divisors of the
positive integer n
Example:
(ii) and a may be expressed in the form
6
NUMBER-THEORETIC FUNCTIONS
Summation & Product
Some interpretation of the symbols (cont.):
(ii)
7
NUMBER-THEORETIC FUNCTIONS
Summation & Product
Definition 3.
8
NUMBER-THEORETIC FUNCTIONS
Summation & Product
Example.
9
NUMBER-THEORETIC FUNCTIONS
Summation & Product
Example.
10
NUMBER-THEORETIC FUNCTIONS
Number of Positive Divisors & Sum of Divisors
Next theorem makes it easy to obtain the positive divisors of a
positive integer n once its prime factorization is known.
Theorem 1.
If n = p p ... p
k1
1
k2
2
kr
r is the prime factorization of n 1, then the
positive divisors are precisely those integers d of the form,
d = p p ... p
a1
1
a2
2
ar
r
where 0 ai ki ( i = 1, 2, ... , r ) .
11
NUMBER-THEORETIC FUNCTIONS
Number of Positive Divisors & Sum of Divisors
Lemma 1
Let p be a prime and k be a positive integer. Then
1. (p k
) = k +1
k +1
−1
( p ) = 1 + p + p + ... + p =
k 2 k p
2.
p −1
12
NUMBER-THEORETIC FUNCTIONS
Number of Positive Divisors & Sum of Divisors
Proof:
13
NUMBER-THEORETIC FUNCTIONS
Number of Positive Divisors & Sum of Divisors
Example.
14
NUMBER-THEORETIC FUNCTIONS
Number of Positive Divisors & Sum of Divisors
Theorem 2
If n = p p ... p
k1
1
k2
2
kr
r is the prime factorization of n 1, then
(a) ( n ) = ( k1 + 1)( k2 + 1) ... ( kr + 1) , and
k1 +1 k2 +1 kr +1
− 1 p2 − 1
p pr − 1
(b) (n) = 1
...
p1 − 1 p2 − 1 pr − 1
15
NUMBER-THEORETIC FUNCTIONS
Number of Positive Divisors & Sum of Divisors
Example.
16
NUMBER-THEORETIC FUNCTIONS
Number of Positive Divisors & Sum of Divisors
Example.
17
NUMBER-THEORETIC FUNCTIONS
Number of Positive Divisors & Sum of Divisors
Example.
Let n =376.
Then,
18
NUMBER-THEORETIC FUNCTIONS
Number of Positive Divisors & Sum of Divisors
Example.
Let n =180.
Then,
positive divisors.
19
NUMBER-THEORETIC FUNCTIONS
Number of Positive Divisors & Sum of Divisors
Cont..
20
NUMBER-THEORETIC FUNCTIONS
Multiplicative Functions
Multiplicative functions arise naturally in the study of the prime
factorization of an integer.
Observe that:
These calculations bring out the nasty fact that, in general, it need not be true that
21
NUMBER-THEORETIC FUNCTIONS
Multiplicative Functions
Definition 4
A number-theoretic function is called multiplicative if
f ( mn ) = f ( m ) f ( n ) whenever gcd ( m, n ) = 1.
Theorem 3
The functions and are both multiplicative functions.
22
NUMBER-THEORETIC FUNCTIONS
Multiplicative Functions
Proof:
23
NUMBER-THEORETIC FUNCTIONS
Multiplicative Functions
Proof:
24
NUMBER-THEORETIC FUNCTIONS
Multiplicative Functions
Lemma 2
If gcd ( m, n ) = 1, then the set of positive divisors of mn consists
of all products d1d 2 , where d1 | m , d 2 | n and gcd ( d1 , d 2 ) = 1,
futhermore, these products are all distinct.
Theorem 4
If f is a multiplicative function and F is defined by
F (n) = f (d )
d |n
then F is also multiplicative.
25
NUMBER-THEORETIC FUNCTIONS
Multiplicative Functions
Example.
26
NUMBER-THEORETIC FUNCTIONS
The Greatest Integer Function
Function [ ] is called as the greatest integer - to treat divisibility problem.
Definition 5
Let x be arbitrary real numbers. [ x ] is the largest integer less than or equal to x;
that is, [ x ] is the unique integer satisfying
x–1[x]x .
Example.
Note:
Let x = - 3/2
where, [ x ] = x holds if and only if x is an integer
- 2.5 < [ - 1.5 ] -1.5
Then, [-1.5] = -2
27
NUMBER-THEORETIC FUNCTIONS
The Greatest Integer Function
Example.
Let x= 2
where,
0.4 2 = 1.414 1.414
Then = 1
2
Example.
1/ 3 = 0
= 3.142 = 3
− = −3.142 = −4
28
NUMBER-THEORETIC FUNCTIONS
The Greatest Integer Function
Next is to investigate how many times a particular prime p appears in n! .
Example.
Let p = 3 & n = 9 .
A formula that will give this
Then,
count, without the necessity of
9 ! = 1 . 2. 3 . 4 . 5 . 6 . 7 . 8 . 9
writing n! is given in the
= 27 . 34 . 5 . 7
following theorem
Then, the exact power of 3 that divides 9! Is 4 .
29
NUMBER-THEORETIC FUNCTIONS
The Greatest Integer Function
Theorem 5
If n is a positive integer and p is a prime,
then the exponent of the highest power of p that divides n! Is
n
pk
k =1
n
where the series is finite, since k = 0 for p k n.
p
30
NUMBER-THEORETIC FUNCTIONS
The Greatest Integer Function
Example.
Determine the number of times 10 enters into the product 50!
Solution:
It is enough to find the exponent of 2 & 5 in the prime factorization of
50! .
50 50 50 50 50 50
k =1
2k = 21 + 22 + 23 + 24 + 25 + 0 + ...
= 25 + 12 + 6 + 3 + 1 + 0 + .... = 47
By Theorem 5, 247 divides 50! .
50 50 50
Similarly, 5k = 51 + 52 + 0 + ... = 10 + 2 + 0 + .... = 12
k =1
By Theorem 5, 512 divides 50! .
Therefore,
50! ends with 12 zeros.
31
NUMBER-THEORETIC FUNCTIONS
The Greatest Integer Function
Theorem 6
If n and r are positive integers with 1 r n
then, the binomial coefficient
n n!
=
r r ! ( n − r )!
is also an integer.
Corollary 1
For a positive integer r, the product of any r consecutive positive
integers is divisible by r! .
32
NUMBER-THEORETIC FUNCTIONS
The Greatest Integer Function
Example. Note:
7.8.9.10.11 = 55440
Let (7)(8)(9)(10)(11) , where r = 5. Where,
55440 = 5! (462) + 0
Then, by corollary 1,
7.8.9.10.11 is divisible by 5! . Then, 5! | 55440 .
Theorem 7
Let f and F be number-theoretic functions such that F ( n ) = f (d )
d |n
Then, for any positive integer N,
N N
N
n =1
F (n ) = f (k )
k =1 k
33
NUMBER-THEORETIC FUNCTIONS
The Greatest Integer Function
Corollary 2
If N is positive integer, then
N N
N
n =1
(n ) =
n =1 n
Corollary 3
If N is positive integer, then
N N
N
n =1
(n ) = n
n =1 n
34
NUMBER-THEORETIC FUNCTIONS
The Greatest Integer Function
Example. (Corollary 2)
Consider the case N = 6. Note that:
6 (1) : 1 ; (2) : 1, 2; (3) : 1,3 ;
By definition of : ( n ) = (1) + ( 2) + ( 3 ) + ( 4 ) + ( 5 ) + ( 6 ) = 14
n =1
(4) : 1, 2, 4 ; (5) : 1, 5 ;
(6) : 1, 2, 3,6
By Corollary 2 ; 6 6
6
n =1
(n ) =
n =1 n
6 6 6 6 6 6
= + + + + +
1 2 3 4 5 6
= 6 + 3 + 2 + 1 + 1 + 1 = 14
35
NUMBER-THEORETIC FUNCTIONS
The Greatest Integer Function
Example. (Corollary 3)
Consider the case N = 6. Note that:
6 (1) : 1 ; (2) : 1+2 = 3;
By definition of : ( n ) = (1) + ( 2) + ( 3 ) + ( 4 ) + ( 5 ) + ( 6 ) = 33 (3) : 1+3 = 4 ; (4) : 1+ 2+ 4 = 7 ;
n =1
(5) : 1+ 5 = 6 ;
(6) : 1+ 2+ 3+6 =12
By Corollary 3 ;6 6
6
n =1
(n ) = n
n =1 n
6 6 6 6 6 6
= 1 + 2 + 3 + 4 + 5 + 6
1 2 3 4 5 6
= 1.6 + 2.3 + 3.2 + 4.1 + 5.1 + 6.1 = 33
36
NUMBER-THEORETIC FUNCTIONS
Perfect Numbers
Definition 6 (Perfect Number)
If n is a positive integer and (n) = 2n , then n is called as a perfect number.
A positive integer n is called as perfect number if n is equal to the sum of all its positive divisors,
excluding n itself.
Example.
(i) Since (6) = 1 + 2 + 3 + 6 = 12 = 2(6) . Then, 6 is perfect.
(ii) Since (28) = 1 + 2 + 4 + 7 + 14 + 28 = 56 = 2(28) . Then, 28 is perfect.
37
NUMBER-THEORETIC FUNCTIONS
Perfect Numbers
Theorem 8
Let m 2 and 2 − 1 be prime. Then, the positive integer n is
m
an even perfect number if and only if
n=2 m −1
(2 m
− 1)
Example.
Let p = 2, 3, 5, 7 and the values 2p – 1 : 3, 7, 31, 127 are primes
2 (22 – 1 ) = 6
22 (23 – 1 ) = 28
24 (25 – 1 ) = 496
26 (27 – 1 ) = 8128
Where, 6, 28, 496 & 8128 are perfect numbers.
38
NUMBER-THEORETIC FUNCTIONS
Perfect Numbers
Proof ():
39
NUMBER-THEORETIC FUNCTIONS
Perfect Numbers
Proof ():
40
NUMBER-THEORETIC FUNCTIONS
Perfect Numbers
41
NUMBER-THEORETIC FUNCTIONS
Perfect Numbers
42
NUMBER-THEORETIC FUNCTIONS
Perfect Numbers
Lemma 3
If ak – 1 is prime (a > 0 , k 2 ) then a = 2 and k is also prime.
Theorem 9
If m is a positive integer and 2m – 1 is prime, then m must be prime.
43
NUMBER-THEORETIC FUNCTIONS
Perfect Numbers
Proof: (Theorem 9)
44
NUMBER-THEORETIC FUNCTIONS
Perfect Numbers
Theorem 10
An even perfect number n ends in the digits 6 or 8, that is
n 6 ( mod10 ) or n 8 ( mod10 )
Proof:
45
NUMBER-THEORETIC FUNCTIONS
Perfect Numbers
46
NUMBER-THEORETIC FUNCTIONS
Perfect Numbers
47
NUMBER-THEORETIC FUNCTIONS
Mersenne Primes
Definition 7 (Mersenne Primes Numbers)
Example (Mersenne Primes).
Note:
i. M2 = 22 – 1 = 3
M11 = 211 – 1 = 2047 is the 11th Mersenne Number
ii. M3 = 23 – 1 = 7
M11 is composite since M11 = 2047 = 23.89
iii. M13 = 213 – 1 = 8191
48
NUMBER-THEORETIC FUNCTIONS
Mersenne Primes
Next theorem gives us a method for determining whether certain special types
of Mersenne numbers are prime or composite.
Theorem 11
If p and q = 2p + 1 are primes, then either q | Mp or q | Mp + 2,
but not both.
Example.
By using Theorem 11, determine whether:
i. M23 is a prime or composite number.
ii. M11 is a prime or composite number
49
NUMBER-THEORETIC FUNCTIONS
Mersenne Primes
Of the two possibilities q | Mp or q | Mp + 2, it is reasonable to ask:
What conditions on q will ensure that q | Mp?
The following theorem gives some conditions on q such that q | Mp.
Theorem 12
If q = 2n + 1 is a prime, then we have the following:
(a) q | Mn, provided that q 1 (mod 8) or q 7 (mod 8).
(b) q | Mn + 2 , provided that q 3 (mod 8) or q 5 (mod 8).
50
NUMBER-THEORETIC FUNCTIONS
Mersenne Primes
The following corollary gives us an immediate consequence of Theorem 12.
Corollary 4
If p and q = 2p + 1 are both odd prime, with p 3 (mod 4)
Then, q | Mp .
Example. (Corollary 4)
Let p = 11 and q = 2(11) + 1 = 23 are both odd prime.
Note that, 11 3 (mod 4)
Then by corollary 4, 23 | M11 .
51
NUMBER-THEORETIC FUNCTIONS
Mersenne Primes
Note:
The following is a partial list of those prime numbers p 3 (mod 4) where q = 2p + 1
is also a prime :
p = 11, 23, 83, 131, 179, 191, 239, 251
Then, by corollary 4, Mp is composite.
52
NUMBER-THEORETIC FUNCTIONS
Mersenne Primes
Fermat’s Theorem:
The following theorems tackle two results of Fermat that restrict the p prime, aZ+, p | a
divisors of Mp.
Then, ap -1 1 (mod p)
Theorem 13
If p is an odd prime, then any prime divisor of Mp is of the
form 2kp + 1 .
Theorem 14
If p is an odd prime, then any prime divisor q of Mp is of the form
q 1 (mod 8).
53
NUMBER-THEORETIC FUNCTIONS
Mersenne Primes
Theorem 15 (Euler)
If n is an odd perfect number, then
n = p p .... p
k1
1
2 j2
2
2 jr
r
where the pi’s the distinct odd primes and p1 k1 1 (mod 4).
Corollary 5.
If n is an odd perfect number, then n is of the form
n=p m k 2
where the p is a primes and p | m and p k 1 (mod 4).
In particular n 1 (mod 4).
54
