2
$\begingroup$

I got this question from a friend. I am not able to solve it.

Is there an expression in terms of $k$ for the following: $\sum_{x=0}^{k-1}\sum_{y=0}^{k-1}(xy\mod{k})?$

It seems that for odd $k,$ this is equivalent to $\frac{k(k-1)^2}{2}.$ However, I am not able to prove this is true, it is simply something that I found after checking a few values of $k.$ I cannot find any such expression for even $k,$ even after trying out a few values.

$\endgroup$
8
  • 1
    $\begingroup$ The conjecture is wrong. For odd $k$ the sequence comes out to $0, 6, 40, 126, 270, 550, 936, 1350, 2176, 3078, 3948, 5566, 7000, 8748, 11368, 13950, 16236, 19390, \dots$ but the conjectured $k(k-1)^2/2$ evaluates to $0, 6, 40, 126, 288, 550, 936, 1470, 2176, 3078, 4200, 5566, 7200, 9126, 11368, 13950, 16896, 20230,\dots$. As you can see, the terms are not always the same after the $4$th term. $\endgroup$ – YiFan Oct 13 '19 at 0:14
  • 2
    $\begingroup$ Btw, this is a sequence on the OEIS: oeis.org/A160255. $\endgroup$ – YiFan Oct 13 '19 at 0:24
  • 1
    $\begingroup$ @YiFan Hmm that doesn’t quite match my calculation. Perhaps I made an error somewhere. $\endgroup$ – Erick Wong Oct 13 '19 at 0:27
  • 1
    $\begingroup$ There was a small typo in my final expression, but now that it’s fixed it seems to agree perfectly with OEIS values, which makes the formula in OEIS suspect (it’s either needlessly complex or it’s wrong). $\endgroup$ – Erick Wong Oct 13 '19 at 7:12
  • 1
    $\begingroup$ @YiFan You’re right, it’s not hard to see the equivalence (I thought there would be an extra remainder term from OEIS that seemed unlikely to cancel out, but was mistaken). So it really is just written in a needlessly complex fashion :). $\endgroup$ – Erick Wong Oct 13 '19 at 15:22
3
$\begingroup$

Fix an $x$ and consider the inner sum over $y$. The $y=0$ term of course drops out, as does any other $y$ such that $k \mid xy$. Note that if $xy \bmod k = a$ with $a>0$ then $x(k-y) \bmod k = k-a$. So when $k$ is odd the non-zero terms pair up to average out to $k/2$. Even when $k$ is even the same principle applies to the middle term $y=k/2$: it’s either exactly $k/2$ or $0$.

Therefore the inner sum is exactly $\frac k2 \#\{ 1 \le y \le k-1: xy \not \equiv 0 \pmod k \}$. This second factor is simply $k - \gcd(x,k)$.

When $k$ is prime (not when $k$ is odd), the gcd term is always $1$, except when $x=0$, so we get $\frac k2 (k-1)^2$. In the general case, we get:

$$\frac k2 \sum_{x=0}^{k-1} k - \gcd(x,k) = \frac k2 (k^2 - a(k)),$$

where $a(k)$ is known as Pillai’s arithmetic function. There appears to be a number of papers studying it so I doubt it can be expressed compactly in terms of other functions. At least a more efficient expression is $a(k) = \sum_{d\mid k} d \varphi(\frac kd)$.

$\endgroup$
5
  • $\begingroup$ I am still confused about the step where you say "Note that if $xy \bmod k=a$ with $a>0$ then $x(k−y) \bmod k=k−a$. So when $k$ is odd the non-zero terms pair up to average out to $k/2$. I don't see how that implies the pairing up of the terms. $\endgroup$ – user686533 Oct 13 '19 at 15:28
  • $\begingroup$ @AnonymusMather1296 Another way to see this is to write the inner sum twice, one with $y$ going from $1$ up to $k-1$ and one with $y$ going from $k-1$ down to $1$. When you group the two sums together, each pair of terms sums to either exactly $k$ or exactly $0$. So evaluating the total amounts to counting how many $k$s there are (then dividing by two since we added the sum to itself). $\endgroup$ – Erick Wong Oct 13 '19 at 15:34
  • $\begingroup$ Also for when you said $k/2#{1≤y≤k−1:xy ≢ 0 (modk)},$ Is this the same thing as saying that it is $k/2$ times all $y$ such that $xy \neq 0?$ $\endgroup$ – user686533 Oct 13 '19 at 15:46
  • $\begingroup$ @AnonymusMather1296 Yes that is what I mean (assuming you mean $\ne 0$ in the ring of integers mod $n$). $\endgroup$ – Erick Wong Oct 13 '19 at 16:06
  • $\begingroup$ yeah i just copied your comment, and didn't bother with the latex. sorry $\endgroup$ – user686533 Oct 13 '19 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy