I recently encountered the following equality ($\{\}$ denotes fractional part):


and found it very interesting as most of the individual summands on one side of the equation do not have a corresponding match on the other side. Investigating further, I found several other similar equalities:




Does anyone have any idea what general principle/pattern these arise from?

  • $\begingroup$ It may help to rewrite it like this: $\sum_{k=1}^{n}k\{\frac{ak}{n}\} = \sum_{k=1}^{n}k\frac{ak \mod n}{n}$ $\endgroup$ – Michael Stocker Jul 21 '14 at 12:37
  • $\begingroup$ @MichaelStocker And then you can remove the division, since it just scales the values... $\endgroup$ – Thomas Andrews Jul 21 '14 at 12:40
  • $\begingroup$ What does it look like when you write it in terms of Dedekind sums? $\endgroup$ – Gerry Myerson Jul 21 '14 at 13:05
  • $\begingroup$ It's interesting that, in the examples I've run (still relatively small) there are always $1,2,$ or $4$ numerators that yield the same value, but never $3$ or more than $4$. I've only been checking denominators that are a product of two primes. $\endgroup$ – Thomas Andrews Jul 21 '14 at 14:30
  • $\begingroup$ When the denominator is divisible by $3$ distinct primes primes, you can find $6$ and $8$ numerators that yield the same value, but still no examples of a value reached by exactly an odd number of numerators, other than $1$... $\endgroup$ – Thomas Andrews Jul 21 '14 at 14:37

Given $n$, let $a$ and $b$ be integers coprime with $n$. Then:

$$\sum_{k=1}^n k \left\{ \frac{ak}{n}\right\} = \sum_{k=1}^n k \left\{ \frac{bk}{n}\right\}$$

As Michael Stocker commented:

$$f(a,n) = \sum_{k=1}^n k \left\{ \frac{ak}{n}\right\} = \sum_{k=1}^n k \frac{ak \mod n}{n} = \frac{1}{n}\sum_{k=1}^n k (ak \mod n)$$ $$f(b,n) = \sum_{k=1}^n k \left\{ \frac{bk}{n}\right\} = \sum_{k=1}^n k \frac{bk \mod n}{n} = \frac{1}{n}\sum_{k=1}^n k (bk \mod n)$$

I've been able to prove that, as Thomas Andrews said, if $ab \equiv 1 \pmod{n}$ then $f(a,n) = f(b,n)$:

