Integers I - 16 Mar 2010
Sergey Sobolev
На сайте кружка
http://mathcircle.csmath.org
на странице задания есть pdf-файл для печати, а в Google Docs
задание разложено по папкам учеников. Его источник -- задание
ВЗМШ, написанное Н.Б.Васильевым и В.Л.Гутенмахером. У меня эта
брошюрка осталась в России, но я взял с сайта журнала "Квант"
близкую к ней статью этих же авторов:
Вагутен В.Н. Алгоритм Евклида и основная теорема арифметики
-- Квант, 1972, N 6
а также полезную статью
Егоров А. Сравнения по модулю и арифметика остатков --
Квант, 1970, N 5 (у автора в "Кванте" есть её переиздание)
и сделал из них pdf-файлы в формате letter, используемом по
умолчанию для распечаток в США (в Европе такую роль играет
близкий формат A4). Эти файлы положены в библиотеку
http://mathcircle.csmath.org/library
Нужно распечатать и читать то, что помогает разобраться с
заданием. Конечно, про делимость и остатки много где написано,
но эти две статьи -- хороший ориентир.
Про арифметику остатков (вычетов) нужно также почитать в книжке
Дынкин Е.Б. и Успенский В.А. Математические беседы.
Она есть в формате djvu в интернете, и издание 2004 года не
отличается от издания 1953 года, которое в интернет-библиотеке
МЦНМО. В 2006 году в США было переиздано английское издание.
В задании три серии задач: "Делимость", "Деление с остатком" и
"Посмотрим на остаток". Сдавать на проверку их нужно по
отдельности, выделив на каждую серию 7-10 дней. Таким образом,
первые две серии должны поспеть к указанному в календаре сроку
16 марта, а третья тоже может поспеть или немного запоздать.
Пожалуйста, отмечайте неточности, опечатки и т.п.
---------------------------------------------------------------
Делимость
Определение. Целое число a делится на целое число d, если
существует целое число k такое, что a=dk. В этом случае говорят
также, что d -- делитель a, или что d делит a, или что a
кратно d. Обозначение: d\mid a (d делит a). В литературе для
школьников и учителей встречается также
a [три вертикальные точки] b (a кратно b).
1. Докажите, что любое шестизначное число вида abcabc
(три первые цифры совпадают с тремя последними) делится на 7,
11 и 13.
2. Докажите, что число a^3-a при любом целом a делится на 3.
Подсказка: это произведение трёх последовательных целых чисел.
3. Докажите, что:
(1) если a и b делятся на d, то a+b и a-b тоже делятся на d;
(2) если a делится на d и c -- любое целое число, то ac тоже
делится на d.
4. Докажите, что если a делится на b, а b делится на c, то a
делится на c.
5. Верно ли, что если число делится на 15 и на 21, то оно
делится на 15*21=315?
6. Выясните, какие из следующих утверждений верные, а какие
нет:
(a) если a и b не делятся на c, то a+b не делится на c;
(b) если a делится на c, а b не делится на c, то a+b не
делится на c;
(c) если a и b не делятся на c, то ab не делится на c;
(d) если ab делится на c, то хотя бы одно из чисел a и b
делится на c.
Верное утверждение докажите, а для неверного укажите значения
a, b и c, при которых оно неверно.
7. Докажите, что если a+b делится на c и ab делится на c, то
a^2+b^2 делится на c и a^3+b^3 делится на c^2.
8. Докажите, что если ab+cd делится на a+c, то и ad+bc делится
на a+c.
9. Целые числа a и b таковы, что число 3a+5b делится на 7.
Докажите, что число 4a+9b тоже делится на 7.
10. Докажите, что a^4+4b^4 делится на a^2+2ab+2b^2.
Деление с остатком
Определение. Пусть a и b -- целые числа, b>0. Разделить с
остатком a на b -- значит найти такие целые числа q и r, что
a=bq+r и 0\le r<b. Число r называется остатком, а число q --
частным. [Здесь \le -- знак "меньше или равно"]
Пример. Разделим с остатком -11 на 4. Имеем: -11=4*(-3)+1.
Отсюда остаток равен 1, а частное равно -3.
Теорема. Разделить a на b с остатком можно, и притом
единственным образом (то есть для любых целых чисел a и b, где
b>0, числа q и r из определения деления с остатком существуют и
единственны).
1. Разделите с остатком: (a) 1000 на 17; (b) -1000 на 17.
2. Пусть r -- остаток от деления a на b. Чему равен остаток от
деления -a на b?
3. Объясните, верно или нет утверждение:
(a) Если число при делении на 15 даёт в остатке 7, то при
делении на 5 оно даёт в остатке 2;
(b) Если число при делении на 5 даёт в остатке 3, то и при
делении на 15 оно даёт в остатке 3.
4. Найдите наибольшее целое число n, такое что 17n<1000.
5. Пусть n -- целое положительное число.
(a) Какой остаток даёт число 4n+7 при делении на число 2n+1?
(b) Какой остаток даёт число 2n^2+3n+3 при делении на
число n+2?
Подсказка: будьте внимательны, ответ зависит от n.
6. Почему произведение двух нечётных чисел нечётно?
7. Числа a и b дают остатки 5 и 7 при делении на 9. Можно ли по
этим данным определить, какие остатки дают числа a+b и ab при
делении на 9?
8. На какую цифру оканчивается число 7^{2010}?
9. Найдите остатки от деления 2^{1000} на 3, 5 и 7.
Посмотрим на остаток
1. (a) Какие остатки может давать квадрат целого числа при
делении на 4?
(b) Докажите, что число вида 4n+2, где n целое, не может
быть квадратом целого числа.
2. Какие остатки может давать квадрат целого числа при делении
на 3?
3. Прямоугольный треугольник называется пифагоровым, если длины
его сторон -- целые числа. Докажите, что в пифагоровом
треугольнике хотя бы один из катетов чётный и хотя бы один
делится на 3.
Подсказка. Используйте теорему Пифагора. Могут ли оба катета
пифагорова треугольника быть нечетными? Если мы допустим это,
то квадрат гипотенузы будет давать остаток 2 при делении на 4,
а такого у квадрата целого числа не может быть.
4. Докажите, что число a^5-a при любом целом a делится на 5.
5. Докажите, что если a^2+b^2 делится на 7, то a и b делятся
на 7.
6. Докажите, что если a^2=2b^2 (a и b целые), то a и b чётные.
Трудный вопрос: при каких целых a и b возможно, что a^2=2b^2?
---------------------------------------------------------------
С.Соболев