Gcd Sum

$G(N)=\sum_{j=1}^N\sum_{i=1}^j \gcd(i,j)$.
You are given: $G(10)=122$.

Find $G(10^{11})$. Give your answer modulo $998244353$.

The computation of G(10^11) would be extremely cumbersome to compute directly, it would involve finding the greatest common divisor (gcd) term by term for 10^11 terms.

So we’ll try to find the pattern or property that converges quickly to compute the sum.

First, break up this sum into two parts for i and j coprime and not coprime.

For i and j coprime (gcd(i, j) = 1), you can use the property of Euler’s Totient function that
Σφ(n) for n = 1 to N equals 1/2*N*(N+1) for N>1.

For i and j not coprime, break j into pa*q format where gcd(pa, q) = 1 and a is the gcd of i and j.

Then the sum is Σ d * φ(N/d) for d from 1 to N. This is simply the property of number theory.

Since the value we are asked for is modulo a large prime number, we can use a property of the Euler Totient function when using modular arithmetic, which makes it solvable.

However, the exact computations of this are complex and would require a deep understanding of number theory and some programming for large numbers, since any attempt to calculate it by hand or straightforward brute forcing with a computer would be unfeasible.

We can use Python to implement the approach:

,,,,,,,,,,,,,

MOD = 998244353

def calculate_gcd(a, b):
while b:
a, b = b, a % b
return a

def calculate_g(N):
dp = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
for j in range(1, i + 1):
dp[i][j] = (calculate_gcd(i, j) + dp[i][j – 1]) % MOD

G_N = 0
for i in range(1, N + 1):
G_N = (G_N + dp[i][i]) % MOD

return G_N

N = 10**11
result = calculate_g(N)
print(result)

,,,,,,,,,,,,,

This problem have been inspired by a problem of Project Euler (Problem 625)

More Answers: