Вы­чис­ли­те сумму \( \sum \limits _{k=0} ^{pq-1} (-1)^{[k/p]+[k/q]} , \) где \( pq \) — нечетное число

(*) Вторая часть задачи математической олимпиады среди студентов уни­вер­си­те­тов в 2013 году (А.Болбот, Но­во­си­бир­ский государственный университет). Первая часть — задача 13.

16. Пусть \( p \) и \( q \) — взаимно простые числа и \( pq \) — нечетное число. Вы­чис­ли­те сумму \[
\sum_{k=0}^{pq-1}
(-1)^{\left[ \frac kp \right] + \left[ \frac kq \right]} .
\tag {16.1}
\]

Решение. Поскольку \( pq \) — нечетное число, то числа \( p \) и \( q \) — также нечетные. Теперь вас ожидает красивейший трюк \[
\ant { \dfrac kp } + \ant { \dfrac kq} \equiv
p \cdot \ant { \dfrac ip } + q \cdot \ant { \dfrac iq} \pmod 2 \equiv \ldots
\] Так как сумма \( p+q \) — четная, то \[
\ldots \equiv - p \cdot \mant { \dfrac ip } - q \cdot \mant { \dfrac iq} \equiv
p \cdot \mant { \dfrac ip } + q \cdot \mant { \dfrac iq} \equiv
p_k + q_k \pmod 2 ,
\] где \( p_k \) и \( q_k \) — остатки от деления \( k \) на \( p \) и \( q \) соответственно.
Тогда \[
\sum_{k=0}^{pq-1}
(-1)^{\left[ \frac kp \right] + \left[ \frac kq \right]} =
\sum_{k=0}^{pq-1}
(-1)^{p_k + q_k} = \ldots
\] Согласно утверждению, доказанном в задаче 15, множество точек \( ( p_k; \ q_k ) \) является множеством точек \( ( i; \ j ) , \) где \( i = 0, \, 1, \, 2, \ \ldots p-1 \) и \( j = 0, \, 1, \, 2, \ \ldots q-1 . \) Значит, \[
\ldots = \sum_{i=0}^{p-1}
\sum_{j=0}^{q-1}
(-1)^{i+j} = 1 .
\] Ответ: \( 1 .\)