Признак делимости на 19: экзотика в теории чисел

Критерий, устанавливающий необходимое и достаточное условие делимости произвольного натурального числа N на данное натуральное число m, называется признаком делимости на m. Предполагается, что этот критерий применяется в форме некоторого алгоритма, не выполняя непосредственно деления данного числа N на m.

В школьном курсе математики выводятся и широко применяются некоторые признаки делимости: на 2, 3, 4, 5, 9, 10 и другие.

Признаки делимости на 2, 3, 5, 9 и 10 были известны с давних времён. Признак делимости на 2 (чётные и нечётные числа) знали древние египтяне за две тысячи лет до н. э. Признаки делимости на 2, 3 и 5 были обстоятельно изложены итальянским математиком Леонардо Фибоначчи (около 1170–1250).

Памятник Фибоначчи работы Джованни Пагануччи (1863) на кладбище Кампосанто, Пиза, Италия. Леонардо Пизанский (Фибоначчи) (1170–1240) — первый самостоятельный математик Западной Европы, который полностью осветил все достижения математиков стран ислама и продвинулся дальше них. Также он подробно изложил признаки делимости на 2, 3 и 5

Большой вклад в изучение признаков делимости чисел внёс Блез Паскаль (1623–1662). Он нашёл алгоритм для нахождения признаков делимости любого натурального числа на любое другое натуральное число, из которого следуют все частные признаки. Общий признак делимости Паскаля состоит в следующем: «Натуральное число N делится на натуральное число m тогда и только тогда, когда сумма произведений цифр числа N на соответствующие остатки, получаемые при делении разрядных единиц на число m, делится на m». Поэтому общая теория признаков делимости относится к теории сравнений (теории равноостаточности).

Блез Паскаль (1623–1662) — французский математик, механик, физик, литератор и философ. Один из основателей математического анализа, теории вероятностей и проективной геометрии, создатель первых образцов счётной техники, автор основного закона гидростатики. В том числе, занимался исследованием признаков делимости натуральных чисел

Особое значение имеют признаки делимости на простые числа. Не затрагивая общеизвестные, мы покажем некоторые экзотические признаки. В частности, признак делимости на 19:

Число делится без остатка на 19 тогда и только тогда, когда число его десятков, сложенное с удвоенным числом единиц, кратно 19.

Попробуйте доказать этот признак методами элементарной алгебры сначала самостоятельно* (чуть ниже он будет приведён).

Алгоритм применения этого признака можно отнести к рекуррентным методам (вычислений на основе значений предыдущих членов последовательности). Он заключается в том, что этот признак делимости применяется неоднократно. Через несколько шагов в результате получается достаточно малое число, к которому деление применяется явным образом.

Пример

Проверить, делится ли число 3086379 на 19?

308637 + 9 × 2 = 308655

30865 + 5 × 2 = 30875

3087 + 5 × 2 = 3097

309 + 7 × 2 = 323

32 + 3 × 2 = 38 (здесь уже можно остановиться)

3 + 8 × 2 = 19

19:19 = 1

Ответ: да, число 3086379 делится на 19.

Этот признак зависит от основания системы счисления, то есть в данном случае он сформулирован для 10-ричной системы. Аналогичные признаки существуют для делимости на 7, 13, 17 и 23.

Примечание

*Доказательство признака делимости на 19

Всякое число N можно представить в виде N = 10a + b, где a — число десятков, b — число единиц.

Нам нужно показать, что N кратно 19 тогда и только тогда, когда M = a + 2b кратно 19. Для этого умножим M на 10 и из этого произведения вычтем N, получим:

10M – N = 10(a + 2b) – (10a + b) = 19b. Отсюда видно, что N кратно 19 тогда и только тогда, когда M делится на 19.

#Лайфхаки #Признаки_делимости #Паскаль #простые_числа #делимость