The Hidden Connections Between the Totient, Sigma, Tau, Möbius, and Dirichlet Convolution

The Hidden Connections Between Totient, Sigma, Tau, Möbius, and Dirichlet Convolution

In number theory, certain functions show how integers interact with their divisors. This post introduces five of them — the Euler totient function phi(n), the sum of divisors sigma(n), the number of divisors tau(n), the Möbius function mu(n), and the Dirichlet convolution — using one example number:

Example number: n = 12

1) Euler’s Totient Function φ(n)

Idea: phi(n) counts how many numbers from 1 to n are coprime to n (that is, share no common factors with n except 1).

Formula: If n = p1^a1 * p2^a2 * ... * pk^ak, then

phi(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)

Example with n = 12: 12 = 2^2 * 3^1

phi(12) = 12 * (1 - 1/2) * (1 - 1/3) = 12 * (1/2) * (2/3) = 4

The numbers 1, 5, 7, and 11 are coprime to 12, so phi(12) = 4.

2) The Sigma Function σ(n)

Idea: sigma(n) is the sum of all positive divisors of n.

Formula: If n = p1^a1 * p2^a2 * ... * pk^ak, then

sigma(n) = [(p1^(a1+1) - 1) / (p1 - 1)] * [(p2^(a2+1) - 1) / (p2 - 1)] * ... * [(pk^(ak+1) - 1) / (pk - 1)]

Example with n = 12:

sigma(12) = [(2^3 - 1) / (2 - 1)] * [(3^2 - 1) / (3 - 1)] = (7) * (4) = 28

The divisors of 12 are 1, 2, 3, 4, 6, 12, and their sum is 28. So sigma(12) = 28.

3) The Tau Function τ(n)

Idea: tau(n) counts how many positive divisors n has.

Formula: If n = p1^a1 * p2^a2 * ... * pk^ak, then

tau(n) = (a1 + 1) * (a2 + 1) * ... * (ak + 1)

Example with n = 12: 12 = 2^2 * 3^1 tau(12) = (2 + 1) * (1 + 1) = 3 * 2 = 6

The divisors of 12 are 1, 2, 3, 4, 6, and 12. There are 6 in total, so tau(12) = 6.

4) The Möbius Function μ(n)

Idea: mu(n) helps detect whether a number has repeated prime factors.

Definition:

  • mu(1) = 1
  • mu(n) = 0 if n has a squared prime factor
  • mu(n) = (-1)^k if n is a product of k distinct primes

Example with n = 12: 12 = 2^2 * 3. Because 12 has a squared factor (2^2), mu(12) = 0.

5) Möbius Inversion Formula

Idea: Sometimes one function (g) is the sum of another function (f) over the divisors of n. If g(n) = Σ f(d) for all d dividing n, the Möbius inversion formula lets us recover f from g.

Formula:

f(n) = Σ mu(d) * g(n / d), summed over all d dividing n.

This means mu acts like an “inverse” for divisor sums.

6) Dirichlet Convolution

Definition: For two arithmetic functions f and g, their Dirichlet convolution is defined as:

(f * g)(n) = Σ f(d) * g(n / d), summed over all d dividing n.

Examples of how these functions relate:

sigma(n) = id * 1 tau(n) = 1 * 1 phi(n) = id * mu

where "id(n)" means the identity function id(n) = n, and "1(n)" means the constant function that always equals 1.

7) Checking the Relationships for n = 12

Check that sigma = id * 1. Divisors of 12: 1, 2, 3, 4, 6, 12.

(id * 1)(12) = 1*1 + 2*1 + 3*1 + 4*1 + 6*1 + 12*1 = 28 That matches sigma(12) = 28.

Check that phi = id * mu. We will make a small table:

d12/dmu(12/d)d * mu(12/d)
11200
2612
3400
43-1-4
62-1-6
121112

Sum = 0 + 2 + 0 - 4 - 6 + 12 = 4 That matches phi(12) = 4.

