Алгоритм деления с остатком
Алгоритм деления с остатком — это способ представить число \(a\) в виде суммы произведения делителя \(b\) на частное \(q\) и остатка \(r\). Остаток всегда неотрицателен и меньше делителя.
Формула
Чтобы выполнить алгоритм, разделите \(a\) на \(b\) с остатком: целая часть результата — это \(q\), а оставшаяся часть — \(r\). Затем проверьте равенство \(a=bq+r\) и условие \(r<b\). Если остаток равен нулю, деление выполняется нацело; это связано с понятием остатка при делении.
Разделим \(47\) на \(6\). Наибольшее число, кратное \(6\) и не превосходящее \(47\), — \(42=6\cdot7\). Поэтому \(q=7\), \(r=5\), и \(47=6\cdot7+5\). Проверка: \(0\le5<6\).
Остаток не может быть равен делителю или быть больше него. Запись \(47=6\cdot6+11\) формально даёт правильную сумму, но это не результат деления с остатком: \(11\not<6\). Нужно выделить ещё одну полную группу: \(47=6\cdot7+5\).
Какова запись деления \(38\) на \(7\) с остатком?
Представление \(a=bq+r\) используют в задачах на делимость: если \(r=0\), число \(a\) делится на \(b\) без остатка. Последовательное применение таких делений лежит в основе алгоритма Евклида.
Главное
- Деление с остатком записывают формулой \(a=bq+r\).
- Остаток удовлетворяет условию \(0\le r<b\).
- При \(r=0\) деление выполняется нацело.