# 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)$?

1$$g(p)$$Let’s expand it
2$$= \sum_{i=1}^p gcd(i,p)$$Let’s expand it even more
3$$= gcd(1,p) + gcd(2,p) + gcd(3,p) + \dots + gcd(p-1,p) + gcd(p,p)$$
Now, we know that all numbers less than $p$ are co-prime with it. So the previous step becomes…
4$$= 1 + 1 + 1 + \dots + 1 + P$$There are exactly $p-1$ values of $i$ which are co-prime to $p$.
5$$= (p-1) + p$$
6$$= 2p – 1$$

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)$

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.

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

1$$g(p^a)$$
2$$= \sum_{i=1}^{p^a}gcd(i,p^a)$$
3$$= gcd(1,p^a) + gcd(2, p^a) + \dots + gcd(p^a,p^a)$$
Before we continue, answer the following question: How many different unique values can we get for $gcd(x,p^a)$, where $1 \leq x \leq p^a$?
Let the value of $gcd(x,p^a)$ be $e$. Since $e$ divides both $x$ and $p^a$, then $e$ must be a divisor of $p^a$.
Hence, the unique values we will get for $gcd(x,p^a)$ will be the divisors of $p^a$
Next question: If $e$ is a divisor of $p^a$, then how many different value of $x$ there are such that $gcd(x,p^a)=e$, where $1 \leq x \leq p^a$?
According to Euler Phi Extension, we know that there are $\phi(\frac{p^a}{e})$ such values of $x$.
So, in step $3$, if we group all equal values together, then each divisor $e$ of $p^a$ will occur exactly $\phi(\frac{p^a}{e})$ times.
4$$= \sum_{e \mid p^a} e \times \phi(\frac{p^a}{e})$$
Next question: What are the divisors of $p^a$?
Answer: $p^a$ has $a+1$ divisors – $1, p, p^2, p^3, \dots, p^a$
5$$= 1 \times \phi(p^a) + p \times \phi(p^{a-1}) + p^2 \times \phi(p^{a-2}) + \dots + p^a \times \phi(1)$$Let’s expand the value of $\phi(x)$
We know that for power of prime, $\phi(p^a) = p^a\frac{p-1}{p}$
6$$= 1(p^a \frac{p-1}{p}) + p(p^{a-1}\frac{p-1}{p}) + \dots + p^a(1)$$If we simplify a bit, it becomes…
7$$= p^{a}\frac{p-1}{p} + p^{a}\frac{p-1}{p} + \dots + p^a$$
8$$= p^{a-1}(p-1) + p^{a-1}(p-1) + \dots + p^a$$Except for the last term, all other terms are $p^{a-1}(p-1)$.
9$$= a \times \Bigl( p^{a-1}(p-1) \Bigr) + p^a$$If we simplify it a bit…
10$$= (ap^a – ap^{a-1}) + p^a$$
11$$= (a+1)p^a – ap^{a-1}$$Done

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

Prerequisite
In order to understand this section, you have to be familiar with the following topics: Multiplicative Function, Euler Phi.

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?

1$$g(n)$$
2$$= gcd(1,n) + gcd(2,n) + gcd (3,n) + \dots + gcd(n,n)$$
All of the terms of form $gcd(x,n)$ are divisors of $n$.
If $e$ is a divisor of $n$, then how many times will it appear in step $2$?
Answer: $\phi(\frac{n}{e})$ times.
So, if we group each $gcd(x,n)$ term according to divisor of $n$, then we get…
3$$= \sum_{e \mid n} e \times \phi(\frac{n}{e})$$Since $e$ is a divisor of $n$, then $\frac{n}{e}$ is also a divisor. Let $d = \frac{n}{e}$. Then we get…
4$$= \sum_{d \mid n} \frac{n}{d} \times \phi(d)$$Since $n$ is just a constant in the summation …
5$$= n \sum_{d \mid n} \frac{\phi(d)}{d}$$Done.

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