Математика
Русский язык

19. Задачи на теорию чисел

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения

Найти остаток от деления числа (страница 2)

Задание 8
Уровень задания: Равен ЕГЭ

Найдите остаток от деления числа \(26^{103} + 3^{101} - 5^{103}\) на \(26\)

Добавить задание в избранное

Обозначим остаток от деления числа \(N\) на число \(m\) через “\(N (\mathrm{mod}\, m)\)”.

Сначала найдём остаток от деления числа \(5^{103}\) на \(26\): \[5^{103} (\mathrm{mod}\, 26) = (5^{102}\cdot 5) (\mathrm{mod}\, 26) = (25^{51}\cdot 5) (\mathrm{mod}\, 26)\,.\] Так как \(25 (\mathrm{mod}\, 26) = -1 (\mathrm{mod}\, 26)\), то последнее выражение можно переписать в виде \[((-1)^{51}\cdot 5) (\mathrm{mod}\, 26) = (-5) (\mathrm{mod}\, 26) = 21\,.\]

Аналогично \[3^{101} (\mathrm{mod}\, 26) = (27^{33}\cdot 9) (\mathrm{mod}\, 26) = (1^{33}\cdot 9) (\mathrm{mod}\, 26) = 9\,.\]

Кроме того, понятно, что \(26^{103}\) делится на \(26\), тогда \[(26^{103} + 3^{101} - 5^{103})(\mathrm{mod}\, 26) = (0 + 9 - 21) (\mathrm{mod}\, 26) = (-12)(\mathrm{mod}\, 26) = 14(\mathrm{mod}\, 26)\,.\]

Таким образом, искомый остаток равен \(14\).

Ответ: 14

Задание 9
Уровень задания: Сложнее ЕГЭ

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

Утверждение: При любом \(n\in\mathbb{N}\) числа \(4^{n}\) и \(441^{n}\) имеют одинаковые остатки от деления на \(46\).

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

Обозначим остаток от деления числа \(N\) на число \(m\) через “\(N (\mathrm{mod}\, m)\)”. Воспользуемся тем, что \(4^n = 2^{2n}\), а \(441^{n} = 21^{2n}\). Рассмотрим \(42^{2n} (\mathrm{mod}\, 46)\): \[42^{2n}(\mathrm{mod}\, 46) = (-4)^{2n}(\mathrm{mod}\, 46) = 4^{2n}(\mathrm{mod}\, 46) = 2^{4n}(\mathrm{mod}\, 46) = (2^{2n}(\mathrm{mod}\, 46)\cdot 2^{2n}(\mathrm{mod}\, 46)) (\mathrm{mod}\, 46)\,.\]

С другой стороны: \[42^{2n}(\mathrm{mod}\, 46) = (2\cdot 21)^{2n}(\mathrm{mod}\, 46) = (2^{2n}\cdot 21^{2n})(\mathrm{mod}\, 46) = (2^{2n}(\mathrm{mod}\, 46)\cdot 21^{2n}(\mathrm{mod}\, 46))(\mathrm{mod}\, 46)\,.\]

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

\[\begin{aligned} &(2^{2n}(\mathrm{mod}\, 46)\cdot 2^{2n}(\mathrm{mod}\, 46))(\mathrm{mod}\, 46) = (2^{2n}(\mathrm{mod}\, 46)\cdot 21^{2n}(\mathrm{mod}\, 46))(\mathrm{mod}\, 46)\qquad\Leftrightarrow\qquad\\ \qquad\Leftrightarrow\qquad &2^{2n}(\mathrm{mod}\, 46) = 21^{2n}(\mathrm{mod}\, 46)\,, \end{aligned}\]

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

Добавить задание в избранное

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

\[\begin{aligned} &(2^{2n}(\mathrm{mod}\, 46)\cdot 2^{2n}(\mathrm{mod}\, 46))(\mathrm{mod}\, 46) = (2^{2n}(\mathrm{mod}\, 46)\cdot 21^{2n}(\mathrm{mod}\, 46))(\mathrm{mod}\, 46)\qquad\Leftrightarrow\qquad\\ \qquad\Leftrightarrow\qquad &2^{2n}(\mathrm{mod}\, 46) = 21^{2n}(\mathrm{mod}\, 46)\,, \end{aligned}\]

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

\[\begin{aligned} &(4(\mathrm{mod}\, 46)\cdot 4(\mathrm{mod}\, 46))(\mathrm{mod}\, 46) = (4(\mathrm{mod}\, 46)\cdot 441(\mathrm{mod}\, 46))(\mathrm{mod}\, 46)\qquad\Leftrightarrow\qquad\\ \qquad\Leftrightarrow\qquad &4(\mathrm{mod}\, 46) = 441(\mathrm{mod}\, 46)\,, \end{aligned}\]

где первое равенство примет вид: \[16 = (4\cdot 27)(\mathrm{mod}\, 46)\] – верное равенство. При этом второе равенство примет вид: \[4 = 27\] – неверное равенство. Таким образом, то, что Илья принял за равносильность при любом \(n\in\mathbb{N}\), не является равносильностью даже при \(n = 1\).

Ответ:

Последний выписанный переход неверен