Общие принципы построения

Понятия делимости, равноделимости и равноостаточности

Если для двух целых чисел a и b существует такое целое число q, что

то говорят, что число a делится на b.

Два целых числа a и b называются равноделимыми на m, если либо они оба делятся на m, либо оба не делятся.

Два целых числа a и b равноостаточны при делении на натуральное число m (или сравнимы по модулю m), если при делении на m они дают одинаковые остатки, то есть существует такие целые числа что

Общие принципы построения

Пусть требуется определить делится ли некоторое натуральное число A на другое натуральное число m. Для этого будем строить последовательность натуральных чисел:

такую, что:

1.

2. каждый член последовательности вполне определяется предыдущим;

3.

4. последний член последовательности меньше m, то есть

5. все члены последовательности являются равноделимыми на m.

Тогда если последний член этой последовательности равен нулю, то A делится на m, в противном случае A на m не делится.

Способ (алгоритм) построения такой последовательности и будет искомым признаком делимости на m. Математически он может быть описан с помощью функции определяющей каждый следующий член последовательности в зависимости от предыдущего:

удовлетворяющей следующим условиям:

1. при значение не определено;

2. при значение есть натуральное число;

3. если то

4. если то и x равноделимы на m.

Если требование равноделимости для всех членов последовательности заменить на более строгое требование равноостаточности, то последний член этой последовательности будет являться остатком от деления A на m, а способ (алгоритм) построения такой последовательности будет признаком равноостаточности на m. В силу того, что из равенства остатка при делении на m нулю следует делимость на m, любой признак равноостаточности может применяться как признак делимости. Математически признак равноостаточности тоже может быть описан с помощью функции определяющей каждый следующий член последовательности в зависимости от предыдущего:

удовлетворяющей следующим условиям:

1. при значение не определено;

2. при значение есть натуральное число;

3. если то

4. если то и x равноостаточны при делении на m.

Примером такой функции, определяющей признак равноостаточности (и, соответственно, признак делимости), может быть функция

а последовательность, построенная с её помощью будет иметь вид:

По сути применение признака равноостаточности на базе этой функции эквивалентно делению при помощи вычитания.

Другим примером может служить общеизвестный признак делимости (а также равноостаточности) на 10.

Если последняя цифра в десятичной записи числа равна нулю, то это число делится на 10; кроме того, последняя цифра будет являться отстатком от деления исходного числа на 10.

Математически этот признак равноостаточности может быть сформулирован следующим образом. Пусть надо выяснить остаток от деления на 10 натурального числа A, представленного в виде

Тогда остатком от деления A на 10 будет a. Функция, описывающая это признак равноостаточности будет выглядеть как

Легко доказать, что эта функция удовлетворяет всем перечисленным выше требованиям. Причём последовательность, построенная с её помощью, будет содержать всего один или два члена.

Также легко видеть, что такой признак ориентирован именно на десятичное представление числа A — так, например, если применять его на компьютере, использующем двоичную запись числа, то чтобы выяснить a, программе пришлось бы сначала поделить A на 10.

Поиск по сайту: