дискретная-математика - Все возможные остатки деления на n

Я понял условие следующим образом. Имеется последовательность "треугольных" чисел $%1, 3, 6, ..., n(n-1)/2, ...$%; требуется выяснить, при каких натуральных $%m$% среди чисел данной последовательности будут встречаться все возможные остатки от деления на $%m$%.

Например, при $%m=3$% получаются остатки $%1,0,0,1,0,0,...$%, среди которых нет $%2$%, то есть $%m=3$% нам не подходит. А если $%m=4$%, то остатки будут равны $%1,3,2,2,3,1,0,...$%, где встречаются все остатки, и потому $%m=4$% нам подходит.

Ответом в этом случае действительно будут степени двойки. Докажем это.

Пусть $%m$% не есть степень двойки. Тогда $%m$% обладает нечётным делителем $%d>1$%. Достаточно доказать, что при делении на $%d$% некоторый из остатков не встречается. Тогда он же не будет встречаться и при делении на $%m$%.

Обозначим через $%r$% остаток от деления $%n(n-1)/2$% на $%m$%. Тогда удвоенная разность числа и остатка, то есть $%n(n-1)-2r$%, делится на $%m$%. То же самое будет верно для числа, умноженного на $%4$%, то есть для $%4n^2-4n-8r=(2n-1)^2-(8r+1)$%.

Теперь обратим внимание на то, что квадрат целого числа при делении на $%d$% не может давать все возможные остатки. Действительно, достаточно возводить в квадрат только числа от $%0$% до $%d-1$% включительно. Это дало бы все $%d$% значений только при отсутствии повторений у остатков, но $%(d-1)^2$% даёт в остатке $%1$%, как и $%1^2$%. Заметим, что у нас $%d>1$%, а потому $%d-1$% и $%1$% -- это разные числа. (Здесь можно также заметить, что $%d-2$% при возведении в квадрат даст то же, что $%2$% и так далее, но этот факт на самом деле не требуется.)

Итак, мы выяснили, что существует такой остаток $%s$%, который не мог возникнуть при делении $%(2n-1)^2$% на $%d$%. Теперь осталось заметить, что при нечётном $%d$%, если $%r$% пробегает все значения от $%0$% до $%d-1$%, то и остаток от деления $%2r$% в каком-то порядке пробегает эти же значения. Значит, то же самое будет верно для $%4r$% и для $%8r$%, а также для $%8r+1$%. В частности, для какого-то $%r$% значение остатка для $%8r+1$% будет равно $%s$%, а у нас было сказано, что $%(2n-1)^2-(8r+1)$% делится на $%d$%. Но это невозможно в силу того, что квадрат остатка $%s$% давать не может.

Осталось выяснить, что все значения вида $%m=2^k$% нам подходят. Установим это методом математической индукции. При $%m=1$%, $%m=2$% всё очевидно. Пусть $%k>1$%, и пусть уже установлено, что числа вида $%n(n-1)/2$% при делении на $%2^{k-1}$% дают все возможные значения для остатков. Пусть $%r$% -- остаток от деления $%n(n-1)/2$% на $%2^{k-1}$%. Тогда при делении на $%2^k$% того же самого числа, остаток принимает одно из значений $%r$% или $%r+2^{k-1}$%. Увеличим значение $%n$% на $%2^k$%, то есть рассмотрим число $$\frac{(n+2^k)(n+2^k-1)}2=\frac{n(n-1)}2+n\cdot2^k+2^{2k-1}-2^{k-1}.$$ Отсюда видно, что остатки от деления на $%2^k$% у двух рассмотренных нами "треугольных" чисел (с номерами $%n$% и $%n+2^k$%), отличаются на $%2^{k-1}$%. Значит, оба остатка $%r$% и $%r+2^{k-1}$% принимаются этими числами в том или другом порядке. Поскольку $%r$% принимало все значения от $%0$% до $%2^{k-1}-1$%, то теперь мы имеем в распоряжении все значения остатков от $%0$% до $%2^k-1$%, что завершает доказательство.