Делимость целых чисел и остатки
Теория > Олимпиада
В задачах про целые числа используются основные понятия и теоремы, связанные с делимостью чисел.
Каждое целое число а можно разделить на натуральное число m с остатком, то есть представить в виде а = mq + r, где q и r – целые числа и r (остаток) не меньше 0, но меньше q.
При этом число r называется остатком от деления a на q, а m — неполным частным.
Среди любых m последовательных целых чисел найдется ровно одно число, делящееся на m.
ПРИМЕР
42 делится на 9 с остатком 6: 42 = 9⋅4+6.
Числа 17 и -17 дают разные остатки при делении на 5: 17 = 5⋅3 + 2, но −17 =5⋅(−4)+3.
Различные натуральные числа при делении на натуральное m могут давать любой из остатков 0, 1, 2, ..., m–1. Однако степени натуральных чисел с фиксированным натуральным показателем n >1 не обязательно снова могут давать при делении на m любой из этих остатков. Так при делении на 3, 4, 5 и 8 четвёртые степени целых чисел могут давать остатки только 0 и 1. Ниже приведена таблица возможных остатков при делении квадратов, кубов, четвертых и пятых степеней на числа от 3 до 10.
| Остатки,которые могут a n : m | n (показатель степени целого числа) | ||||
| 2 | 3 | 4 | 5 | ||
|
| 3 | 0; 1 | 0; 1; 2 | 0; 1 | 0; 1; 2 |
| 4 | 0; 1 | 0; 1; 3 | 0; 1 | 0; 1; 3 | |
| 5 | 0; 1; 4 | 0; 1; 2; 3; 4 | 0; 1 | 0; 1; 2; 3; 4 | |
| 6 | 0; 1; 3; 4 | 0; 1; 2; 3; 4; 5 | 0; 1; 3; 4 | 0; 1; 2; 3; 4; 5 | |
| 7 | 0; 1; 2; 4 | 0; 1; 6 | 0; 1; 2; 4 | 0; 1; 2; 3; 4; 5; 6 | |
| 8 | 0; 1; 4 | 0; 1; 3; 5; 7 | 0; 1 | 0; 1; 3; 5; 7 | |
| 9 | 0; 1; 4; 7 | 0; 1; 8 | 0; 1; 4; 7 | 0; 1; 2; 3; 4; 5; 6; 7; 8 | |
| 10 | 0; 1; 4; 5; 6; 9 | 0; 1; 2; 3; 4; 5; 6; 7; 8; 9 | 0; 1; 5; 6 | 0; 1; 2; 3; 4; 5; 6; 7; 8; 9 | |
Если два числа а и b при делении на число m дают одинаковые остатки, то говорят, что а сравнимо с b по модулю m. Записывают это так а ≡ b (mod m )
|
|
|
Если a > b, то наибольший общий делитель a и b равен наибольшему общему делителю a – b и b.
Рассмотрим эти свойства при решении задач:
ЗАДАЧИ
1. Сколько существует натуральных чисел, меньших 1000, которые не делятся ни на 5, ни на 7?
Решение: Вычёркиваем из 999 чисел, меньших 1000, числа, кратные 5: их 199 (999/5 = 199). Далее вычёркиваем числа, кратные 7: их 142 (999/7 = 142). Но среди чисел, кратных 7, имеется 28 (999/35 = 28) чисел, одновременно кратных 5; они будут вычеркнуты дважды. Итого, нами должно быть вычеркнуто 199 + 142 – 28 = 313 чисел.
Остаётся 999 – 313 = 686. Ответ: 686 чисел.
2. Найдите остаток от деления 2009⋅2010⋅2011+20122 на 7.
Решение задачи
Учитывая, что 2009⋮7, то остаток будет равен 20122 ≡ 32 ≡ 2(mod7)
3. Известно, что остаток от деления числа aa на 19 равен 7, а числа b на 19 — равен 11. Найдите остаток от деления на 19 числа ab(a+b)(a−b).
Решение задачи
Заметим, что ab(a+b)(a−b )≡ 7⋅11⋅18⋅(−1) ≡ 7⋅(−8)⋅(−1)⋅(−4) =−224 = −228+4 ≡ 4(mod19)
|
|
|
4. Докажите, что сумма квадратов трёх целых чисел не может при делении на 8 дать в остатке 7.
Решение
Любое целое число при делении на 8 имеет остатком одно из следующих восьми чисел 0, 1, 2, 3, 4, 5, 6, 7, поэтому квадрат целого числа имеет остатком при делении на 8 одно из трёх чисел 0, 1, 4. Чтобы при делении на 8 сумма квадратов трёх чисел имела остаток 7, необходимо, чтобы выполнялся один из двух случаев: либо один из квадратов, либо все три при делении на 8 имеют нечётные остатки.
В первом случае нечётный остаток есть 1, а сумма двух чётных остатков равна 0, 2, 4, то есть сумма всех остатков равна 1, 3, 5. Остатка 7 в этом случае получить нельзя. Во втором случае три нечётных остатка это три 1, и остаток всей суммы равен 3. Итак, 7 не может быть остатком при делении на 8 суммы квадратов трёх целых чисел.
5. Существуют ли такие натуральные nn, что n2+n+1 делится на 2014?
Решение задачи
Заметим, что n2 + n = n(n+1) делится на 2, поскольку является произведением двух подряд идущих чисел, а значит n2+n+1 всегда нечетно (также это можно было заметить, используя малую теорему Ферма: n2 + n + 1 ≡ n + n+1 = 2n + 1 ≡1 (mod 2).
Поскольку число 2014 четное, то не существует таких n, что число n2 +n+1 делится на 2014 (если бы такие n существовали, то это бы противоречило тому, что n2+n+1 — нечетное).
|
|
|
6. Существует ли десятизначное число, делящееся на 11, в записи которого каждая цифра встречается по одному разу?
Решение
I способ. Выписывая трёхзначные числа, делящиеся на 11, можно среди них найти три числа, в записи которых участвуют все цифры от 0 до 9. Например, 275, 396,418. С их помощью можно составить десятизначное число, делящееся на 11. Например:
2753964180 = 275·107 + 396·107 + 418·10 = 11·(25·107 + 36·104 + 38·10).
II способ. Для нахождения требуемого числа воспользуемся признаком делимости на 11, согласно которому числа n = a1a2a3…a10 (в данном случае аi не множители, а цифры в записи числа n) и S(n) = a1–a2+a3–…–a10 одновременно делятся на 11.
Пусть А – сумма цифр, входящая в S(n) со знаком «+», В – сумма цифр, входящая в S(n) со знаком «–». Число А–В, согласно условию задачи, должно делиться на 11. Положим В – А = 11, кроме того, очевидно, А + В = 1+2+3+…+9 = 45. Решая полученную систему В – А =11, А + В = 45, находим, А =17, В = 28. Подберём группу из пяти различных цифр с суммой 17. Например, 1+2+3+5+6 = 17. Эти цифры возьмём в качестве цифр с нечётными номерами. В качестве цифр с чётными номерами возьмём оставшиеся – 4, 7, 8, 9, 0.
|
|
|
Мы видим, что условию задачи удовлетворяет, например, число 1427385960.
7. Найдите наименьшее натуральное число, дающее такой же остаток при делении на 25, какой дает число 1234.
Решение
Рассмотрим остаток при делении числа 1234 на 25. Все числа, меньшие, чем он, дают другие остатки, поскольку сами являются своими остатками. Остаток при делении 1234 на 25 это 9, так как 1234=49⋅25+9, это и будет ответом.
8. Получив двойку по географии, Вася решил порвать географическую карту в клочья. Каждый попавший ему в руки клочок он рвет на четыре части. Может ли он когда-нибудь получить ровно 2012 кусков? 2013 кусков? 2014 кусков? 2015 кусков?
Решение задачи
Заметим, что каждый раз Вася увеличивает число кусков на 3, так как он один кусок превращает в четыре. Поэтому он будет получать числа вида 1+3N, где N - количество кусков, которые он рвал на части. Число 2014 имеет такой вид, поэтому 2014 кусков у него получится, а другие не представимы в таком виде (у них остатки при делении на 3 равны 0 или 2).
9. Найдите наименьшее натуральное число, дающее следующие остатки: 1 — при делении на 2, 2 — при делении на 3, 3 — при делении на 4, 4 — при делении на 5, 5 — при делении на 6.
Решение задачи
Рассмотрим искомое число, увеличенное на единицу. Оно делится на 2,3,4,5,6, т.к. оно дает остатки, меньшие на единицу, чем сами делители. Нам необходимо найти минимальное такое число, следовательно, искомое число есть наименьшее общее кратное чисел 2,3,4,5,6 минус 1. Наименьшее общее кратное 2,3,4,5,6 равно 22⋅3⋅5=60 , т.к. в числах 2,3,4,5,6 есть только 3 простых делителя, тройка и пятерка входят максимум в первой степени, а двойка во второй (в числе 4). Значит, искомое число равно 60−1 = 59.
.
Дата добавления: 2018-11-24; просмотров: 548; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!