Möbius Function Calculator

Instantly compute the Möbius function μ(n), explore its properties, and visualize the related Mertens function with this powerful number theory tool.

"Mathematics is the queen of the sciences and number theory is the queen of mathematics." - Carl Friedrich Gauss

💻 Code Implementations

Here’s how you can implement the Möbius function in Python and Java. These are common challenges in competitive programming platforms like Codeforces and are central to many CP algorithms.

Möbius Function in Python


def get_prime_factorization(n):
    factors = {}
    d = 2
    temp = n
    while d * d <= temp:
        while temp % d == 0:
            factors[d] = factors.get(d, 0) + 1
            temp //= d
        d += 1
    if temp > 1:
        factors[temp] = factors.get(temp, 0) + 1
    return factors

def mobius_function(n):
    if n == 1:
        return 1
    
    factors = get_prime_factorization(n)
    
    for p in factors:
        if factors[p] > 1:
            return 0  # Has a squared prime factor
            
    # Product of k distinct primes
    k = len(factors)
    return (-1)**k

# Example
print(f"μ(30) = {mobius_function(30)}")
# Output: μ(30) = -1

Möbius Function in Java


import java.util.HashMap;
import java.util.Map;

public class MobiusFunction {

    public static int calculate(int n) {
        if (n == 1) {
            return 1;
        }

        Map primeFactors = new HashMap<>();
        int temp = n;
        for (int i = 2; i * i <= temp; i++) {
            while (temp % i == 0) {
                primeFactors.put(i, primeFactors.getOrDefault(i, 0) + 1);
                if (primeFactors.get(i) > 1) {
                    return 0; // Squared prime factor
                }
                temp /= i;
            }
        }
        if (temp > 1) {
            primeFactors.put(temp, 1);
        }

        // Number of distinct prime factors
        int k = primeFactors.size();
        return (k % 2 == 0) ? 1 : -1;
    }

    public static void main(String[] args) {
        System.out.println("μ(30) = " + calculate(30));
        // Output: μ(30) = -1
    }
}
Ad Space 1 (e.g., 728x90 or Responsive)

🤔 What is the Möbius Function? A Deep Dive

The Möbius function, denoted as μ(n) (or möbius function), is a fundamental multiplicative function in number theory and combinatorics. It's a cornerstone of many advanced concepts, including the famous Möbius inversion formula. Its definition is elegant and depends entirely on the prime factorization of the input integer n.

📜 The Möbius Function Formula

The function μ(n) is defined for all positive integers n and its value can only be -1, 0, or 1. The rules are as follows:

  • 1️⃣ μ(n) = 1 if n is a square-free positive integer with an even number of distinct prime factors. By definition, the Möbius function of 1 is μ(1) = 1 (as it has 0 prime factors, and 0 is even).
  • ➖ μ(n) = -1 if n is a square-free positive integer with an odd number of distinct prime factors.
  • 0️⃣ μ(n) = 0 if n has a squared prime factor (i.e., it is not square-free).

A number is "square-free" if its prime factorization contains no repeated factors. For example, 30 (2 × 3 × 5) is square-free, but 12 (2² × 3) is not.

🧮 Möbius Function Examples

Let's walk through some classic Möbius function examples to make the definition concrete.

  • What is μ(6)?
    • The prime factorization of 6 is 2 × 3.
    • It has two distinct prime factors (2 and 3).
    • Since 2 is an even number, μ(6) = 1.
  • What is μ(10)?
    • The prime factorization of 10 is 2 × 5.
    • It has two distinct prime factors (2 and 5).
    • Since 2 is an even number, μ(10) = 1.
  • What is μ(30)?
    • The prime factorization of 30 is 2 × 3 × 5.
    • It has three distinct prime factors.
    • Since 3 is an odd number, μ(30) = -1.
  • What is μ(12)?
    • The prime factorization of 12 is 2² × 3.
    • It contains a squared prime factor (2²).
    • Therefore, μ(12) = 0.

