Please enable JavaScript.
Coggle requires JavaScript to display documents.
Number Theoretic Functions (τ(n) := number of divisors of n (Observations.…
Number Theoretic Functions
τ(n) := number of divisors of n
Observations.
Let p, q be distinct primes. Let ki be a natural number
τ(p^k) = k+1
τ(pq) = 4
τ(p^k q^m) = (k+1)(m+1)
τ(p1^k1p2^k2 · · · pn^kn) = (k1+1)(k2+2) · · · (kn+1)
Q: Is τ(n) product preserving?
A: No. Consider τ(50).
τ(50)= 6 ≠ 8 = τ(5)τ(10)
τ(n) is multiplicative.
Example:
τ(50) = 6 = τ(2)τ(25)
Theorem: Let n = p1^k1p2^k2 · · · pn^kn be the prime factorization of n by FTA. Then the divisors of n are integers of the form
d = p1^a1p2^a2 · · · pn^an
with
0 ≤ a1 ≤ k1
0 ≤ a2 ≤ k2
...
0 ≤ am ≤ km
Corollary 1: The number of divisors of n is τ(n) = Πp1^k1p2^k2 · · · pm^km
Corollary 2: τ(n) is multiplicative
ω(n) := number of distinct prime factors of n
σ(n) := sum of divisors of n
Examples
σ(6) = 1+ 2 + 3 + 6 = 12
σ(5) = 1+5 = 6
φ(n) := Euler's phi function; counts the number of natural numbers a < n such that gcd(a,n) = 1
P(n) := Partition function; number of ways n can be written as a sum of natural numbers
π(n) := number of primes ≤ n
Ω(n) := number of total prime factors of n
General Properties of Functions:
(0) f(a+b) = f(a) + f(b) (LINEARITY)
(i) f(ab) = f(a)f(b) if gcd(alb) = 1 (MULTIPLICATIVE
(n) f(ab) = f(a)f(b) (PRODUCT PRESERVING)