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

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

Условие

Автор: Тен О.

Даны натуральные числа m и n. Докажите, что число  2n – 1  делится на число  (2m – 1)²  тогда и только тогда, когда число n делится на число  m(2m – 1).


Решение

  2km – 1  делится на  2m – 1,  поэтому  2km+d – 1 = 2km+d – 2d + 2d – 1 = 2d(2km – 1) + 2d – 1 ≡ 2d – 1 (mod 2m – 1).  Таким образом  2n – 1  делится на  2m – 1  тогда и только тогда, когда n делится на m. Если  n = km,  то  

  Каждое слагаемое дает остаток 1 при делении на  2m – 1,  поэтому     Значит,  2km – 1  делится на  (2m – 1)²  тогда и только тогда, когда k делится на  2m – 1,  что равносильно тому, что n делится на  m(2m – 1).

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1997
Этап
Вариант 4
Класс
Класс 10
задача
Номер 97.4.10.3

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

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