Не производя деления

Вопрос о том, делится ли данное число 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.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *