Тема 19. Задачи на теорию чисел
19.07 Остатки
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела задачи на теорию чисел
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#2127

Илья сформулировал и доказал неверное утверждение. Найдите ошибку в доказательстве Ильи.

Утверждение: При любом n ∈ ℕ  числа 4n  и 441n  имеют одинаковые остатки от деления на 46  .

Доказательство:

Обозначим остаток от деления числа N  на число m  через “N (modm  )  ”. Воспользуемся тем, что 4n = 22n  , а 441n =  212n  . Рассмотрим 422n(mod46 )  :

422n(mod46 ) = (− 4)2n(mod46  ) = 42n(mod46 ) = 24n(mod46  ) = (22n(mod46 ) ⋅ 22n(mod46 ))(mod46 ).

С другой стороны:

422n (mod46  ) = (2 ⋅ 21)2n (mod46 ) = (22n ⋅ 212n)(mod46 ) = (22n(mod46 ) ⋅ 212n (mod46 ))(mod46 ).

Таким образом,

      (22n(mod46  ) ⋅ 22n(mod46 ))(mod46 ) = (22n (mod46  ) ⋅ 212n (mod46 ))(mod46 )    ⇔
⇔     22n(mod46  ) = 212n(mod46 ),

откуда получаем требуемое равенство.

Показать ответ и решение

Рассуждения Ильи были верны до этого места:

      (22n(mod46  ) ⋅ 22n(mod46 ))(mod46 ) = (22n (mod46  ) ⋅ 212n (mod46 ))(mod46 )    ⇔
        2n              2n
⇔     2  (mod46  ) = 21  (mod46 ),

Убедимся в том, что выписанная равносильность не имеет места. Пусть n = 1  , тогда эта “равносильность” примет вид:

       (4 (mod46  ) ⋅ 4(mod46 ))(mod46 ) = (4(mod46 ) ⋅ 441(mod46 ))(mod46 )     ⇔
⇔      4(mod46 ) = 441(mod46  ),

где первое равенство примет вид:

16 = (4 ⋅ 27)(mod46 )
– верное равенство. При этом второе равенство примет вид:
4 = 27
– неверное равенство. Таким образом, то, что Илья принял за равносильность при любом n ∈ ℕ  , не является равносильностью даже при n = 1  .
Ответ: Последний выписанный переход неверен

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное обучение
в Школково

Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!