I came across this thread today, where the OP was attempting to solve a problem regarding counting divisors. Here, the use of a multiplicative function provided means to optimize when counting divisors for larger numbers.

First, let's define two terms- multiplicative and completely multiplicative. A multiplicative function f is one such that if n = pq, where p and q are relatively prime, then f(n) = f(p)f(q). A completely multiplicative function f does not rely on the factors of n being relatively prime. So if f is completely multiplicative and n = pq, then f(n) = f(p)f(q).

Let's examine the multiplicative function in question- the Tau function, also known as the number of divisors function. It is defined as follows: Tau(n) = Sum_{d|n} 1. Another definition is if n = p^{a}q^{b}r^{c} ..., then Tau(n) = (a+1)(b+1)(c+1)....

Before showing how the Tau function is useful here, I want to first detour with an argument for why it is a multiplicative, but not completely multiplicative function. This will provide some insight as to how to use it, as well as indulge the inner mathematician in me.

First, consider n = pq, and a|p or a|q. Thus, it follows that a|n. So it stands to reason that if a is counted under Tau(p) or Tau(q), it should be counted once under Tau(n). However, if p and q are not relatively prime, then a will be counted twice under Tau(p) and Tau(q). Thus, it would follow that if p and q are not relatively prime, then Tau(n) != Tau(p)Tau(q), so it isn't completely multiplicative.

Consider if a|p and !(a|q) (a does not divide q), and !(b|p) and b|q. So a uniquely divides p, and b uniquely divides q. Thus, a|n and b|n. So both must be counted under Tau(n). If p and q are relatively prime, there won't exist a k such that k|p and k|q, so no factors of n will be double counted. Thus, by a combinatorial argument, Tau(n) = Tau(p)Tau(q) only when p and q are relatively prime, which satisfies the definition of a multiplicative function.

Applying this to the problem at hand, it is easy to calculate Tau(n) for small n. Multiplying together those relatively prime values n₁ * n₂ ... * n_i and the results of Tau(n₁) * Tau(n₂)... * Tau(n_i) = Tau(n₁ * n₂ ... * n_i). Thus, it should be possible to more quickly determine the number of factors for larger n.