Show that f is multiplicative and evaluate f at prime powers

Question

I'm trying to prove the problem about multiplicative function.

The problem is the following :

Let $f(n) = $ #{($n_1, n_2$) $\in$ $\mathbb{N^2}$ : $lcm$($n_1, n_2) = n$}. Now, prove that $f$ is multiplicative and evaluate $f$ at prime powers.

I don't know where I start with. Does anyone give me the idea for this? The only thing that I found is, it can be a multiplicative function regardless of the choice of $n_1$ and $n_2$, i.e, even if $n_1$ and $n_2$ are not co-primes, it can be the multiplicative function.

Answer 1

Multiplicative: let $m$ and $n$ be relatively prime. If $m_1, m_2, n_1, n_2 \in \Bbb N$ and $\text{lcm}(m_1, m_2) = m$, $\text{lcm}(n_1, n_2)=n$, then $\text{lcm}(m_1n_1, m_2n_2)=mn$ (prove this!). Also, given $x_1, x_2 \in \Bbb N$ with $\text{lcm}(x_1,x_2)=mn$, let $m_1$ be the factor of $x_1$ that contains all the prime factos of $m$, $n_1$ the factor of $x_1$ that contains all the prime factors of $n$, and similarly $m_2, n_2$. Use this to show there is a bijective correspondence between the quadruples $(m_1, m_2), (n_1,n_2)$ that define $f(m)$ and $f(n)$ on the one hand, and the pairs $(x_1, x_2)$ that define $f(mn)$ on the other hand.

$f(p^k)$ - Both $n_1$ and $n_2$ must be powers of $p$, and the greatest exponent must be $k$. A direct count shows that $f(p^k)=2k+1$.

Answer 2

• The set of couples $\qquad (a,b), \ \ lcm(a,b) = n$

  maps bijectively to the set of couples $\ (d,A),\ \ d | n,\ \ A | \frac{n}{d}, \ \ gcd(A,\frac{n}{d A})=1$

  $\qquad $(let $d = gcd(a,b), \ A = \frac{a}{d}, \ B = \frac{b}{d} = \frac{n}{Ad}$)

  so that :

  $$f(n) = \sum_{d | n} \sum_{A | \frac{n}{d}} 1_{gcd(A, \frac{n}{dA}) = 1} $$

• Assuming $$g(n) = \sum_{A | n} 1_{gcd(A, \frac{n}{A}) = 1}$$ is multiplicative, we have that $$f(n) = \sum_{d | n} g(n/d) = \sum_{d | n} g(d)$$ is multiplicative too.

• Show that $n = \prod_{i=1}^k p_i^{e_i} \implies g(n) = 2^k$, i.e. $$g(n) = 2^{\omega(n)}$$ where $\omega(n )$ is the number of distinct prime factors of $n$.

  So it is obvious that $$gcd(n,m) = 1 \quad \implies \quad \omega(nm) = \omega(n)+\omega(m) $$ $$ \implies \quad g(nm) = 2^{\omega(nm)} = 2^{\omega(n)+\omega(m)} = g(n)g(m) $$

• Since $g(1) = 1, g(p^k) = 2$, we have $$f(p^k) = \sum_{d | p^k} g(d) = \sum_{m=0}^k g(p^m) = 1+\sum_{m=1}^k 2 = 2k+1$$