ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 60821
Темы:    [ Китайская теорема об остатках ]
[ Малая теорема Ферма ]
[ Теорема Эйлера ]
Сложность: 4-
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Найдите остатки от деления:  а) 1910 на 6;   б) 1914 на 70;   в) 179 на 48;   г) 141414 на 100.


Решение

  а)  1910 ≡ 1 (mod 2),  1910 ≡ 110 = 1 (mod 3).  Кроме того, по малой теореме Ферма  1910 ≡ 1 (mod 11).

  б)  1914 ≡ 1 (mod 2),  1914 ≡ (–1)14 = 1 (mod 5),  1914 ≡  19² ≡ (–2)² = 4 (mod 7).

  в)  179 ≡ 19 = 1 (mod 16),  179 ≡ (–1)9 = –1 (mod 3).

  г)  1414 ≡ 0 (mod 4).
  φ(25) = 20,  1414 ≡ 0 (mod 4),  1414 ≡ (–1)14 = 1 (mod 5),  значит,  1414 ≡ 16 (mod 20).
  141414 ≡ 1416 = (196)8 ≡ (–4)8 = (16)4 ≡ (–9)4 ≡ (6)² = 36 (mod 25).


Ответ

а) 1;  б) 11;  в) 17;  г) 36.

Источники и прецеденты использования

книга
Автор Алфутова Н.Б., Устинов А.В.
Год издания 2002
Название Алгебра и теория чисел
Издательство МЦНМО
Издание 1
глава
Номер 4
Название Арифметика остатков
Тема Деление с остатком. Арифметика остатков
параграф
Номер 6
Название Китайская теорема об остатках
Тема Деление с остатком. Арифметика остатков
задача
Номер 04.195

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .