(*) Вторая часть задачи математической олимпиады среди студентов университетов в 2013 году (А.Болбот, Новосибирский государственный университет). Первая часть — задача 13.
\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 .\)
16. Пусть \( p \) и \( q \) — взаимно простые числа и \( pq \) — нечетное число. Вычислите сумму \[
\sum_{k=0}^{pq-1}
(-1)^{\left[ \frac kp \right] + \left[ \frac kq \right]} .
\tag {16.1}
\]
Решение. Поскольку \( pq \) — нечетное число, то числа \( p \) и \( q \) — также нечетные. Теперь вас ожидает красивейший трюк \[\sum_{k=0}^{pq-1}
(-1)^{\left[ \frac kp \right] + \left[ \frac kq \right]} .
\tag {16.1}
\]
\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 .\)