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