Let $k' := ak \mod n$ then $k' (bk' \mod n) = k (ak \mod n)$. Here's the proof: $k'[b(ak \mod n) \mod n] = k'(abk \mod n) = k'(k \mod n) = k'k = k(ak \mod n)$.

Note that $\lbrace (ak \mod n) \vert 1\leq k \leq n\rbrace = \lbrace 0, 1,2\cdots ,n-1\rbrace$.

So now $$f(a,n) = \sum_{k=1}^n k \left\{ \frac{ak}{n}\right\} = \sum_{k'=1}^n k' \left\{ \frac{bk'}{n}\right\} = f(b,n)$$

Now for the cases like $f(8,65) = f(18,65)$ where $ab \not\equiv 1$ I've found that $$k(ak \mod n) - k(bk\mod n) = \\(n-k)(b(n-k)\mod n) - (n-k)(b(n-k)\mod n)$$

But so far I've been unable to caracterize the pairs $(a,b)$ with that property.

  • $\begingroup$ But doesn't the first sum become $\sum_{k=1}^n k \left\{ \frac{bk'}{n}\right\}$ instead of $\sum_{k=1}^n k \left\{ \frac{bk}{n}\right\}$? $\endgroup$ – N. S. Jul 21 '14 at 13:31
  • $\begingroup$ @N.S. It will become $\sum_{k'=1}^n k' \left\{\frac{bk'}{n}\right\}$ wich is equivalent... I think $\endgroup$ – Darth Geek Jul 21 '14 at 13:34
  • $\begingroup$ No it doesn't. As you said, for each $k$ there exists a $k'$ so that $\left\{ \frac{ak}{n} \right\}= \left\{ \frac{bk'}{n} \right\}$. Which means that $k\left\{ \frac{ak}{n} \right\}$ becomes $k\left\{ \frac{bk'}{n} \right\}$.... $\endgroup$ – N. S. Jul 21 '14 at 13:43
  • $\begingroup$ @N.S. You are absolutely right. I'll try to think a way to fix this. $\endgroup$ – Darth Geek Jul 21 '14 at 14:06
  • $\begingroup$ @ThomasAndrews my proof is not right as pointed out in the comment. I'm trying to work out a fix. I think $a$ and $b$ must me coprime with $n$ but $a-b$ must not. $\endgroup$ – Darth Geek Jul 21 '14 at 16:53

Here is a small GNU Maxima script to ease experimentation

    display2d : false;

    /* x rational */
    my_floor(x) := block(
        if (x >= 0) then block(
            ab : divide(ratnumer(x),ratdenom(x)),
            a : ab[1], b : ab[2],
            if (b = 0) then block(
            ) else block(
                return(x - b/ratdenom(x))
        ) else block(
            ab : divide(ratnumer(-x),ratdenom(-x)),
            a : ab[1], b : ab[2],
            if (b = 0) then block(
            ) else block(
                return(x - (1-b/ratdenom(-x)))

    /* x rational */
    my_frac(x) := x - my_floor(x);

    cz : 0; cnz : 0;
    for N : 1 thru 20 do block(
    for m1 : 1 thru 20 do block(
    for m2 : m1+1 thru 20 do block(
        mylhs : apply("+",makelist(k*my_frac(m1*k/N),k,1,N)),
        myrhs : apply("+",makelist(k*my_frac(m2*k/N),k,1,N)),
        if (mylhs - myrhs = 0) then block(
            cz : cz+1,
        ) else block(
            cnz : cnz+1

  • $\begingroup$ Using the script above, I have found no solutions with $1 \le N,m1,m2 \le 100$, $gcd(N,m1) \neq 1$, $gcd(N,m2) \neq 1$, $gcd(m1,m2) = 1$. $\endgroup$ – andre Jul 21 '14 at 15:22
  • $\begingroup$ What do you mean by "no solutions?" Do you mean no more solutions than the ones above? $\endgroup$ – Thomas Andrews Jul 21 '14 at 18:30
  • $\begingroup$ Exactly what I've said. I have found no solution for $1 \le N,m1,m2 \le 100$ with the additional conditions $gcd(N,m1) \neq 1$, $gcd(N,m2) \neq 1$ and $gcd(m1,m2) = 1$. You may substitute $m1=a$ and $m2=b$. $\endgroup$ – andre Jul 21 '14 at 19:00
  • $\begingroup$ Sorry, reading comprehension failure on my part - read $\neq$ as $=$... $\endgroup$ – Thomas Andrews Jul 21 '14 at 19:45
  • $\begingroup$ Because of my low reputation, I comment here. I believe we should identify the pattern of the function $f(n,m,k) := (n-m)/n - \{mk/N\} + \{m(k+1)/N\}$ in order to perform a summation by parts. $\endgroup$ – andre Jul 22 '14 at 22:41

[Raw data deleted.]

Defining $$f(a,n)=\sum_{k=1}^{n-1} k\left\{\frac{ka}{n}\right\}$$ it's pretty obvious that $f(a,n)+f(n-a,n)=\frac{n(n-1)}{2}$ when $(a,n)=1$. It's also true, as proven by Darth Geek, that if $ab\equiv 1\pmod n$ then $f(a,n)=f(b,n)$.

Further data leads to:

Conjecture: If $f(a,n)=f(b,n)$ then $n\mid (a-b)(ab-1)$, or, equivalently, $a+a^{-1}\equiv b+b^{-1}\pmod n$, where the inverses are taken modulo $n$.

This would mean that the pairs $a,a^{-1}$ are the only solutions when $n$ a prime.

It is definitely not sufficient, since $a=3,b=48,n=65$ satisfies this condition.

This conjecture holds for all integers $4\leq n\leq 5000$.

$$\begin{align}f(a,n)&=\frac{a}{n}\sum_{k=1}^{n-1} k^2 - \sum_{k=1}^{n-1} k\left\lfloor\frac{ka}{n}\right\rfloor\\ &=\frac{a(n-1)(2n-1)}{6} - \sum_{k=1}^{n-1} k\left\lfloor\frac{ka}{n}\right\rfloor \end{align}$$

Thus $f(a,n)$ is an integer if $(n,6)=1$.

  • $\begingroup$ Perhaps the condition is sufficient for prime $n$? It's just a guess since for prime $n$ the sum may behave nicer. $\endgroup$ – Bart Michels Jul 22 '14 at 10:57
  • $\begingroup$ For prime $n$, that means $ab=1$ or $a=b$, and that does appear to be sufficient in that case, with the data I'm looking at. @barto $\endgroup$ – Thomas Andrews Jul 22 '14 at 12:16
  • $\begingroup$ Thank you, that's interesting. Understanding the behavior for prime $n$ would be a good step forward. $\endgroup$ – Bart Michels Jul 22 '14 at 18:45

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.