Задача к ЕГЭ на тему «Остатки» №8

Просмотров 7 Комментарии 0

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

Утверждение: При любом $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$ .