сумма чисел представимых в виде px+qy

[maxal]

Пусть $p,q$ - два различных простых числа.
Вычислите сумму целых чисел меньших $pq$ и представимых в виде $px+qy$, где $x,y$ - целые положительными числа.

[ex-math]

$$\frac{4p^2q^2-3p^2q-3pq^2+3pq-p^2-q^2+1}{12}$$

Свел к суммам Дедекинда и применил закон взаимности.

[kotenok gav]

ex-math в сообщении #1246054 писал(а):

суммам Дедекинда

А что это?

[ex-math]

Посмотрите хотя бы в англовики dedekind sum.

[maxal]

ex-math, сходится. В факторизованном виде чуть красивее:

$$\frac{(p-1)(q-1)(4pq+p+q+1)}{12}.$$

Мое решение (довольно элементарное) тут: https://mathoverflow.net/q/280557

-- Fri Sep 08, 2017 00:54:09 --

ex-math, для полноты картины напишите свое решение?

[Andrey A]

Этот вопрос три года висел безответно http://dxdy.ru/post881550.html#p881550 (последняя строка). Правда, несколько в ином виде. Там $S$ - сумма представимых, $s$ - сумма непредставимых.

[ex-math]

Нужно сосчитать сумму по натуральным $x$ и $y$

$$ S=\sum_{px+qy\leqslant pq}\bigl(px+qy\bigr)=p\sum_{x\leqslant q-1}x\left[p-\frac{px}q\right]+q\sum_{y\leqslant p-1}y\left[q-\frac{qy}p\right]=S_1+S_2. $$

Имеем

$$ S_1=p\sum_{x\leqslant q-1}x\left(p-1-\left[\frac{px}q\right]\right)=\frac{p(p-1)q(q-1)}2-p\sum_{x\leqslant q-1}x\left[\frac{px}q\right]. $$

Последняя сумма выражается через сумму Дедекинда

$$ s(p,q)=\sum_{x\leqslant q-1}\rho\left(\frac xq\right)\rho\left(\frac{px}q\right), $$

где $\rho(t)=\frac12-\{t\}$ следующим образом:

$$ \sum_{x\leqslant q-1}x\left[\frac{px}q\right]=-qs(p,q)-\frac{q(q-1)}4+\frac{p(q-1)(2q-1)}6. $$

Сумма $S_2$ получается если поменять местами $p$ и $q$. Потом складываем получившиеся выражения и пользуемся законом взаимности:

$$ s(p,q)+s(q,p)=\frac p{12q}+\frac q{12p}+\frac1{12pq}-\frac 14. $$

Доказательство закона взаимности элементарное, его можно найти у Apostol "Modular functions and Dirichlet series in number theory". Оно небольшое, но нет времени набирать. Его можно совместить с этим рассуждением, кое-где подсократив и выйдет недлинное рассуждение "от основ".