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

19.07 Остатки

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела задачи на теорию чисел

Решаем задачи

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

Задача 1#719Максимум баллов за задание: 4

Найдите все натуральные числа, при делении которых на 8 в частном получится то же число, что и в остатке. В ответ запишите их сумму.

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

Пусть при делении числа $a$ на 8 в частном получится то же число, что и в остатке. Тогда $a= 8r+ r.$ Так как $r$ — это остаток при делении на 8, то $r$ может быть равно только 1, 2, 3, 4, 5, 6 или 7. Для каждого из этих значений $r$ найдем возможное значение $a:$

9, 18, 27, 36, 45, 54, 63

Тогда в ответ записываем

9 + 18 +27 +36 +45+ 54+ 63= 252

Ответ: 252

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 2#720Максимум баллов за задание: 4

Число при делении на 8 дает остаток 5. Какой остаток оно дает при делении на 4?

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

Пусть число $a$ при делении на 8 дает остаток 5. Тогда имеем:

a= 8b+ 5= 8b+ 4+ 1 =4(2b+ 1)+1

Следовательно, число $a$ при делении на 4 дает остаток 1.

Ответ: 1

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

Задача 3#2014Максимум баллов за задание: 4

Докажите, что числа вида $n2,$ где $n∈ ℕ,$ не могут при делении на 3 давать остаток 2.

Показать доказательство

Остаток от деления на число $k$ произведения натуральных чисел $A ⋅B$ равен остатку от деления на число $k$ произведения $a ⋅b$ , где $a$ и $b$ – остатки от деления на $k$ чисел $A$ и $B$ соответственно.

Таким образом, остаток от деления числа

(3m + 1)2 = (3m + 1)⋅(3m + 1)

на $3$ равен остатку от деления $1 ⋅1$ на $3$ , то есть равен $1$ .

Остаток от деления числа

(3m + 2)2 = (3m + 2)⋅(3m + 2)

на $3$ равен остатку от деления $2 ⋅2$ на $3$ , то есть равен $1$ .

Остаток от деления числа

(3m)2 = 9m2

на $3$ равен $0$ .

Так как любое натуральное число $n$ всегда можно представить в одном из видов: $3m$ , $3m + 1$ , $3m + 2$ ( $m ∈ ℕ∪ {0}$ ), то $2 n$ при делении на $3$ не может давать в остатке $2$ .

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

Задача 4#2015Максимум баллов за задание: 4

При каких простых $p$ число $p2 +26$ также является простым? Если таких $p$ не существует, то в ответ запишите 0.

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

Проверим, каким может быть остаток от деления числа $p2 +26$ на $3$ :

1) Если $p$ не делится на $3$ , то $p2$ при делении на $3$ даёт остаток $1$ , тогда $p2+ 26$ при делении на $3$ даёт такой же остаток, как и число $1+ 26= 27$ , то есть $0$ .

Таким образом, если $p$ не делится на $3$ , то $2 p +26$ делится на $3$ , но $2 p + 26 > 3$ , а простых чисел, делящихся на $3$ , кроме числа $3$ , не бывает.

2) Единственное простое число, которое делится на $3$ – это число $3$ , следовательно, осталось проверить только случай $p = 3$ :

2 p + 26 = 9+ 26= 35

– не является простым.

В итоге мы доказали, что не существует простых чисел $p$ , таких, что число $p2+ 26$ – простое. Тогда в ответ запишем число 0.

Ответ: 0

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

Задача 5#30639Максимум баллов за задание: 4

Какие остатки при делении на 5 может давать точный квадрат?

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

Рассмотрим точный квадрат $2 a .$ Произведение чисел дает при делении на 5 такой же остаток, какой дает произведение их остатков при делении на 5. Следовательно, достаточно посмотреть, какие остатки может давать $a$ при делении на 5.

Пусть $a =5k.$ Тогда
$2 2 2 a = 25k = 5⋅5k$
Значит, $2 a$ без остатка делится на 5.
Пусть $a =5k +1.$ Тогда
$2 2 ( 2 ) a =25k + 10k+ 1= 5 5k + 2k + 1$
Значит, $a2$ дает остаток 1 при делении на 5.
Пусть $a =5k +2.$ Тогда
$2 2 ( 2 ) a =25k + 20k+ 4= 5 5k + 4k + 4$
Значит, $a2$ дает остаток 4 при делении на 5.
Пусть $a =5k +3$ . Тогда
$a2 = 25k2+ 30k +9 = 5(5k2+6k +1) +4$
Значит, $2 a$ дает остаток 4 при делении на 5.
Пусть $a =5k +4.$ Тогда
$2 2 ( 2 ) a =25k + 40k+ 16= 5 5k + 8k+ 3 + 1$
Значит, $a2$ дает остаток 1 при делении на 5.

Ответ:

$0;1;4$

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

