Дискретно-непрерывная математика (стр. 19 )

Теорема 21. Представим произвольное нату­ральное число А в виде atk + b, где 0 ≤ b < tk, и положим

Чтобы для данной функции f алгоритм построе­ния последовательности (4) по правилу (5) был признаком равноостаточности при делении на т, не­обходимо и достаточно, чтобы было tk т.

Доказательство.

Необходимость. Если описанный алгоритм является признаком равноостаточности при де­лении на т, то числа А и b при делении на т должны быть равноостаточными. В частности, это будет так, если А= tk + b. Но это значит, что А — b = tk т.

Достаточность. В наших обозначениях А — b = atk, т. е. числа А и b равноостаточны при делении на т. Если tkт, то по следствию теоремы 17 они равноостаточны и при делении на т. Поэтому конструируемая алгоритмом в этом случае последо­вательность А0, А1, ... состоит из равноостаточных при делении на т чисел. Следовательно, процесс по­строения этой последовательности является призна­ком равноостаточности при делении на т.

13. В качестве второго примера рассмотрим при­знак равноостаточности при делении на 3 в десятич­ной системе счисления.

Запись натурального числа А в десятичной си­стеме счисления имеет вид

где

Положим

Теорема 22. Представим произвольное натуральное число А в виде

где

и положим

Тогда для того чтобы, порождаемый функцией f алгоритм построения последовательности (4) по правилу (5) был признаком равноостаточности при делении на т, необходимо и достаточно, чтобы было (tk—1) m.

Доказательство.

Необходимость. Если описанный алго­ритм действительно является признаком равнооста­точности при делении на т, то он, в частности, должен быть применим и к числу А = tk +а0. Здесь

f(A) =а0+1, и равноостаточность чисел А и f(A) при делении на т означает (tk—1) т.

Достаточность. Пусть А ≥tk. Тогда из оп­ределения функции f следует, что

Здесь каждое слагаемое (см., например, задачу 22, п. д)) делится на tk— 1. Значит, если (tk— 1) т, то и (А — f(A)) m. Равноостаточность остальных чле­нов последовательности (4), а также ее членов, если она начинается с числа А < tk, вытекает из ее построения.

Теорема 23. Пусть А — натуральное число, пред­ставленное в виде

где

Положим

Тогда для того чтобы порождаемый функцией f ал­горитм построения последовательности (4) по правилу (5) был признаком равноостаточности при де­лении на т, необходимо и достаточно, чтобы было (tk+1) m.

Доказательство.

Необходимость. В случае A = tk+a0 равноостаточность чисел А и f(A)= a0 —1 при деле­нии на т дает нам (tk + 1) т.

Достаточность. Мы имеем в нашем случае при А ≥tk

(*)

(знак «плюс» стоит здесь в члене, соответствующем нечетному коэффициенту при k в показателе, а знай «минус» — в члене, соответствующем четному коэффициенту). Согласно пп. д) и е) задачи 22 при нечет­ном r выражение ikr + 1 делится на tk+1, а при чет­ном r выражение tkr—1 делится на tk+1. Значит, если (tk+1) m, то на т делится каждый член в (*) справа, а потому и вся разность А — f(A), Тем самым числа А и f(A) оказываются равноостаточными при делении на т. Равноостаточность ос­тальных членов последовательности (4), а также членов этой последовательности, если она начинается с числа А<tk, вытекает непосредственно из ее по­строения.

14. Во многих задачах несущественна не только величина неполного частного от деления одного числа на другое, но также и величина остатка от деления, а интересно только, обращается этот остаток в нуль или нет, т. е. делится или нет первое число на второе. После сказанного в п. 1 ясно, как подходить к зада­чам такого рода.

Назовем числа а и b равноделимыми при делении на т, если либо и а и b делятся на т, либо на т ни а, ни b не делятся.

15. Пусть нужно выяснить делимость на т числа А. Будем строить последовательность убывающих на­туральных чисел

А = А0, А1, А2, ..., (6)

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

Всякий способ построения последовательности (6) назовем признаком делимости на т.

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

Нетрудно проверить (это предоставляется чита­телю), что при помощи всякой функции f(x), удов­летворяющей условиям а)—в) из п. 10 и условию

г*) если f(x) имеет смысл, то числа х и f(x) равноделимы на т,

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

Найдем несколько признаков делимости.

Согласно теореме 16 достаточно уметь определять делимость чисел на числа вида рα (степени простого числа).

16. Признак делимости на 7 в десятич­ной системе счисления. Пусть А — натуральное число. Представим А в виде 10a+b, где 0 ≤b < 10, как это уже делалось раньше. Положим

Функция f3(А) дает нам известный признак дели­мости на 7: число 10a+b (0 ≤b < 10) делится на 7 тогда и только тогда, когда на 7 делится число а — 2b; полученное число снова проверяется этим же способом на делимость на 7 и т. д.

17. Признак делимости на 13. Представим натуральное число А в виде 10a+b и положим

18. Признаки делимости того же типа имеются и для чисел, записанных в других, недесятичных си­стемах счисления.

Признак делимости на 11 в шестеричной системе счисления. Представим натуральное число А в виде 6a+b, где 0≤b<6 (в соответствии со сказанным выше все рассуждения ведутся с употреблением обо­значений и названий чисел в десятичной системе счисления), и положим

19. В предыдущих пунктах этого параграфа мы познакомились с большим количеством самых разно­образных признаков равноостаточности и признаков делимости. Практической целью построения всех этих признаков является получение удобно работающих алгоритмов нахождения остатков при делении на не­которые определенные числа (признаки равнооста­точности) или алгоритмов, обнаруживающих, равны эти остатки нулю или нет (признаки делимости). На­сколько же мы осуществили поставленную цель?

Некоторые признаки равноостаточности, такие, как при делении на 2, 3, 5, 10 в десятичной системе счисления (и вообще — на делитель степени основа­ния системы счисления) действительно оказались весьма практичными и удобными. Применение других признаков связано с более или менее громоздкими вычислениями.

Естественно поэтому искать и применять такие признаки делимости и равноостаточности, использо­вание которых приводит к цели по возможности бо­лее простым путем.

Одна из трудностей, с которой мы сталкиваемся при такого рода попытках, состоит в том, что мы должны уметь простоту (или, наоборот, сложность) применения того или иного признака оценивать неко­торым числом. В качестве такой числовой характе­ристики можно, например, взять число арифметиче­ских действий над однозначными числами, которые необходимо произвести в процессе применения дан­ного признака к тому или иному числу.