Не производя деления
Вопрос о том, делится ли данное число n нацело на другое число m, часто возникает в самых разных практических задачах. Один из способов выяснить это состоит в непосредственном делении числа n на число m, однако такой способ далеко не самый легкий. Желание иметь какие-либо критерии, позволяющие устанавливать факт делимости, не прибегая к операции деления, приводит нас к задаче о нахождении наиболее простах признаков делимости.
Напомним, что деление числа n на число m с остатком означает нахождение частного q и остатка r, для которых выполнены условия
n = qm + r, 0 ≤ r < m.
Если r = 0, то говорят, что число n делится на m или кратно m.
Полезно знать следующие несложные факты (если они вам не известны, то попробуйте доказать их самостоятельно):
- а) если два числа отличаются друг от друга на число, кратное m, то остатки от деления этих чисел на m совпадают, и наоборот;
- б) сумма двух чисел имеет тот же остаток от деления на m, что и сумма остатков от деления этих чисел на m;
- в) произведение двух чисел имеет тот же остаток от деления на m, что и произведение остатков от деления этих чисел на m.
- г) если произведение двух чисел, одно из которых взаимно просто с числом m, делится на m, то второе из этих чисел делится на m, и наоборот;
- д) если число делится на каждое из двух взаимно простых чисел, то оно делится и на их произведение.
Источник: Примени математику. И.Н. Сергеев. С.Н. Олехник. С.Б. Гашков. Москва «Наука» 1989.
