Целые числа

Истоки: Н.Б.Васильев и В.Л.Гутенмахер, "Целые числа" — задание ВЗМШ при МГУ. Про арифметику остатков полезно посмотреть книгу Е.Б.Дынкина и В.А.Успенского "Математические беседы" и статьи А.Егорова в "Кванте". Подробности — на сайте кружка. Несколько задач из задания:

∗ Выясните, какие из следующих утверждений верные, а какие нет:

• если a и b не делятся на c, то a + b не делится на c;
• если a делится на c, а b не делится на c, то a + b не делится на c;
• если a и b не делятся на c, то ab не делится на c;
• если ab делится на c, то хотя бы одно из чисел a и b делится на c.

Верное утверждение докажите, а для неверного укажите значения a, b и c, при которых оно неверно.

∗ Докажите, что если a + b делится на c и ab делится на c, то a² + b² делится на c и a³ + b³ делится на c².

∗ Найдите остатки от деления 2¹⁰⁰⁰ на 3, 5 и 7.

∗ Какие остатки может давать квадрат целого числа при делении на 3?

∗ Докажите, что в пифагоровом треугольнике хотя бы один из катетов чётный и хотя бы один делится на 3.

∗ Докажите, что если a² + b² делится на 7, то a и b делятся на 7.

Комбинаторика I

Номера с возрастающим порядком цифр

∗ Сколько трехзначных номеров с различными цифрами?

∗ Пусть a, b и c — три различные цифры. Сколько различных трехзначных номеров можно составить из них?

∗ Сколько трехзначных номеров с возрастающим порядком цифр (первая цифра меньше второй, вторая меньше третьей)?

∗ На окружности отмечено 10 точек. Сколько имеется треугольников с вершинами в этих точках?

∗ Докажите, что семизначных номеров с возрастающим порядком цифр столько же, сколько и трехзначных номеров с возрастающим порядком цифр.

∗ Сколько имеется трёхзначных номеров, в которых третья цифра больше первых двух? А в которых третья цифра наибольшая (т.е. не меньше первых двух)?

Использовано задание ВЗМШ, написанное Н.Б.Васильевым и В.Л.Гутенмахером по материалам бесед И.М.Гельфанда со школьниками (1971-72 г.).