You can verify all these using our Möbius function calculator above!

Ad Space 2 (e.g., 300x250 or Responsive)

➕ The Sum of Möbius Function Over Divisors

One of the most remarkable properties of the Möbius function relates to summing its values over the divisors of a number n. This property is key to the Möbius inversion formula.

The identity is: Σd|n μ(d) = { 1 if n=1, 0 if n>1 }

This means if you find all divisors of n (including 1 and n), calculate the Möbius function for each divisor, and add them all up, the result will be 0 for any n greater than 1.

Example: Sum for n=10

  • The divisors of 10 are {1, 2, 5, 10}.
  • μ(1) = 1
  • μ(2) = -1 (1 prime factor)
  • μ(5) = -1 (1 prime factor)
  • μ(10) = 1 (2 prime factors: 2, 5)
  • Sum: 1 + (-1) + (-1) + 1 = 0.

🤝 Proof: The Möbius Function is Multiplicative

To prove that the Möbius function is multiplicative is a classic exercise in number theory. A function f is multiplicative if for any two coprime integers a and b (meaning gcd(a, b) = 1), we have f(ab) = f(a)f(b).

Let's consider the cases for μ(ab) where gcd(a, b) = 1:

  1. Case 1: Either a or b has a squared prime factor.
    • If a is not square-free, then μ(a) = 0. Since a and b are coprime, the squared prime factor in a will also be in ab, making ab not square-free. Thus, μ(ab) = 0.
    • The equation holds: μ(ab) = 0 = 0 × μ(b) = μ(a)μ(b). The same logic applies if b is not square-free.
  2. Case 2: Both a and b are square-free.
    • Let a = p₁p₂...pₖ (k distinct primes) and b = q₁q₂...qₘ (m distinct primes). Then μ(a) = (-1)ᵏ and μ(b) = (-1)ᵐ.
    • Since gcd(a, b) = 1, none of the pᵢ primes are the same as any of the qⱼ primes.
    • The product ab will have k + m distinct prime factors.
    • Therefore, μ(ab) = (-1)ᵏ⁺ᵐ.
    • By the laws of exponents, (-1)ᵏ⁺ᵐ = (-1)ᵏ × (-1)ᵐ.
    • This means μ(ab) = μ(a)μ(b).

Since the property holds in all cases, we have successfully proven that the Möbius function is multiplicative.

🌐 Applications and Further Concepts

The Möbius function is not just a mathematical curiosity. It has profound applications:

  • 🔄 Möbius Inversion Formula: Its primary use. It relates a function to the sum of its values over its divisors, and vice-versa. This is used extensively in number theory and combinatorics.
  • 📊 Möbius function poset: The inversion formula can be generalized from integers to partially ordered sets (posets), a powerful concept in algebraic combinatorics.
  • 💻 Competitive Programming: Used in problems involving number theory, divisibility, and inclusion-exclusion principles. A good understanding is essential for solving certain tasks on platforms like Codeforces and for mastering CP algorithms. (A `Möbius function PDF` or tutorial is often a great resource for this).
  • 📈 Mertens Function M(n): The sum of the Möbius function up to n, M(n) = Σ μ(k). Its behavior is related to the distribution of prime numbers and the Riemann Hypothesis.

✅ Conclusion: A Powerful Tool in Number Theory

The Möbius function is a simple-to-define yet incredibly deep concept. From its three basic rules springs a wealth of properties and applications that touch many areas of mathematics and computer science. This Möbius function calculator is designed to be your companion in exploring this fascinating function, whether you're solving a homework problem, tackling a Codeforces challenge, or just satisfying your mathematical curiosity.

Support Our Work

Help keep this advanced calculator free and updated with a small contribution.

Donate via UPI

Scan the QR code for UPI payment in India.

UPI QR Code

Support via PayPal

Contribute securely via PayPal.

PayPal QR Code for Donation
⇧