# GCD Sum Function

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

# | Steps | Comments |
---|---|---|

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

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

# | Steps | Comments |
---|---|---|

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

[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?

# | Steps | Comments |
---|---|---|

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

Paper on GCD Sum Function – The gcd-sum Function

forthright48.com – Prime Factorization of an Integer