Задание по олимпиадной математике от Малкина М. И.

Можно считать, что число $m = q - p$ не меньше 2. При этом НОД($p, m$) = НОД($p, q$) = 1. Числа $p$ и $q$ сравнимы по модулю $m$, но не кратны $m$, значит, после увеличения их на некоторое натуральное число $n < m$, станут кратными $m$. Докажем, что такое $n$ будет искомым. Заметим, что ($p$ – 1)($q$ – 1) > 1⋅$m$ ≥ $n$ + 1, то есть $pq > p + q + n$. Поэтому $pqm \geqslant pq(1 + n) > pq + n(p + q + n) = (p + n)(q + n)$.

Поделив на $m$ = НОД($p + n, m$) = НОД($p + n, q + n$), получим $pq$ > НОК($p + n, q + n$).