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

Проект МЦНМО
при участии
школы 57
Задача 60653
Темы:    [ Деление с остатком ]
[ Разложение на множители ]
[ Арифметика остатков (прочее) ]
[ Малая теорема Ферма ]
Сложность: 3+
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Докажите, что
  а)  241 + 1  делится на 83;
  б)  270 + 370  делится на 13;
  в)  260 – 1  делится на 20801.


Решение

  а)  29 = 512 ≡ 14 (mod 83),  218 ≡ 196 ≡ 30,  236 ≡ 900 ≡ 70 ≡ –13,  241 ≡ –13·32 ≡ –416 ≡ –1.

  б)  270 + 370 = 435 + 935  делится на  4 + 9 = 13.

  в)  20801 = 11·31·61.
  Первый способ.  260 – 1  делится на  210 – 1 = (25 – 1)(25 + 1) = 31·33.  Это число делится на 31 и на 11. Кроме того,   26 ≡ 3 (mod 61),  230 ≡ 243 ≡ –1,
260 ≡ 1.
  Второй способ. Согласно малой теореме Ферма (см. задачу 60736)  260 – 1  делится на 61,  230 – 1  делится на 31,  210 – 1  делится на 11. Поэтому
260 – 1  делится на все эти числа.

Замечания

В п. а) школьники, знакомые с квадратичными вычетами могут рассуждать так:  (241 – 1)(241 + 1) = 282 – 1  делится на 83 по малой теореме Ферма. Двойка не является квадратичным вычетом по модулю 83, поэтому  241 – 1  на 83 не делится. Значит, на 83 делится  241 + 1.

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

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

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

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