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

19.07 Остатки

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

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

Задача 1#719

Найдите все натуральные числа, при делении которых на 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

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

Задача 2#720

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

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

Пусть число a  при делении на 8  дает остаток 5  , тогда a = 8b + 5 = 8b + 4 + 1 = 4(2b + 1) + 1  , тогда a  при делении на 4  дает остаток 1  .

Ответ:

1

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

Задача 3#2014

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

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

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

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

         2
(3m  + 1) =  (3m + 1 ) ⋅ (3m + 1)
на       3  равен остатку от деления 1 ⋅ 1  на 3  , то есть равен 1  .

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

         2
(3m  + 2) =  (3m + 2 ) ⋅ (3m + 2)
на       3  равен остатку от деления 2 ⋅ 2  на 3  , то есть равен 1  .

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

    2      2
(3m ) = 9m
на       3  равен 0  .

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

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

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

Задача 4#2015

При каких простых p  число p2 + 26  также является простым?

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

Проверим, каким может быть остаток от деления числа 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  – простое.

Ответ:

∅

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

Задача 5#30639

Какие остатки при делении на 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

Докажите, что если сумма квадратов двух целых чисел делится на 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

Может ли сумма 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

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

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

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

Ответ: Нет

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

Задача 9#30643

Верно ли, что из пяти целых чисел всегда можно выбрать два таких, разность квадратов которых делится на 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

У числа 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

Найдите все числа, при делении которых на 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

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

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

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

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

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

Задача 13#2126

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

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

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

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

5103(mod26 ) = (5102 ⋅ 5)(mod26 ) = (2551 ⋅ 5)(mod26 ).
Так как 25(mod26 ) = − 1(mod26 )  , то последнее выражение можно переписать в виде
((− 1)51 ⋅ 5 )(mod26 ) = (− 5)(mod26 ) = 21.

Аналогично

3101(mod26  ) = (2733 ⋅ 9)(mod26 ) = (133 ⋅ 9)(mod26 ) = 9.

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

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

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

Ответ: 14

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

Задача 14#16125

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

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

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

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

Ответ:

Вася

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

Задача 15#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  .
Ответ: Последний выписанный переход неверен
Рулетка
Вы можете получить скидку в рулетке!