Problem

Given a positive integer $N$, find the value of $g(N)$, where $$g(n) = gcd(1,n) + gcd(2,n) + gcd(3,n) + \dots + gcd(n,n) = \sum_{i=1}^n gcd(i,n)$$

For example,
$$ \begin{align}
g(6) & = gcd(1,6) + gcd(2,6) + g(3,6) + gcd(4,6) + gcd(5,6) + gcd(6,6) \\
& = 1 + 2 + 3 + 2 + 1 + 6 \\
& = 15
\end{align}$$

The function $g(n)$ is called GCD Sum Function for obvious reasons.

There is a paper on this topic, “The gcd-sum Function” and in this post, I will attempt to explain it as simply as possible.

GCD Sum Function – $g(n)$

In short, there is a direct formula for calculating the value of $g(n)$.

If the prime factorization of $n$ is $p_{1}^{a_1} \times p_2^{a_2}\times \dots p_k^{a_k}$, then $$g(n) = \prod_{i=0}^k (a_i + 1)p_i^{a_i} – a_ip^{a_i-1}$$

For example, we know that $6 = 2 \times 3$. So using the formula above, we get:
$$ \begin{align}
g(6) & = \big((1+1)2 – 2^{1-1} \big) \big((1+1)3 – 3^{1-1}\big) \\
& = (4-1)(6-1) \\
& = 15
\end{align}$$

Very neat formula. So, as long as we can prime factorize $n$, we can easily calculate gcd-sum for $n$.

For the curious minds who want to know how we got the formula above, please proceed to next section.

Proof

Instead of trying to prove the theorem for any value of $n$, let us first try to prove it for a prime number $p$. If we can’t even prove it for a prime $p$, then forget about proving it for a composite number.

GCD Sum Function for Prime – $g(p)$

What is the value of $g(p)$?

Great! We managed to derive a formula. We now know that $g(p) = 2p – 1$.

Next, we try to derive a formula for a power of a prime.

GCD Sum Function for Power of Prime – $g(p^a)$

[su_box title=”Prerequisite”]In order to understand this section, you have to be familiar with the following topics: Euler Totient or Phi Function and Euler Phi Extension Theorem.[/su_box]

What is the value of $g(p^a)$?

Hence, $$g(p^a) = (a+1)p^a – ap^{a-1}$$

Next, if we can prove that $g(n)$ is a multiplicative function, then we are done.

GCD Sum Function is Multiplicative

[su_box title=”Prerequisite”]In order to understand this section, you have to be familiar with the following topics: Multiplicative Function, Euler Phi.[/su_box]

If we can prove that $g(n)$ is multiplicative, then our proof will be complete.

We know that a multiplicative function $f(x)$ works as follows:

$$f(mn) = f(m) \times f(n)$$, where $gcd(m,n) = 1$.

So, if we can prove that $g(n)$ is multiplicative, then we can say that:

$$g(n) = g(p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}) = g(p_1^{a_1})g(p_2^{a_2})\dots g(p_k^{a_k}) = \prod_{i=0}^k g(p_i^{a_i})$$

Since we know the formula for finding the value of $g(p^a)$, we can easily find gcd-sum for any composite number.

So, how do we prove that $g(n)$ is multiplicative?

Hence, we can say that: $$\bbox[yellow,5px]{g(n) = n\sum_{d \mid n} \frac{\phi(d)}{d}}$$

We know that $\phi(n)$ is multiplicative (for proof read post on Euler Phi). Since, $g(n)$ is divisor sum of the multiplicative function $\phi(n)$, using the Divisor Sum Theorem of Multiplicative Function we can say that $g(n)$ is also multiplicative.

Therefore, when $gcd(m,n) = 1$, we can say that $g(mn) = g(m) \times g(n)$.

Conclusion of Proof

We proved the following:

• $g(p^a) = (a+1)p^a – ap^{a-1}$
• $g(n)$ is multiplicative

Hence, we can say that:

$$g(n) = g(p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}) = g(p_1^{a_1})g(p_2^{a_2})\dots g(p_k^{a_k}) = \prod_{i=0}^k g(p_i^{a_i})\\
=\prod_{i=0}^k (a_i+1)p_i^{a_i} – a_ip_i^{a_i-1}$$

Proved 🙂

Reference

1. Paper on GCD Sum Function – The gcd-sum Function

2. forthright48.com – Prime Factorization of an Integer

Related Problems

1. SPOJ GCDEX – GCD Extreme

• Category: CPPS, Number Theory
• Tag: proof, theorem