А деление с остатком мы выразить можем: чтобы q было неполным частным от деления A на B, нужно, чтобы выполнялись неравенства
A>=B*q
и
A<B*(q+1)
А нестрогое неравенство — это равенство, если добавить к меньшей части ещё одну свободную переменную (а для строгого нужно ещё 1 добавить). Итого соотношение q=r! выражается системой на неотрицательные целые переменные

// M достаточно большое относительно r, //
M^r = q*(C_M^r) + x_1,
(q+1)*(C_M^r) = M^r + 1 + x_2