Логин:Пароль:
 FAQ по форумуНовые сообщения на Форуме
  • Страница 1 из 1
  • 1
Форум Эрудитов » Логические задачи и головоломки » Математические задачи » Решенные задачи » Остатки кубов (sml[ok]задачи без решения)
Остатки кубов
LexxДата: Пт, 28.10.11, 20:19 | Сообщение # 1
Высший разум
Сообщений: 4728
Награды: 88
Совы: 6
Продолжу давно заброшенную рубрику-задачи без решения.
Суть ее такова, что решения задачи нет, могу проверить только ответ.
Уровень задачи 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
 
ИванДата: Сб, 29.10.11, 14:35 | Сообщение # 2
Гений
Сообщений: 3061
Награды: 50
Совы: 1
Quote (Lexx)
Уровень задачи 3 класс и выше

Quote (Lexx)
Сколько различных чисел встречается среди остатков от деления на n чисел 1^3, 2^3, 3^3, ..., (n−1)^3, n^3, где n=9699690·2011?

shocked
Если вы нашли ошибку на нашем сайте, выделите её мышкой и нажмите Alt+F4.
 
LexxДата: Сб, 29.10.11, 20:14 | Сообщение # 3
Высший разум
Сообщений: 4728
Награды: 88
Совы: 6
Quote
Уровень задачи 3 класс и выше
grin
Уровень не 3 класс, а 3 курс cheesy
 
zhekasДата: Вс, 13.11.11, 23:05 | Сообщение # 4
Гуру
Сообщений: 166
Награды: 43
Совы: 6
Пусть 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 равно:

2) 2
3) 3
5=6*1-1) 6*1-1=5
7=6*1+1) 2*1+1=3
11) 11
13) 5
17) 17
19) 7
2011) 671

Тогда для n количество остатков равно их произведению и равно 2*3*5*3*11*5*17*7*671=395252550
 
LexxДата: Пн, 14.11.11, 14:28 | Сообщение # 5
Высший разум
Сообщений: 4728
Награды: 88
Совы: 6
Евгений up


Сообщение отредактировал Lexx - Пн, 14.11.11, 14:29
 
RostislavДата: Пн, 14.11.11, 22:13 | Сообщение # 6
ЭРУДИТ
Сообщений: 5379
Награды: 237
Совы:
zhekas, bravo
Сова - символ мудрости, знаний и эрудиции.
Сова - это единственная птица, которая может видеть "голубой" цвет.
 
ИванДата: Ср, 16.11.11, 19:59 | Сообщение # 7
Гений
Сообщений: 3061
Награды: 50
Совы: 1
Не, ну понятно, он же наверное сейчас в третьем классе учится, всё помнит, а я вот в третьем классе учился давно и уже всё забыл. :(
Если вы нашли ошибку на нашем сайте, выделите её мышкой и нажмите Alt+F4.
 
Форум Эрудитов » Логические задачи и головоломки » Математические задачи » Решенные задачи » Остатки кубов (sml[ok]задачи без решения)
  • Страница 1 из 1
  • 1
Поиск:

Интересная информация
Последние задачи Сообщество эрудитов ВКонтакте Рейтинг сообщений Совиный рейтинг
1.Цифра)))2
2.Бессмысленное и загадочно...9
3.Помощь с решением задачи1
4.Помогите решить ребус1
5.О времена, о нравы ...10
6.Случайная хорда3
7.Лучше9
8.Акула12
9.6 ребусов3
10.Головоломка без ключа1
1.Rostislav5379
2.Lexx4728
3.nebo3636
4.Иван3061
5.никник2735
6.Kreativshik2472
7.Гретхен1807
8.Vita1488
9.erudite-man1378
10.Valet937
1.nebo123
2.Kreativshik113
3.sovetnik49
4.MrCredo38
5.IQFun30
6.Pro100_Artyom27
7.marutand20
8.хан20
9.никник15
10.Фигаро15

ГлавнаяГостевая книгаFAQОбратная связьКоллегиФорум Эрудитов