Математика · объяснение и практика

Как делить отрицательное целое с неотрицательным остатком

Находим целое частное при отрицательном делимом, удерживаем остаток в заданных границах и доказываем, что подходящая пара единственна.

Синяя и оранжевая половины складываются в целый круг.

В теме Целые, рациональные числа и степени · Учебная карта

Главная мысль

При положительном делителе b запись a = bq+r с 0 ≤ r < b требует округлить a/b вниз. Для отрицательного a это отличается от отбрасывания дробной части: например, −23 = 6·(−4)+1.

Сначала договориться о знаке делителя

Деление с остатком задаёт не только равенство, но и ограничение на остаток. Здесь делитель — положительное целое число. Нужно найти целые q и r так, чтобы a = bq+r, а r был неотрицательным и меньше b. При таком соглашении остаток обозначает расстояние вправо от ближайшего кратного b, не превосходящего a.

На числовой прямой отметим кратные шести: −30, −24, −18, −12. Число −23 находится между −24 и −18. Подходящее нижнее кратное равно −24, поэтому частное равно −4. До −23 остаётся пройти одну единицу. Пара q = −3, r = −5 тоже даёт исходное равенство, однако нарушает условие на остаток. При усечении частного к нулю отрицательный остаток исправляется заменой q на q−1 и r на r+b: равенство сохраняется.

Почему частное округляется вниз

Разделим ограничения на положительное b. Из равенства следует a/b = q+r/b, причём дробная добавка лежит от нуля включительно до единицы исключительно. Поэтому q — наибольшее целое, не превосходящее a/b. Это определение округления вниз, которое часто обозначают floor. Направление округления не зависит от того, где расположен ноль.

Если число делится нацело, дополнительного шага не нужно. Так, −24/6 = −4, и остаток равен нулю. Если же обычный калькулятор показывает −3,833…, число −3 больше точного частного и не подходит. Прибавление ещё одной отрицательной единицы к q увеличивает остаток на b и возвращает его в нужный диапазон.

Пример

Разделите −38 на 7 с неотрицательным остатком.

Кратное −42 не превосходит −38, следующее кратное −35 уже больше. Поэтому q = −6, r = 4. Проверка: 7·(−6)+4 = −38 и 0 ≤ 4 < 7.

Что делает ответ единственным

Предположим, что нашлись две допустимые записи a = bq+r и a = bq′+r′. Вычитая, получаем b(q−q′) = r′−r. Правая часть по модулю меньше b, потому что оба остатка лежат между нулём и b. Но ненулевое целое кратное b имеет модуль не меньше b. Значит, обе части равны нулю и пары совпадают.

В программировании соглашения об остатке различаются, поэтому формулу лучше проверять вместе с границами. Для целых Python при положительном b операции // и % соответствуют рассмотренному правилу. Отрицательный делитель требует отдельно определить диапазон остатка; переносить на него условие 0 ≤ r < b нельзя. Указание соглашения предотвращает спор между разными корректными алгоритмами.

От чтения к действию

А теперь — вы

Для a = −29 и b = 5 найдите q и r при условии 0 ≤ r < 5.

Частые вопросы

Можно просто убрать минус, разделить и вернуть знак?

Для частного это может потребовать дополнительного уменьшения на единицу. Надёжнее восстановить равенство и отдельно проверить неотрицательный остаток.

Почему остаток не может равняться делителю?

Такой остаток позволил бы увеличить частное на единицу и заменить остаток нулём; выбранный диапазон исключает двойную запись.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться