# determine $\left(\sum\limits_{g=1}^{p-1} g \times ((ag \mod p))\right) \bmod p^2$

Let $p$ be a prime, and let $((x))$ be the least positive residue of $x$ modulo $p$. For $a \in \{1, 2, ..., p-1\}$, consider $f(a) = \sum\limits_{g=1}^{p-1} g \times ((a g))$.

Does the following hold: $f(a)=f(b)$ if and only if $a=b$ or $a=b^{-1} \bmod p$？ Furthermore, can we determine $f(a) \bmod p^2$？

-

It seems I can't delete even my own answers here, so I'm doing the next best thing:

Please ignore what I wrote in the first edit, ending with

In particular the answer to the question as posed is "no".

This assumes I computed what the proposer intended with the following gp code:

f(p, a) = sum(g=1,p-1,g*(a*g)%p)


That code is missing a pair of parentheses and should say

f(p, a) = sum(g=1,p-1,g*((a*g)%p)) a


With this correction, the answer is yes. Experimental evidence through $p=199$ is consistent with the conjecture $$f(a) \equiv p \frac{a+a'}{12} \bmod p^2$$ where $a'$ is the multiplicative inverse of $a \bmod p$, which would imply that $f(a)\equiv f(b) \bmod p^2$ iff $a \equiv b$ or $a \equiv b^{-1} \bmod p$, as desired. In a previous edit I wrote at this point "I expect that (assuming I've not made yet another error) this corrected formula is known and/or not too hard to prove." This expectation was confirmed a few hours later by the original proposer, building on an answer from Gerry Myerson, who wrote $f(a)$ in terms of a Dedekind sum: $$f(a) = p^2 \bigl(s(a,p) + \frac14(p-1)\bigr).$$ To calculate $f(a) \bmod p^2$, we may ignore the term $p^2(p-1)/4$; the result then follows from the reciprocity formula for Dedekind sums: $$s(a,p) + s(p,a) = \frac{a^2-3ap+p^2+1}{12ap}$$ together with the observation that the denominator of $s(p,a)$ is not a multiple of $p$.

-
Professor Elkies, the reason you are unable to delete your posts is that your account here is currently unregistered (here are the general deletion rules). If you would like to put your most recent edit as a new answer, I can then delete this answer for you, if you would like. –  Zev Chonoles Oct 15 '11 at 3:27
Thanks so much! I comfirmed your formula following the suggestion of Gerry Myerson and by a known result involving Dedekind sum. –  fan Oct 15 '11 at 7:26
@Z.Chonoles: Thanks, but by now it's probably best to let the edited answer stand. I'll register soon in case this happens again. &fan: You're welcome; I saw the follow-ups by Myerson and you, and will edit my answer appropriately. –  Noam D. Elkies Oct 15 '11 at 15:26

First,

$f(a) = \frac{1}{2} \sum_{g=1}^{p-1} [ (g + a(g))^2 - g^2 - a(g)^2 ] = \frac{1}{2} \sum_g (g + a(g))^2 - \sum_g g^2$ .

Next, note that $g + a(g) = c(g)$ or $c(g) + p$ for $a \neq p-1$, where $c = a+1 ($mod $p)$, and $g + a(g) = p$ for $a=p-1$.

So for $a=p-1$,

$f(a) = \frac{p^2(p-1)}{2} - \frac{(p-1)p(2p-1)}{6} = \frac{(p-1)p(p+1)}{6}$.

For $a<p-1$,

$f(a) = \frac{1}{2} \sum_g c(g)^2 + \frac{1}{2} \sum_{c(g)<g} (2c(g) p + p^2) - \frac{(p-1)p(2p-1)}{6}$ $= \frac{1}{2} \sum_{c(g)<g} (2c(g) p + p^2) - \frac{(p-1)p(2p-1)}{12}$.

Now, I believe that for $c\neq 1$, $c(g)<g$ exactly half the time (as $c(-g) = p-c(g)$). So we have in the latter case

$f(a) = \sum_{c(g)<g} c(g) p + \frac{p^2(p-1)}{4} - \frac{(p-1)p(2p-1)}{12} = \sum_{c(g)<g} c(g) p + \frac{(p-1)p(p+1)}{12}$.

Edited: That's as far as I got.

-
Thanks for your interest. However I think you might accidently make a mistake. $k*p<c*g<k*p+g$ iff $\frac{kp}{c}<g<\frac{kp}{c-1}$ other than $\frac{kp}{c} < g < \frac{kp}{c} + 1$ as you said. –  fan Oct 14 '11 at 12:11
Yes. Dumb mistake on my part. I'll look at this later and see if I can salvage. –  Craig Oct 14 '11 at 14:06

I don't know the answer, but I can relate the question to Dedekind sums, for which there is a considerable literature (and I note that Noam Elkies suggested this in a comment at MathOverflow).

The least positive residue of $x$ modulo $p$ is given by $p\lbrace x/p\rbrace$, where the curly brackets indicate the fractional part. So $f(a)$, which I will write as $f(a,p)$, is given by $$f(a,p)=\sum_{g=1}^{p-1}gp\lbrace ag/p\rbrace=p\sum_{g=1}^{p-1}g\lbrace ag/p\rbrace$$

The Dedekind sum is given by $$s(h,k)=\sum_{\nu=1}^{k-1}\left({\nu\over k}-{1\over2}\right)\left(\left\lbrace{h\nu\over k}\right\rbrace-{1\over2}\right)$$ Multiplying out, $$s(h,k)=\sum_{\nu=1}^{k-1}{\nu\over k}\lbrace h\nu/k\rbrace+{\rm\ easy\ stuff}$$ that is, the other three sums are easy to evaluate (and are left as an exercise to the reader). So $$p^2s(a,p)=p\sum_{\nu=1}^{p-1}\nu\lbrace a\nu/p\rbrace+{\rm\ other\ easy\ stuff}$$ and thus $$f(a,p)=p^2s(a,p)+{\rm\ as\ usual}$$

-
Thanks so much! I've figured out the answer following your steps. Actually $p^2s(a,p)$ mod $p^2$ is known to be $\frac{p(a^2+1)}{12a}$, and thus $f(a,p)$ mod $p^2$ is clear. –  fan Oct 15 '11 at 7:23