Разделы 
Дополнительно
Задача по математике - 2915
2019-05-06 
Доказать, что если $p$ и $q$ - взаимно простые целые числа, то
$\left [ \frac{p}{q} \right ] + \left [ \frac{2p}{q} \right ] + \left [ \frac{3p}{q} \right ] + \cdots + \left [ \frac{(q-1)p}{q} \right ] = \left [ \frac{q}{p} \right ] + \left [ \frac{2q}{p} \right ] + \left [ \frac{3q}{p} \right ] + \cdots + \left [ \frac{(p-1)q}{p} \right ] = \frac {(p-1)(q-1)}{2}$.
Решение:
Отметим все точки плоскости с обеими целыми координатами («целые» точки), для которых $1 \leq x \leq q - 1, 1 \leq y \leq p - 1$ ($x$ и $у$ - координаты точек). Эти точки лежат внутри прямоугольника $OABC$, длины сторон которого равны $OA = q$ и $OC = p$ (рис.); число всех точек равно $(q-1)(p-1)$. Проведем диагональ $OB$ прямоугольника. Ясно, что на этой диагонали не будет расположена ни одна «целая» точка (координаты $x$ и $у$ всех точек диагонали $OB$ связаны соотношением $\frac{x}{y} = \frac{OA}{AB} = \frac{q}{p}$; но так как $q$ и $p$ - взаимно простые, то не существует целых положительных чисел $x < p$ и $y < q$, таких, что $\frac{x}{y} = \frac{q}{p}$). Заметим теперь, что число «целых» точек, имеющих абсциссу, равную $k$ ($k$ - какое-то целое положительное число, меньшее $q$), и расположенных под диагональю $OB$, равно целой части длины отрезка $MN$, изображенного на рис. Так как $MN = \frac{OM}{OA} \cdot AB = \frac{kp}{q}$, то это число равно $\left [ \frac{kp}{q} \right ]$. Следовательно, сумма
$\left [ \frac{p}{q} \right ] + \left [ \frac{2p}{q} \right ] + \left [ \frac{3p}{q} \right ] + \cdots + \left [ \frac{(q-1)p}{q} \right ]$
равна общему числу всех «целых» точек, расположенных под диагональю $OB$. Но всего внутри прямоугольника имеется $(q-1) \times (p-1)$ «целых» точек; из симметрии расположения этих точек относительно центра прямоугольника $OABC$ следует, что ровно половина из них расположена под диагональю $OB$ (здесь существенно, что на самой диагонали не лежит ни одна из точек). Таким образом,
$\left [ \frac{p}{q} \right ] + \left [ \frac{2p}{q} \right ] + \left [ \frac{3p}{q} \right ] + \cdots + \left [ \frac{(q-1)p}{q} \right ] = \frac {(q-1)(p-1)}{2}$.
Точно так же доказывается, что
$\left [ \frac{q}{p} \right ] + \left [ \frac{2q}{p} \right ] + \left [ \frac{3p}{q} \right ] + \cdots + \left [ \frac{(q-1)p}{q} \right ] = \frac{(p-1)(q-1)}{2}$.
Доказать, что если $p$ и $q$ - взаимно простые целые числа, то
$\left [ \frac{p}{q} \right ] + \left [ \frac{2p}{q} \right ] + \left [ \frac{3p}{q} \right ] + \cdots + \left [ \frac{(q-1)p}{q} \right ] = \left [ \frac{q}{p} \right ] + \left [ \frac{2q}{p} \right ] + \left [ \frac{3q}{p} \right ] + \cdots + \left [ \frac{(p-1)q}{p} \right ] = \frac {(p-1)(q-1)}{2}$.
Решение:
Отметим все точки плоскости с обеими целыми координатами («целые» точки), для которых $1 \leq x \leq q - 1, 1 \leq y \leq p - 1$ ($x$ и $у$ - координаты точек). Эти точки лежат внутри прямоугольника $OABC$, длины сторон которого равны $OA = q$ и $OC = p$ (рис.); число всех точек равно $(q-1)(p-1)$. Проведем диагональ $OB$ прямоугольника. Ясно, что на этой диагонали не будет расположена ни одна «целая» точка (координаты $x$ и $у$ всех точек диагонали $OB$ связаны соотношением $\frac{x}{y} = \frac{OA}{AB} = \frac{q}{p}$; но так как $q$ и $p$ - взаимно простые, то не существует целых положительных чисел $x < p$ и $y < q$, таких, что $\frac{x}{y} = \frac{q}{p}$). Заметим теперь, что число «целых» точек, имеющих абсциссу, равную $k$ ($k$ - какое-то целое положительное число, меньшее $q$), и расположенных под диагональю $OB$, равно целой части длины отрезка $MN$, изображенного на рис. Так как $MN = \frac{OM}{OA} \cdot AB = \frac{kp}{q}$, то это число равно $\left [ \frac{kp}{q} \right ]$. Следовательно, сумма
$\left [ \frac{p}{q} \right ] + \left [ \frac{2p}{q} \right ] + \left [ \frac{3p}{q} \right ] + \cdots + \left [ \frac{(q-1)p}{q} \right ]$
равна общему числу всех «целых» точек, расположенных под диагональю $OB$. Но всего внутри прямоугольника имеется $(q-1) \times (p-1)$ «целых» точек; из симметрии расположения этих точек относительно центра прямоугольника $OABC$ следует, что ровно половина из них расположена под диагональю $OB$ (здесь существенно, что на самой диагонали не лежит ни одна из точек). Таким образом,
$\left [ \frac{p}{q} \right ] + \left [ \frac{2p}{q} \right ] + \left [ \frac{3p}{q} \right ] + \cdots + \left [ \frac{(q-1)p}{q} \right ] = \frac {(q-1)(p-1)}{2}$.
Точно так же доказывается, что
$\left [ \frac{q}{p} \right ] + \left [ \frac{2q}{p} \right ] + \left [ \frac{3p}{q} \right ] + \cdots + \left [ \frac{(q-1)p}{q} \right ] = \frac{(p-1)(q-1)}{2}$.
