Целые числа

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

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

• если 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.