Понятие и свойства делимости

Возьмем два целых числа a и b, причем b ≠ 0 (b не равно 0). Если существует целое число q, такое, что a = bq, то говорят, что число a делится на число b или что b делит a. При этом a называется кратным числа b, а b - делителем числа a. Тот факт, что b делит a, обозначается так: b|a. Если же b не делит a, то пишут b†a.

Вот свойства делимости:

1) Целое число делится на само себя a|a.

2) Если a кратно m, а m, в свою очередь, кратен b, то и a кратно b. Это свойство транзитивности делимости.

Действительно: можно записать a = a₁m, m = m₁b. Тогда a = a₁m₁b. И так как a₁m₁ - целое, то a кратно b.

3) Если a делится на c, то его произведение с b тоже будет делиться на c: c|a, c|ab.

4) Если a и b делятся на c, то ax + by, где x, y - целые, тоже делится на c.

5) Если b делит a, то b меньше a по модулю: b|a, то |b| ≤ |a|.

6) Все целые числа делятся на единицу: 1|a.

Всякое целое a можно представить единственным образом через положительное целое b в виде

a = bq + r; 0 ≤ r < b. Это достаточно очевидно. Легче понять это из рисунка. Рассмотрим отрезки длины a (красного цвета), b (синего цвета), r (зеленого цвета). далее вместо отрезок длины a будем говорить просто отрезок a. В случае a > 0 можно откладывать отрезки b вдоль отрезка a до тех пор пока они помещаются в отрезок a. Число отрезков b равно q. Понятно, что если отрезки b больше не помещаются в отрезок a, то отложить можно только отрезок длиной меньше b. Это отрезок r. Для отрицательного a рассуждения аналогичны, только q берем отрицательное. Если в качестве последнего отрезка, откладываемого вдоль отрезка a мы возьмем отрезок b вместо отрезка r, то отрезок, состоящий из суммы отрезков b будет выпирать над отрезком a на величину r.

Например, если r = 0, то получаем деление без остатка. Число q называется неполным частным, а r - остатком от деления a на b.