Extremal and Average Behavior of a Shifted GCD Sum over Divisors

Abstract

For every integer n >= 2, define A(n) = sum_{d|n} gcd(d-1, n/d-1), and write B(n) = A(n) - 2(n-1). We prove the sharp inequality A(n) <= 9n/4, with equality only at n = 36, and determine the next two extremal ratios: after excluding 36, equality in A(n) <= 20n/9 occurs only at n = 45; after also excluding 45, equality in A(n) <= 31n/14 occurs only at n = 28. The extremal theorem combines an analytic cutoff with an exact finite verification. We establish B(n) = O_epsilon(n^(1/2+epsilon)), show that the exponent 1/2 is optimal on the power scale, classify the integers for which A(n) <= 2n, and give an explicit uniform bound of order n^(3/4). We also prove a three-term average-order formula whose leading term is (3/(2 pi^2)) x (log x)^2, derive quantitative bounds for exceptional sets, construct a Pell-type family with two distinct large gcd contributions, and give an exact summatory formula evaluable in O(sqrt(X) log X) arithmetic operations. This Version 2 substantially extends the original sharp-bound preprint. The uploaded files include the paper, its LaTeX source, and the exact-integer extremal verifier.