Преобразование одной суммы [Теория чисел]

[Whitaker]

Здравствуйте, уважаемые друзья!
Помогите пожалуйста решить следующую задачку:
Доказать, что при любых целых $m$ и $n$, $n>0$, и любом действительном $x$ справедливы равенства:
$\sum \limits_{k=0}^{n}\Big[\dfrac{x+mk}{n}\Big]=\dfrac{(m-1)(n-1)}{2}+\dfrac{d-1}{2}+d\Big[\dfrac{x}{d}\Big]=\sum \limits_{k=0}^{m}\Big[\dfrac{x+nk}{m}\Big]$, где $d$ - наибольший общий делитель чисел $m$ и $n$.
Не знаю даже с чего начать.

С уважением, Whitaker.

[Sonic86]

Можно переписать $\left[\frac{A}{B}\right]=\frac{A}{B}-\frac{A\mod B}{B}$ и подставить - должно что-то сократиться, а дальше считать суммы с $A\mod B$ бывает легче.
(сам не решал, не знаю, насколько этот вариант оптимален)

[Whitaker]

Sonic86 в сообщении #562546 писал(а):

$\left[\dfrac{A}{B}\right]=\dfrac{A}{B}-\dfrac{A\mod B}{B}$

А что означает $\dfrac{A\mod B}{B}$? Не могу понять

[Sonic86]

Очевидно, что $A\mod B$ обозначает $A-B\left[\frac{A}{B}\right]$. А поскольку Вы знаете, что такое $A-B\left[\frac{A}{B}\right]$, значит Вы знаете, что такое $A\mod B$ Шучу конечно (хотя и это оно тоже обозначает).
$A\mod B$ - остаток от деления $A$ на $B>0$ (бинарная операция, функция). Не следует путать с отношением сравнения по модулю.

[Whitaker]

Если я Вас правильно понял, то получается так:
$\Big[ \frac{x}{n}\Big]=\frac{x}{n}-\frac{x \mod n}{n}$
$\Big[ \frac{x+m}{n}\Big]=\frac{x+m}{n}-\frac{(x+m) \mod n}{n}$

$\cdots$

$\Big[ \frac{x+m(n-1)}{n}\Big]=\frac{x+m(n-1)}{n}-\frac{(x+m(n-1)) \mod n}{n}$ $\Big[ \frac{x+mn}{n}\Big]=\frac{x+mn}{n}-\frac{(x+mn) \mod n}{n}$

Суммируя все получаем:
$\sum \limits_{k=0}^{n}\Big[\frac{x+mk}{n}\Big]=\frac{x(n+1)}{n}+\frac{m(n+1)}{2}-\frac{1}{n}\Big( \Big(x(n+1)+\frac{mn(n+1)}{2} \Big)\mod n\Big)$
А вот последнюю скобку где стоит $\mod n$ не получается никак преобразовать

[Sonic86]

Whitaker в сообщении #562642 писал(а):

А вот последнюю скобку где стоит $\mod n$ не получается никак преобразовать

Чему равно $(kn)\mod n$ для $k\in\mathbb{Z}$? Так что последнюю скобочку можно немного все же упростить.
Ааа, там же $x\in\mathbb{R}$. Но вроде как с самого начала $x$ можно было заменить на $[x]$.
Можно так же посчитать сумму справа, подставить и попытаться что-то сократить.

[Whitaker]

Ну да $x\in \mathbb{R}$.
Почему это $x$ изначально нужно заменить на $[x]$? Мы ведь рассматриваем вещественные $x$.
P.S. $(kn) \mod n=0$ при $k\in \mathbb{Z}$

[Sonic86]

Whitaker в сообщении #562668 писал(а):

Почему это $x$ изначально нужно заменить на $[x]$? Мы ведь рассматриваем вещественные $x$.

Потому что $\left[\frac{x+km}{n}\right]=\left[\frac{[x]+\{x\}+km}{n}\right]=\left[\frac{[x]+km}{n}\right]$, поскольку добавление к числителю числа из $[0;1)$ целой части дроби не увеличит. (ну и я бы не сказал, что так именно нужно - просто так можно).
А предлагал я это делать для того, чтобы можно было воспользоваться этим:

Whitaker в сообщении #562668 писал(а):

$(kn) \mod n=0$ при $k\in \mathbb{Z}$

ведь если просто $x\in\mathbb{R}$, то о $xn \mod n$ трудно что-то сказать, а вот $[x]n \mod n$ уже определенно равно нулю.

[Whitaker]

Sonic86
я воспользовался Вашей подсказкой и получил следующее:
$\sum \limits_{k=0}^{n}\Big[\dfrac{x+mk}{n}\Big]=\dfrac{[x](n+1)}{n}+\dfrac{m(n+1)}{2}-\dfrac{1}{n}\Big(\Big([x]+\dfrac{mn(n+1)}{2}\Big)\mod n \Big)$
А как полученное упростить дальше? Что-то ничего в голову не приходит.

[arseniiv]

Может быть, $(a + b) \bmod n = (a \bmod n + b \bmod n) \bmod n$ поможет?

-- Вс апр 22, 2012 22:28:51 --

Вроде кое-что уберётся при этом! Ну и плюс $a \bmod n \bmod n = a \bmod n$.

-- Вс апр 22, 2012 22:31:50 --

Ой. Я забыл про наличие знаменателя.

[Whitaker]

arseniiv
у меня так получилось:
Если $n$ - четное, то: $\Big([x]+\frac{mn(n+1)}{2}\Big) \mod n=([x]+\frac{mn}{2})\mod n$
Если $n$ - нечетное, то: $\Big([x]+\frac{mn(n+1)}{2}\Big) \mod n=[x]\mod n$

[arseniiv]

Должно быть верным.

[Whitaker]

Я вот попробовал, но привести его к требуемому виду пока не получается.

[arseniiv]

Мне кажется, надо перейти к $d$ с самого начала:

$$\frac{x + mk}{n} = \frac{\frac xd + \frac mdk}{\frac nd}.$$

Это так мне кажется из-за слагаемого $d\left[ \dfrac xd \right]$ в результате.

[Whitaker]

arseniiv
даже если вначале разделить на $d$, то в конце получается наверное что-то с $\mod n$