Элективный курс 7 класс Март, 2025
Сравнение по модулю Везде далее a, b ∈ Z, m ∈ N. Числа a и b называются сравнимыми по модулю m, если (a−b) делится на m. Иными словами, a сравнимо с b по модулю m, если числа a и b имеют одинаковые остатки при делении на m. Обозначение a ≡ b (mod m). Примеры: 13 ≡ 37 ( mod 6) ; −12 ≡ 3 (mod 5) ; 13 ≡ 5 (mod 4).
Теорема 1 Пусть a ≡ b (mod m), c ≡ d (mod m). Тогда a + c ≡ b + d (mod m) ; a − c ≡ b − d (mod m) ; ac ≡ bd (mod m). Доказательство: Пусть a − b = pm, c − d = qm, где p, q ∈ Z. Тогда ( a + c) − (b + d) = a + c − b − d = (a − b) + (c − d) = pm + qm = m (p + q). Это выражение делится на m. (a − c) − (b − d) = a − c − b + d = (a − b) − (c − d) = pm − qm = m (p − q) делится на m; ac − bd = ac − bc + bc − bd = c (a − b) + b (c − d) = cpm + bqm = m (cp + bq ) делится на m. Значит a + c ≡ b + d (mod m) ; a − c ≡ b − d (mod m) ; ac ≡ bd (mod m).
Следствие 1 Пусть a ≡ b (mod m). Тогда a ² ≡ b ² (mod m) ; a ³ ≡ b ³ (mod m) ; · · · ≡ (mod m), n ∈ N. Иначе говоря, обе части сравнения можно возводить в любую натуральную степень. Примеры: 16 ≡ 9 ( mod 7) ⇒ 256 ≡ 81 (mod 7) ; 5 ≡ 2 (mod 3) ⇒ 125 ≡ 8 (mod 3) ; 10 ≡ 3 (mod 7) ⇒ 10000 ≡ 81 (mod 7).
Задача. Доказать, что для любого натурального n: а) б) в) Решение: а) б) в)
Задача Доказать, что − делится на 27. Число 10 бессмысленно сравнивать по модулю 27, поэтому представим Заметим, что 100 ≡ 19 ≡ −8 ( mod 27), откуда получаем
Задача. Найти остаток от деления на 19 Заметим, что Ответ: 11.
Теорема 2 (Малая теорема Ферма) Пусть p — простое число, тогда для любого натурального а или Доказательство. Рассмотрим два случая: a делится на p ; a не делится на p. 1) a делится на p ; Тогда используя сравнения запишем: a ≡ 0 ( mod p ); a p ≡ 0 ( mod p ); Или a p ≡ a ( mod p ) В этом случае теорема доказана. .
2) a не делится на p ; Рассмотрим числа a, 2 a, 3 a,...,( p - 1) a (*). Покажем, что эти числа дают разные остатки при делении на p. Очевидно, остаток также не может быть 0. Докажем от обратного. Пусть какие-то два числа ka, na имеют одинаковые остатки при делении на p (пусть k > n ). Тогда разность ka - na делится на p. Значит ( k - n ) a делится на p. Но a не делится на p, а разница k - n меньше p и отлична от нуля, потому также не делится на p. Мы пришли к противоречию - наше предположение, что числа (*) могут давать одинаковые остатки при делении на p ошибочно. Запишем это: a ≡ r 1 ( mod p ); 2 a ≡ r 2 ( mod p ); ... ( p - 1) a ≡ r p - 1 ( mod p ); Используя свойства сравнения перемножаем предыдущие сравнения. Так как всего множителей p - 1, а все остатки при делении на p разные, то справа будет ( p - 1)! a p - 1 ( p - 1)! ≡ ( p - 1)! ( mod p ); ( a p - 1 - 1)( p - 1)! ≡ 0 ( mod p ); Но ( p - 1)! не делится на p, так как p - простое, а все множители факториала меньше p. Значит ( a p - 1 - 1) делится на p. ( a p - 1 - 1) ≡ 0 ( mod p ); a p - 1 ≡ 1 ( mod p ); a p ≡ a ( mod p ); Что и требовалось доказать.
Задача. Докажите, что делится на 143 Решение. Докажем, что и По теореме Ферма По свойствам делимости, если и то
Задача. Пусть n – натуральное число, не кратное 17. Докажите, что либо n 8 + 1, либо n 8 – 1 делится на 17. Решение. По теореме Ферма а значит один из множителей делится на 17.
Задача. Докажите, что при любом целом a : a 5 - a делится на 30. Решение. С одной стороны по теореме Ферма с другой стороны Т.к.произведение трех последовательных натуральных чисел делится на 6. Если число делится на 5 и на 6, то оно делится и на 30
Задача. Докажите, что для любого целого числа a число a 561 - a делится на 561. Решение По малой теореме Ферма, при любом целом a и простом p число a p - a делится на p (или a p-1 -1 делится на p при a, не делящемся на p ). Также будем пользоваться тем фактом, что x n -1 делится на x-1 при любом целом x и любом натуральном n. (Это следует из разложения x n - 1=( x - 1)(x n-1 + x n-2 +... + x + 1).) Прямо теоремой Ферма воспользоваться нельзя, так как 561=3*11*17 - составное число. Докажем вначале, что a 561 - a делится на 17. Если a делится на 17, то все ясно. Если нет, то a 561 -a = a (a 560 -1) = a ((a 16 ) 35 -1) делится на a 16 -1, что в свою очередь делится на 17 по теореме Ферма (можно в этом убедиться и непосредственно, перебирая остатки от деления на 17). Таким же образом, используя, что 561 - 1=560 делится на11-1=10 и 3 - 1=2, доказываем, что a 561 -a делится на 11 и на 3. Если число делится на 17, на 11 и на 3, то оно делится на 561=3*11*17.
Задача. Написано 1992‐значное число. Каждое двузначное Ч исло, образованное соседними цифрами, делится на 17 или на 23. Последняя цифра числа 1. а) Делится ли данное число на 3? б) Какова первая цифра числа? Решение. Выпишем все двузначные числа, делящиеся на 17 или 23. Это 17, 34, 51, 68, 85, 23, 46, 69, 92. У всех этих чисел последние цифры различны, значит, искомое число мы сможем восстановить однозначно. Последняя цифра 1, значит, соответствующее двузначное чисто 51, т.е. предыдущая цифра в числе 5. Эта цифра 5 соответствует двузначному числу 85, следовательно, перед ней стоит цифра 8.
Рассуждая аналогично, получим ряд из девяти последних цифр числа: 692346851. Набор 92346 будет теперь всё время повторяться. Всего же цифр 1992, в том числе: 3 последние, 5 цифр из периода, встречающиеся 397 раз, и ещё 4 цифры — последние 4 цифры периода, они же — первые 4 цифры числа. Таким образом, первая цифра искомого числа 2. Найдем сумму цифр этого числа: 2 + 3 + 4 + 6 + 397(9 + 2 + 3 + 4 + 6) + 8 + 5 + 1 = 9557. Это число не делится на 3, значит и данное в условии число не делится на 3. Ответ: а) нет; б) 2.
Задача. Можно ли расставить числа а) от 1 до 7; б) от 1 до 9 по кругу так, чтобы любое из них делилось на разность своих соседей? Решение. а) Например, так: -1-5-6-2-7-3-4- б) Заметим, что нечётное число не делится на чётное, а значит, не может стоять в окружении чисел одинаковой чётности. Отсюда следует, что нечётные числа стоят парами. Однако среди чисел 1, 2,..., 9 нечётных чисел пять, и поэтому из них нельзя образвать пары. Ответ: а) да; б) нет.
Задача. Даны натуральные числа а, b и с такие, что a > b > c. Среднее арифметическое этих чисел делится на 13. а) Найдите наименьшую сумму а +b + с такую, что она является квадратом натурального числа. б) Найдите наибольшее значение числа c, если a =32 и сумма а +b + с имеет наименьшее значение. в) Найдите наименьшее число b, если известно, что числа c, b и а в указанном порядке составляют арифметическую прогрессию с разностью n. г) Если известно, что числа c, b и a в указанном порядке составляют возрастающую арифметическую прогрессию с разностью n при котором число c будет наименьшим, и все члены арифметической прогрессии будут являться квадратами натурального числа.
а) По условию где k – натуральное. Значит, a + b + c = 39k. Таким образом, a + b +c является квадратом и делится на 39 = 13 3 поэтому минимальное возможное значение a + b + c = 39² =1521 б) Из пункта а) получаем, что b + c = 39k - 32. Если сумма a + b + c минимальна, то и b + c минимально, значит k = 1 и b + c = 7 Вспомнив, что по условию b < c получаем, что c < 3 в) По условию a + b + c = 39k, а из того, что c, b, a — арифметическая прогрессия, следует равенство b – c = a – b или 2 b = a + c или a + b + c = 3b Значит, 3b=39k или b=13 k. b должно быть минимально, поэтому b=13
в) Пусть с = p²,b = q²,a = r². Тогда 2q² = r² + p². Из предыдуще г о пункта q кратно 13. Если n и c минимально, то и b должно быть минимально, значит p² + q² = 2 169 = 338. Подбором получаем, что единственная пара чисел (p, q) такая, что p<q и удовлетворяющая последнему равенству это p = 7,q = 17. Тогда получаем, что n=b-c=169-49=120
В вершинах треугольника записано по натуральному числу, на каждой стороне — произведение чисел, записанных в её концах, а внутри треугольника — произведение чисел, записанных в его вершинах. Сумма всех семи чисел равна 1000. Какие числа записаны в вершинах треугольника? Решение. Пусть в вершинах треугольника стоят числа a, b и с. Из условия следует равенство: a + b +c + ab + bc + ac + abc = 1000 Добавим к обеим частям единицу: a + b +c + ab + bc + ac + abc+1 = 1001 (c+1)+(c+1)a+(c+1)b+(c+1) ab =1001 (c+1)(1+a+b+ab)=7 11 13 (c+1)(a+1)(b+1)= 7 11 13
Ясно, что все скобки в левой части больше единицы, а все множители в правой части — простые числа. Значит, с точностью до перестановки, числа a + 1 , b +1 и с+1 равны 7, 11, 13. Значит числа в вершинах треугольника на единицу меньше и равны 6, 10, 12.
Задача. Можно ли привести пример пяти целых чисел, произведение которых равно 720 и а) пять из них; б) три из них образуют геометрическую прогрессию? Решение. Предположим, что существует пять чисел, образующих геометрическую прогрессию и произведение их равно 720, т.е. но 720 не является пятой степенью никакого целого числа. Разложим 720 на множители: Из этих чисел только три могут образовать геометрическую прогрессию 1, 2, 4 Получим произведения пяти чисел:
Задача. На доске написано число 7. Раз в минуту Вася дописывает на доску одно число: либо вдвое большее какого-то из чисел на доске, либо равное сумме каких-то двух чисел, написанных на доске (таким образом, через одну минуту на доске появится второе число, через две ― третье и т.д.). а) Может ли в какой-то момент на доске оказаться число 2012? б) Может ли в какой-то момент сумма всех чисел на доске равняться 63? в) Через какое наименьшее время на доске может появиться число 784?
Решение. 1. Каждое число на доске будет делиться на 7. Действительно, исходное число делится на 7, в случае удвоения числа делящегося на 7, получится число, делящееся на 7. А при сложении чисел, делящихся на 7, также получится число, делящееся на 7. Таким образом, все числа на доске будут делиться на 7, а 2012 на 7 не делится, следовательно, оно не может появиться на доске. 2. В условии не сказано, что одно число нельзя удваивать несколько раз, поэтому получим: или 7+14+14+14+14=63
Покажем, что за 7 минут число 112 из 1 получить невозможно. . 1 1,2 1,2,4 1,2,4,8 1,2,4,8,16 1,2,4,8,16,32 1,2,4,8,16,32, 64 1,2,4,8,16,32,64,128 или 1,2,4,8,16,32,64,96 Приведем пример, как его получить за 8 минут: 1 1,2 1,2,4 1,2,4,8 1,2,4,8,16 1,2,4,8,16,32 1,2,4,8,16,32,64 1,2,4,8,16,32,64,96 1,2,4,8,16,32,64,96,112 Все числа на доске будут делиться на 7. Рассмотрим аналогичную задачу, разделив исходное число 7 и то число, которое нужно получить, т.е. 784, на 7. От этого количество операций не изменится. Таким образом, достаточно за наименьшее количество операций получить число 112, начав с числа 1.