Задача 6#30640Максимум баллов за задание: 4

Докажите, что если сумма квадратов двух целых чисел делится на 3, то и каждое из них делится на 3.

Показать доказательство

Полный квадрат при делении на 3 может давать в остатке либо 0, либо 1. Докажем это. Рассмотрим, какой остаток при делении на 3 дает квадрат целого числа в зависимости от его остатка.

Если $a =3k$ , то $a2 = 9k2 = 3⋅3k2$ , значит, $a2$ делится без остатка на 3.
Если $a = 3k+ 1$ , то $a2 = 9k2 +6k +1 = 3(3k2 +2k)+ 1$ , значит, $a2$ дает остаток 1 при делении на 3.
Если $a = 3k + 2$ , то $2 2 ( 2 ) a =9k +12k+ 4 =3 3k + 4k+ 1 + 1$ , значит, $2 a$ дает остаток 1 при делении на 3.

Таким образом, полный квадрат при делении на 3 может давать в остатке либо 0, либо 1. Тогда сумма двух квадратов, если ровно один из них не делится на 3, дает остаток 1 при делении на 3. Если же оба квадрата не делятся на 3, то их сумма дает остаток 2 при делении на 3. Значит, если сумма квадратов делится на 3, то и каждый из квадратов делится на 3, следовательно, каждое из чисел тоже делится на 3.

Курсы

Всё необходимое для достижения цели

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

Задача 7#30641Максимум баллов за задание: 4

Может ли сумма $2 2 2 a +b + c$ делиться на 5, если каждое из натуральных чисел $a, b$ и $c$ не делится на 5?

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

Полный квадрат при делении на 5 может давать в остатке либо 0, либо 1, либо 4. Докажем это. Рассмотрим точный квадрат $n2.$ Произведение чисел дает при делении на 5 такой же остаток, какой дает произведение их остатков при делении на 5, следовательно, достаточно посмотреть, какие остатки может давать $n$ при делении на 5.

Пусть $n =5k.$ Тогда
$n2 = 25k2 = 5⋅5k2,$
значит, $n2$ без остатка делится на 5.
Пусть $n =5k +1.$ Тогда
$n2 = 25k2+ 10k+ 1= 5(5k2+ 2k)+ 1,$
значит, $2 n$ дает остаток 1 при делении на 5.
Пусть $n =5k +2.$ Тогда
$n2 = 25k2+ 20k+ 4= 5 ⋅5k2 +4k +4,$
значит, $n2$ дает остаток 4 при делении на 5.
Пусть $n =5k +3.$ Тогда
$n2 = 25k2+ 30k + 9= 5⋅5k2+ 6k+ 1+ 4,$
значит, $n2$ дает остаток 4 при делении на 5.
Пусть $n =5k +4.$ Тогда
$n2 = 25k2+ 40k+ 16= 5(5k2+ 8k+ 3)+ 1,$
значит, $2 n$ дает остаток 1 при делении на 5.

Значит, если на одно из чисел $a2, b2$ и $c2$ не делится на 5, то их остатки при делении на 5 могут быть равны 1 или 4.

Сумма трех чисел, каждое из которых равно 1 или 4, никогда не будет делится на 5, значит, сумма $a2+ b2+ c2$ никогда не будет делиться на 5, если каждое из натуральных чисел $a, b$ и $c$ не делится на 5.

Ответ:

Нет, не может

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

Задача 8#30642Максимум баллов за задание: 4

Верно ли, что из ста различных целых чисел всегда можно выбрать пять таких, что их сумма делится на 7? В ответ запишите «Да» или «Нет».

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

Возьмем сто чисел, дающих остаток 1 при делении на 7. Тогда сумма любых пяти чисел дает остаток 5 при делении на 7. Следовательно, ответ «Нет».

Ответ: Нет

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

Задача 9#30643Максимум баллов за задание: 4

Верно ли, что из пяти целых чисел всегда можно выбрать два таких, разность квадратов которых делится на 7? В ответ запишите «Да» или «Нет».

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

Рассмотрим остатки, которые может давать точный квадрат при делении на 7:

2 1 ≡ 1 (mod 7) 22 ≡ 4 (mod 7) 32 ≡ 2 (mod 7) 2 4 ≡ 2 (mod 7) 52 ≡ 4 (mod 7) 2 6 ≡ 1 (mod 7) 72 ≡ 0 (mod 7) 2 2 8 ≡ 8⋅8 ≡1 ⋅1≡ 1 (mod 7) 92 ≡ 9⋅9 ≡2 ⋅2≡ 22 (mod 7) 102 ≡ 10⋅10≡ 3⋅3 ≡32 (mod 7) ...

Таким образом, мы получили цикл остатков

1, 4, 2, 2, 4, 1, 0

Следовательно, множество остатков, которые дает точный квадрат при делении на 7, состоит из четырех чисел:

