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


 
zhekasДата: Воскресенье, 13.11.2011, 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.2011, 14:28 | Сообщение # 5
Высший разум
Сообщений: 4728
Награды: 88
Совы: 6
Евгений up



Сообщение отредактировал Lexx - Понедельник, 14.11.2011, 14:29
 
RostislavДата: Понедельник, 14.11.2011, 22:13 | Сообщение # 6
ЭРУДИТ
Сообщений: 5346
Награды: 232
Совы:
zhekas, bravo

Сова - символ мудрости, знаний и эрудиции.
Сова - это единственная птица, которая может видеть "голубой" цвет.
 
ИванДата: Среда, 16.11.2011, 19:59 | Сообщение # 7
Гений
Сообщений: 3061
Награды: 53
Совы: 1
Не, ну понятно, он же наверное сейчас в третьем классе учится, всё помнит, а я вот в третьем классе учился давно и уже всё забыл. :(

Если вы нашли ошибку на нашем сайте, выделите её мышкой и нажмите Alt+F4.
 
Форум Эрудитов » Логические задачи и головоломки » Математические задачи » Решенные задачи » Остатки кубов (sml[ok]задачи без решения)
  • Страница 1 из 1
  • 1
Поиск:

Интересная информация
Последние задачи Сообщество эрудитов ВКонтакте Рейтинг сообщений Совиный рейтинг
1.Гидродинамика13
2.Гексаграмма4
3.Неархимедов мир.2
4.Улитка4
5.Геометрия удара 2.00
6.Коллективный эффект0
7.О "числах Хоппа"...1
8.Хитрый ребус на смекалку0
9.Мешки с зерном2
10.Неверный ход0
1.Rostislav5346
2.Lexx4728
3.nebo3612
4.Иван3061
5.никник2670
6.Kreativshik2472
7.Гретхен1807
8.Vita1411
9.erudite-man1342
10.Valet937
1.nebo123
2.Kreativshik113
3.sovetnik49
4.MrCredo37
5.IQFun30
6.Pro100_Artyom27
7.marutand20
8.хан20
9.никник15
10.Vita13

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