# Equality of sums with fractional parts of the form $\sum_{k=1}^{n}k\{\frac{mk}{n}\}$

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

$$\sum_{k=1}^{65}k\left\{\frac{8k}{65}\right\}=\sum_{k=1}^{65}k\left\{\frac{18k}{65}\right\}$$

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:

$$\sum_{k=1}^{77}k\left\{\frac{9k}{77}\right\}=\sum_{k=1}^{77}k\left\{\frac{16k}{77}\right\}$$

$$\sum_{k=1}^{77}k\left\{\frac{17k}{77}\right\}=\sum_{k=1}^{77}k\left\{\frac{24k}{77}\right\}$$

$$\sum_{k=1}^{85}k\left\{\frac{7k}{85}\right\}=\sum_{k=1}^{85}k\left\{\frac{22k}{85}\right\}$$

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

-
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}$ – Michael Stocker Jul 21 '14 at 12:37
@MichaelStocker And then you can remove the division, since it just scales the values... – Thomas Andrews Jul 21 '14 at 12:40
What does it look like when you write it in terms of Dedekind sums? – Gerry Myerson Jul 21 '14 at 13:05
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. – Thomas Andrews Jul 21 '14 at 14:30
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$... – 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.

-
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\}$? – N. S. Jul 21 '14 at 13:31
@N.S. It will become $\sum_{k'=1}^n k' \left\{\frac{bk'}{n}\right\}$ wich is equivalent... I think – Darth Geek Jul 21 '14 at 13:34
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\}$.... – N. S. Jul 21 '14 at 13:43
@N.S. You are absolutely right. I'll try to think a way to fix this. – Darth Geek Jul 21 '14 at 14:06
@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. – 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(
return(x)
) 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(
return(x)
) 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,
print(N,m1,m2,"|",mylhs)
) else block(
cnz : cnz+1
)
)));
print(cz,"|",cnz);


-
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$. – andre Jul 21 '14 at 15:22
What do you mean by "no solutions?" Do you mean no more solutions than the ones above? – Thomas Andrews Jul 21 '14 at 18:30
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$. – andre Jul 21 '14 at 19:00
Sorry, reading comprehension failure on my part - read $\neq$ as $=$... – Thomas Andrews Jul 21 '14 at 19:45
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. – 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)$.

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

-
Perhaps the condition is sufficient for prime $n$? It's just a guess since for prime $n$ the sum may behave nicer. – barto Jul 22 '14 at 10:57
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 – Thomas Andrews Jul 22 '14 at 12:16
Thank you, that's interesting. Understanding the behavior for prime $n$ would be a good step forward. – barto Jul 22 '14 at 18:45