3
$\begingroup$

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$

3 Answers 3

6

[Edited again to account for G.Myerson's answer and fan's comments]

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$.

  • 0
    @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.2011-10-15
1

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,

$f(a) = \frac{1}{2} \sum_g c(g)^2 + \frac{1}{2} \sum_{c(g) $ = \frac{1}{2} \sum_{c(g).

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

$ f(a) = \sum_{c(g).

Edited: That's as far as I got.

  • 0
    Yes. Dumb mistake on my part. I'll look at this later and see if I can salvage.2011-10-14
0

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}$

  • 0
    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.2011-10-15