8) Summary Table

FunctionMeaningFormulan=12
phi(n)Count of numbers coprime to nphi(n) = n * Π (1 - 1/p)4
sigma(n)Sum of divisorssigma(n) = Π [(p^(a+1) - 1)/(p - 1)]28
tau(n)Number of divisorstau(n) = Π (a + 1)6
mu(n)Detects squared primesmu(1)=1; mu(n)=0 if any p^2 divides n; else (-1)^k0

These relationships show how number theory ties together through divisor functions. The Möbius function “undoes” divisor sums, and the Dirichlet convolution “combines” functions in a structured way. Even with n = 12, we can see the elegance in how these mathematical ideas connect.

Comments

Post a Comment

Popular posts from this blog

What is Mathematical Fluency?

What does it really mean for students to be mathematically fluent? If you’ve been in any math PD over the past few years, you’ve likely heard the phrase everywhere. We talk about fluency as something students should develop, strengthen, and demonstrate, but it can still feel abstract when we try to describe it in observable, classroom-ready terms. This post breaks down mathematical fluency into the two simplest frames we can use as teachers: what it looks like and what it sounds like . These descriptions can guide instruction, assessment, student goal-setting, and even walkthrough conversations with colleagues or administrators. What Mathematical Fluency Looks Like In a classroom where students are developing mathematical fluency, you see students making choices about strategies rather than following steps robotically. They use representations—number lines, diagrams, tables, graphs, manipulatives, symbolic expressions—and switch between them to make sense of a problem. They move ...
Read more

Unlocking the Group: Cosets, Cayley’s Theorem, and Lagrange’s Theorem

Mathematics is full of elegant ideas that take simple definitions and build deep, powerful structures. In group theory, three such concepts—cosets, Cayley's Theorem, and Lagrange’s Theorem—form a foundational trio that unveils the internal symmetry of algebraic systems. Let’s explore what they mean and why they matter. What’s a Coset, Really? Imagine you have a group and a smaller subgroup inside it. Now, pick any element from the big group and use it to shift every element in the subgroup by multiplying on the left. The resulting set is called a left coset . You can also do this multiplication on the right, forming a right coset . These cosets aren’t usually groups themselves—but they do break the original group into equal-sized, non-overlapping pieces. Intuitively , cosets act like “shifts” of the subgroup across the whole group. Think of tiling a floor: each tile is a copy of the same shape (the subgroup) placed in different locations (cosets). Lagrange’s Theorem: Size Matt...
Read more

Verifying the Binomial Formula with Mathematical Induction

The binomial formula states: ( z 1 + z 2 ) n = ∑ k = 0 n ( n k ) z 1 n − k z 2 k (z_1 + z_2)^n = \sum_{k=0}^n \binom{n}{k} z_1^{n-k} z_2^k where ( n k ) = n ! k ! ( n − k ) ! \binom{n}{k} = \frac{n!}{k!(n-k)!} and n = 1 , 2 , … n = 1, 2, \ldots . This is a powerful formula in algebra, expressing the expansion of ( z 1 + z 2 ) n (z_1 + z_2)^n as a sum of terms involving powers of z 1 z_1 and z 2 z_2 . We’ll verify this formula using mathematical induction . Mathematical induction is a logical method to prove that a statement holds for all positive integers n n . The process involves two steps: Base Case : Verify the formula for the smallest value of n n , typically n = 1 n = 1 . Inductive Step : Assume the formula holds for some n = k n = k , and then prove it holds for n = k + 1 n = k+1 . Step 1: Base Case ( n = 1 n = 1 ) For n = 1 n = 1 , the formula becomes: ( z 1 + z 2 ) 1 = ∑ k = 0 1 ( 1 k ) z 1 1 − k z 2 k (z_1 + z_2)^1 = \sum_{k=0}^1 \binom{1}{k} z_1^{1-k} z_2^k L...
Read more