Количество целочисленных точек

[log_evgenyi]

Почему сумма $ \left \lfloor \frac{q}{p} \right \rfloor+\left \lfloor \frac{2q}{p} \right \rfloor+..+\left \lfloor \frac{p-1}{p} \right \rfloor$где$q,p$взаимно простые числа, равна количеству целочисленных точек находящихся внутри треугольника $\left ( 0,0 \right ),\left ( p-1,q-1 \right ),\left ( p-1,0 \right )$ Я её решил через сумму арифметической прогрессии.

[Sonic86]

Общую формулу для числителя выпишите плиз, как-то она не угадывается.

log_evgenyi в сообщении #1229340 писал(а):

равна количеству целочисленных точек находящихся внутри треугольника

Это стандартная геометрическая интепретация дискретной суммы, аналог интегральной суммы. Площадь под кривой $y=f(x)$ для $x\in [a;b]$ равно понятно какому интегралу, а число целых точек под этой кривой равно понятно какой сумме.

[log_evgenyi]

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

Общую формулу для числителя выпишите плиз, как-то она не угадывается.

$\left \lfloor \frac{(p-1)q}{p} \right \rfloor$$\left \lfloor \frac{q}{p} \right \rfloor+\left \lfloor \frac{(p-1)q)}{p} \right \rfloor= q-1$ И таких сумм $p-1$для прямоугольника, значит разделить на 2 для треугольника. Т.к. на диагонали нет целочисленных точек.
Спасибо за разъяснение.А где можно доказательство прочитать?

[Sonic86]

log_evgenyi в сообщении #1229546 писал(а):

А где можно доказательство прочитать?

Да как бы очевидно: нарисуйте график функции, целочисленную решетку и посчитайте число точек в каждом вертикальном столбике из точек. Ну или Бухштаба скачайте - в нем это где-то в самом начале.

log_evgenyi в сообщении #1229546 писал(а):

$\left \lfloor \frac{(p-1)q}{p} \right \rfloor$$\left \lfloor \frac{q}{p} \right \rfloor+\left \lfloor \frac{(p-1)q)}{p} \right \rfloor= q-1$

М.б. это и ответ, но явно не на мой вопрос Квадратичный закон взаимности изучаете? Если да, то там общая формула $\lfloor \frac{kp}{q}\rfloor$, и тогда последнее слагаемое у Вас выписано неверно.

[log_evgenyi]

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

М.б. это и ответ, но явно не на мой вопрос , и тогда последнее слагаемое у Вас выписано неверно.

$\left \lfloor \frac{q}{p} \right \rfloor+\left \lfloor \frac{2q}{p} \right \rfloor+...+\left \lfloor \frac{(p-1)q}{p} \right \rfloor=\frac{(p-1)(q-1)}{2} $
Нашел то, что вы советовали у Бухштаба, все предельно ясно, спасибо.