More fun in 2015, Part 33

Set $N$ be a square-free number (and we will take $N = 2015 = 5\cdot 13\cdot 31$ ), and $d$ be a divisor of $N$ .

Lemma: $\langle \text{gcd}(k-1,N) | k\ \text{is a multiple of}\ d\rangle = \langle \text{gcd}(\ell,N/d) | 0 \leq \ell < N/d\rangle.$ (This is an equality of "bags", i.e. the lists of numbers are identical except for the order.)

Proof : Apply the Chinese Remainder Theorem to the system of equations $\left\{\begin{array}{ll} x \equiv -1\ \text{mod}\ d, \\ x \equiv \ell\ \text{mod}\ N/d. \end{array}\right.$ to be guaranteed a unique solution $0 \leq x = k-1 < N$ for every value of $\ell$ . (It is essential that $N$ is square-free, so that $d$ and $N/d$ are coprime.) This defines a bijection between the values of $k$ and $\ell$ . Moreover, $\gcd(k-1,N) = \gcd(x,N) = \gcd(x,N/d) = \gcd(\ell,N/d).\ \ \ \square$

Now define $\Sigma(n) := \sum_{\ell = 0}^{n-1} \text{gcd}(\ell, n)$ for square-free integers $n$ .

Lemma: $\Sigma$ is a multiplicative function and for prime numbers $p$ , $\Sigma(p) = 2p-1.$ (I leave the proof to you.)

Now to solve the problem we observe that the set of $k$ values over which we sum is $\{\text{multiples of 1}\} - \{\text{multiples of 5}\} - \{\text{multiples of 13}\} - \{\text{multiples of 31}\} \\ + \{\text{multiples of 65}\} + \{\text{multiples of 155}\} + \{\text{multiples of 403}\} - \{\text{multiples of 2015}\}$ (E.g. after subtracting multiples of 5 and multiples of 13 we have subtracted all multiples of 65 twice, so we need to add them back in once, and so on. This is a common counting strategy.)

We obtain the desired sum by adding and subtraction various sums along the same lines; and note that $\sum_{k\ \text{is multiple of}\ d} \text{gcd}(k-1,2015) = \sum_{\ell = 0}^{2015/d-1} \text{gcd}(\ell, 2015/d) = \Sigma(2015/d).$ Thus we get as result $\Sigma(2015) - \Sigma(403) - \Sigma(155) - \Sigma(65) + \Sigma(31) + \Sigma(13) + \Sigma(5) - \Sigma(1) \\ = 9\cdot 25\cdot 61 - 25\cdot 61 - 9\cdot 61 - 9\cdot 25 + 61 + 25 + 9 - 1 = \boxed{11520}.$

By Menon's elegant identity, the answer is $\tau(2015)\phi(2015)$ , where $\tau$ denotes the number of positive integer factors. Now $2015=5*13*31$ so that $\tau(2015)\phi(2015)=2^3*1440=11520$ .