0, 1, 2, 4

Тогда по принципу Дирихле среди пяти чисел всегда найдутся как минимум два числа, квадраты которых дают одинаковые остатки при делении на 7. Следовательно, разность этих квадратов будет давать остаток 0 при делении на 7. Тогда ответ «Да».

Ответ: Да

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

Задача 10#30647Максимум баллов за задание: 4

У числа $2100$ нашли сумму цифр, у результата снова нашли сумму цифр, и т.д. В конце концов получилось однозначное число. Найдите его.

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

Так как остатки у числа и у суммы его цифр при делении на $9$ совпадают, то при проведении операции, описанной в условии, остаток каждого полученного числа при делении на $9$ один и тот же.

Определим, какие остатки при делении на $9$ дает двойка в некоторой степени:

1 2 ≡2 (mod 9) 22 ≡4 (mod 9) 23 ≡8 (mod 9) 24 ≡7 (mod 9) 5 2 ≡5 (mod 9) 26 ≡1 (mod 9) 27 ≡2 (mod 9) 28 ≡4 (mod 9) ...

Таким образом, мы получили цикл остатков $2,4,8,7,5,1$ длиной $6$ . Так как $100≡ 4 (mod 6)$ , то $2100 ≡24 ≡ 7 (mod 9).$ Существует единственное однозначное число, дающее остаток $7$ при делении на $9$ , — это число $7.$

Ответ: 7

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

Задача 11#2012Максимум баллов за задание: 4

Найдите все числа, при делении которых на 5 в частном получится то же число, что и в остатке.

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

Пусть при делении числа $a$ на 5 в частном получится то же число, что и в остатке. Тогда $a= 5r+ r.$ Так как $r$ — это остаток при делении на 5, то $r$ может быть равно только 0, 1, 2, 3 или 4. Для каждого из этих значений $r$ найдем соответствующее значение $a :$

0, 6, 12, 18, 24

Ответ:

0, 6, 12, 18, 24

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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

Задача 12#2013Максимум баллов за задание: 4

Докажите, что если числа $a$ и $b$ дают при делении на $c$ одинаковые остатки, то $(a− b) ..c. .$

Показать доказательство

Исходя из условия, имеем $a= n1c+ r$ и $b= n2c+ r.$ Следовательно,

. a− b= n1c+ r− n2c− r = c(n1 − n2) .. c

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

Задача 13#2126Максимум баллов за задание: 4

Найдите остаток от деления числа $26103+ 3101 − 5103$ на 26.

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

Обозначим остаток от деления числа $N$ на число $m$ через $N (modm ).$

Сначала найдём остаток от деления числа $5103$ на $26$ :

5103(mod26)= (5102⋅5)(mod26)= (2551⋅5)(mod 26).

Так как $25(mod 26)= −1(mod 26)$ , то последнее выражение можно переписать в виде

((−1)51⋅5)(mod 26) =(−5)(mod26)= 21.

Аналогично

101 33 33 3 (mod 26)= (27 ⋅9)(mod 26)= (1 ⋅9)(mod 26)= 9.

Кроме того, понятно, что $26103$ делится на $26$ , тогда

103 101 103 (26 +3 −5 )(mod26)= (0+9−21)(mod 26)= (−12)(mod 26)= 14(mod 26).

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

Ответ: 14

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

Задача 14#16125Максимум баллов за задание: 4

Петя и Вася по очереди выписывают цифры шестисотзначного числа (каждый имеет право ставить цифры в любое место). Начинает Петя. Если полученное в итоге число не делится на семь, то выигрывает Петя, иначе выигрывает Вася. Кто из них может выиграть, как бы ни играл соперник?

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

Заметим, что последний ход сделает Вася. Покажем одну из возможных стратегий Васи.

Все ходы, кроме последнего, Вася делает произвольно, то есть ставит любые цифры на любые места (например, только единицы каждый раз на самое левое свободное поле). Последним ходом перед Васей осталось одно пустое поле). Последним ходом перед Васей осталось одно пустое поле. Пусть после этого поля еще $k$ цифр слева. Будем считать, что пока что на месте этого поля стоит цифра 0. Тогда, когда Вася пишет на месте поля цифру $c$ , он увеличивает шестисотзначное число на $c⋅10k.$ Заметим, что числа $1 ⋅10k, 2⋅10k, 3⋅10k,..., 7⋅10k$ дают различные остатки при делении на 7, так как разность любых двух из этих чисел не делится на 7. А так как этих чисел 7, то они дают все возможные остатки при делении на 7.

Получается, что, написав одну из цифр от 1 до 7 на свободном поле, Вася может прибавить к данному числу любой остаток при делении на 7. В частности, Вася может выбрать такой остаток, чтобы результат делился на 7, тем самым победив.

Ответ:

Вася

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

Задача 15#2127Максимум баллов за задание: 4

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

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

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

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