Делимость
Делимость - одно из основных понятий, изучаемых в теории чисел. Говорят, что целое число а делится на целое b, если существует такое целое число с, что а = bc. Например, 54 делится на 6, так как 54 = 6*9; 273 делится на 21, так как 273 = 21*13. Из определения делимости следует, что число 0 делится на любое число, включая 0, но ни одно целое число, отличное от нуля, на нуль не делится.
Часто утверждение о делимости числа а на число b выражают другими равнозначными словами: а кратно b, b-делитель а, b делит а. Для обозначения делимости а на b обычно пользуются записью b/a.
Всякое целое число а делится по крайней мере на четыре числа а, -а, 1, -1. Если а -простое число, то никаких других делителей оно не имеет.
Приведем несколько свойств делимости:
- если числа а и b делятся на с, то и числа а + b, а - b делятся на с;
- если а делится на b и с – произвольное целое число, то ас делится на bc;
- если а делится на b и b-на с, то а делится на с.
Зная разложения чисел а и b на простые множители, можно легко выяснить, делится ли а на b. Для того чтобы число а делилось на число b, необходимо и достаточно, чтобы каждый простой множитель, входящий в разложение числа b, входил и в разложение числа а; причем если простой множитель встречается k раз в разложении числа b, то он должен встретиться не менее k раз и в разложении числа а.
Если целые числа а и b заданы своими записями в десятичной системе счисления, то, разделив «в столбик» первое число на второе, мы найдем их частное, а значит, сможем ответить на вопрос, делится ли а на b.
Уже давно были найдены признаки делимости чисел, которые позволяют в некоторых случаях быстро установить делимость одного числа на другое, не прибегая к непосредственному делению «в столбик». Среди этих признаков практически наиболее удобны следующие (связанные с записью числа в десятичной системе):
- для делимости на 2 нужно, чтобы последняя цифра числа делилась на 2;
- для делимости на 3 нужно, чтобы сумма цифр числа делилась на 3;
- для делимости на 4 нужно, чтобы число, записанное двумя последними цифрами, делилось на 4;
- для делимости на 5 нужно, чтобы последняя цифра была 0 или 5;
- для делимости на 8 нужно, чтобы число, записанное тремя последними цифрами, делилось на 8;
- для делимости на 9 нужно, чтобы сумма цифр делилась на 9;
- для делимости на 10 нужно, чтобы последняя цифра была 0;
- для делимости на 11 нужно, чтобы разность между суммой цифр, стоящих начетных местах, и суммой цифр, стоящих на нечетных местах, делилась на 11.