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

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

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

Если числа a и b дают одинаковые остатки при делении на число m, то говорят, что a сравнимо с b по модулю m и записывают a=b (mod m).

Два числа a и b сравнимы по модулю m тогда и только тогда, когда их разность делится на m.

Сравнения можно складывать и умножать. Если a = b (mod m) и c = d (mod m), n — произвольное натуральное число, то a + c = b + d (mod m), ac = bd (mod m) и aⁿ=bⁿ(mod m).

Каждое число сравнимо ровно с одним из чисел 0, 1, ..., m – 1 по модулю m.

Натуральное число называется простым, если у него только два делителя - единица и оно само p. Натуральное число n называется составным, если у него более двух делителей. Единица не является ни простым, ни составным. Например 2, 3, 5, 7 — простые числа, а 4 = 2 · 2, 6, 8, 9 — составные.

Приведём решение задачи 10 занятия 8. Посмотрим, какие остатки может давать квадрат числа при делении на 8. Для этого достаточно посмотреть только остатки чисел 0, 1, ..., 7, так как если a=b(mod m), то a²=b²(mod m): 1²=3²=5² =7² =1(mod 8);  2²=6²=4(mod 8);  0²=4²=0(mod 8). Откуда видно, что сумма трёх квадратов не может быть сравнима с 7 по модулю 8, в частности не может быть равна 1999, так как 1999=7(mod 8).

Приведём решение задачи 10 занятия 4. Так как 8=1(mod 7), то 8¹⁰¹+8¹⁰²+...+8¹⁰⁷ = 1¹⁰¹+1¹⁰²+...+1¹⁰⁷ = 1+1+...+1=7=0(mod 7), то есть делится на 7.