МАЛЫЙ МЕХМАТ МГУ

Занятие 19. Делимость и остатки

Определение 1. Целое число a делится на натуральное число b, если существует такое целое число q, что a = bq.

Определение 2. Пусть даны целое число a и натуральное число b. Тогда поделить a на b с остатком — значит найти такие целые числа q и r, что a = bq + r и 0 ≤ r < b. Такая пара чисел всегда существует и единственна. Число q называют (неполным) частным, а r — остатком от деления a на b. Остаток равен нулю в тех и только тех случаях, когда a делится на b.

Определение 3. Говорят, что число a сравнимо с числом b по модулю m, и пишут a=b(mod m), если a и b дают одинаковые остатки при делении на m. Очевидно, что каждое целое число a сравнимо с одним из чисел 0, 1, 2, ..., m – 1 по модулю m.

1.	Разделите с остатком число –1 на число 1000.
2.	а) Докажите, что a = b (mod n) тогда и только тогда, когда a – b делится на n. б) Докажите, что найдется число вида 11...100...0, которое делится на 2003.
3.	Докажите, что если a=b (mod m), c=d (mod m), n – произвольное натуральное число, то а) a+c=b+d (mod m), б) ac=bd (mod m), в) aⁿ=bⁿ (mod m).
4.	Какие остатки может давать квадрат натурального числа при делении а) на 3; б) на 4; в) на 8?
5.	Может ли сумма квадратов двух целых чисел, не кратных 3, быть квадратом целого числа?
6.	Может ли сумма квадратов трех нечетных чисел быть квадратом целого числа?
7.	Может ли сумма квадратов трех целых чисел быть равна 1999?
8.	Целые числа x, y, z таковы, что x² + y² = z². Докажите, что одно из этих чисел кратно трём.
9.	Докажите, что число 8¹⁰¹ + 8¹⁰² + ... + 8¹⁰⁷ делится на 7.
10.	Докажите, что среди любых пяти целых чисел найдутся два числа, у которых либо сумма, либо разность делится на 7.
11.	Можно ли найти 1000000 подряд идущих натуральных чисел, среди которых нет ни одного простого числа?