Продолжу давно заброшенную рубрику-задачи без решения. Суть ее такова, что решения задачи нет, могу проверить только ответ. Уровень задачи 3 из 5, 11 класс и выше
Сколько различных чисел встречается среди остатков от деления на n чисел 1^3, 2^3, 3^3, ..., (n−1)^3, n^3, где n=9699690·2011? Подсказочка: Начните со случая, когда n — простое. Затем воспользуйтесь китайской теоремой об остатках.
Коллективное решение приветствуется.
Сообщение отредактировал Lexx - Пт, 28.10.11, 20:32
Пусть p - простое число. Тогда у системы вычетов (без нуля) от деления на p существует порождающий элемент a, такой что a^i пробегает всю систему вычетов. То есть любой остаток можно представить как a^i mod p.
Пусть x1 и x2 - два остатка по модулю p. Найдём, когда остатки их кубов совпадают. То есть
x1^3 = x2^3 mod p
x1 = a^i x2=a^j
(a^i)^3 = (a^j)^3 mod p
a^{3i} = a^{3j} mod p
3i = 3j mod (p-1)
Любое простое число, кроме 2 и 3, можно представить в виде 6k+1 или 6k-1
Итак рассмотрим два случая 1) p=6k+1 3i = 3j mod 6k i = j mod 2k тогда количество остатков кубов равно 2k+1 (+1 - это ноль).
2) p = 6k - 1 3i=3j mod (6k-2) i=j mod (6k-2) тогда количество остатков кубов равно 6k-1
Ну и отдельно найдём количество остатков для p=2 и p=3. Для p=2 их 2. Для p=3 - 3.
n=9699690·2011= 2*3*5*7*11*13*17*19*2011
Итак количество остатков кубов при делении на p равно:
