Энциклопедия Брокгауза и Ефрона - деление

1) Деление есть действие, обратное умножению; в нем по заданному произведению двух чисел и одному из двух множителей ищется второй множитель. Заданные произведение и множитель называются соответственно делимым и делителем, а искомый множитель — частным. В частности Д. целого числа на целое определяется, сколько раз меньшее число заключается в большем; в этом случае является еще один элемент Д. — остаток; далее, под Д. полинома А степени m на полином В степени n (n < m) разумеется определение полиномов: частного — Q и остатка — R, степеней n — m^ой и r < m, удовлетворяющих условию:

А = BQ + R.

2) Правила Д. чисел и полиномов излагаются в руководствах; указания относительно приемов, употреблявшихся при Д. в древние и средние века, можно найти, между прочим, у Кантора в "Vorlesungen über Geschichte der Mathematik" (Лпц., 1880—92). Из правил приближенного Д. заслуживают внимания так назыв. сокращенное Д. и Д. Фурье, назван. им division ordonnée ("Analyse des équations déterminées", 1831). В сокращенном Д. при составлении произведений найденных цифр частного на делителя число знаков последнего постепенно уменьшается на одну цифру; при этом поступают, как в следующем примере:

24680135 | 7531121

— 22593368 | 3,277086

"2086772

— 1506224

"580548

— 527178

"53370

— 52718

""652

— 602

50

— 45

5

По правилу Фурье прежде всего в делителе отделяют слева один или несколько знаков (по усмотрению), которые и принимаются за действительный делитель. Затем Д. на этот последний делитель (сокращенный) производится по общим правилам, но после сноса цифры делимого к полученному частному остатку всякий раз вводится поправка, которая вычисляется следующим образом: найденные цифры частного подписываются в обратном порядке под цифрами делителя, следующими за теми цифрами, на которые действительно производится Д.; стоящие одна под другой цифры перемножаются, а сумма полученных произведений и составляет число, которое нужно вычесть из соответствующего частного делителя; так, если полный делитель равен 4156, а деление производится на 4 и если в частном найдены цифры 231, то поправка равна

1...5...6

1...3...2

1+15+12 = 28

Пример:В первоначально избранном делителе можно впоследствии, если остатки будут слишком малы, увеличить число цифр; в таком случае к исправленному остатку надо снести соответственные цифры делимого и опять ввести поправку, отвечающую новому делителю, а затем продолжать деление в том же порядке. Доказательство способа Фурье основывается на рассмотрении разрядов единиц, входящих в поправку.

3) Делителем целого числа А наз. целое число, на которое А делится без остатка.

Если В — делитель А, то все делители В будут делителями А, если же В есть число простое, то оно наз. простым делителем числа А. Для определения простых делителей А, вообще говоря, необходимо испытать, делится ли число А на простые числа, меньшие √a.

Пусть р1, p2... рm — простые делители А и пусть А других простых делителей не имеет; в таком случае А может быть представлено в виде

А = p1^l1 p2^l2 ... pm^lm,

(l1, l2,... lm — целые числа); такое представление возможно только одним образом.

Самое общее выражение для какого-нибудь делителя А будет

p1^k1 p2^k2... pm^km

где k1 < l1, k2 < l2,... km < lm.

Все делители числа А найдутся из произведения

(1 + p1 + p1² +... +p1^l1)(1 + p2 +p2² +... + p2^l2)...... (1 + pm + pm² +... + pm^lm)

и будут отдельными членами этого произведения.

Число N всех делителей числа А будет, следовательно, равно

N = (l1 + 1) (l2 + 1)... (lm + 1)

а сумма их S = самому произведению или (по формуле Безу)

S = [(p1^l1+1 — 1)/p1 — 1][(p2^l2+1 — 1)/p2 — 1]... [ (pm^lm+1 — 1)/pm — 1]

Так, для числа 831600 = 2⁴.3³.5².7.11 число делителей N = 5.4.3.2.2 = 240, а сумма делителей S = 3690240.

4) Иногда возможно определить некоторых делителей числа А, не зная простых его делителей и не производя отдельных испытаний, по известным признакам делимости: так, напр., можно доказать, что на 2 делятся числа, последняя цифра которых — четная; на 3 — сумма цифр которых делится на 3; на 4 — две последних цифры которых делятся на 4; на 5 — последняя цифра которых 0 или 5; на 7 — если по разделении числа на грани, начиная справа, по три цифры в грани разность суммы четных и нечетных граней делится на 7; на 8 — если три последних знака делятся на 8; на 9 — если сумма цифр делится на 9; на 11 — если разность суммы цифр четного порядка и суммы цифр нечетного порядка, считая справа или слева, делится на 11; на 13 — если составленная указанным для 7 разность делится на 13 и т. д.

Доказательство приведенных признаков делимости на 3, 9, 7, 11 и 13 получаются из рассмотрении степеней 10, дающих при делении на эти числа остаток + 1.

С помощью указанных признаков можно прямо установить признаки делимости для произведений двух, трех и т. д. из приведенного выше взаимно простых чисел: напр., можно, не производя деления, доказать, что число 2646072 разделится на 10296=8.9.11.13; в самом деле: 72 делится на 8; 2+7+6+4+6+2=27 делится на 9, (2+0+4+2)—(7+6+6)=—11 делится на 11; (72+2)—(646)=—572 делится на 13; по указанным признакам отсюда следует, что самое число разделится на 8, 9, 11 и 13 и на их произведение.

Кроме того, имеется несколько отдельных теорем о делимости чисел; напр., если p число простое и а не делится на р, то всегда а^р-1—1 разделится на p (теорема Fermat'a); далее, если p число простое, то 1.2.3.... (p—1)+1 всегда разделится на p (теорема Wilson'a), и т. д.

5) Общим делителем двух или нескольких чисел наз. число, на которое все данные числа делятся без остатка; самый большой из сих делителей назыв. общим наибольшим делителем. Если для чисел А и В известны все их простые делители, то, очевидно, возможно немедленно найти и их общий наибольший делитель. Но общий наибольший дел. можно найти с помощью конечного числа действий и не зная делителей чисел А и В. Доказательство положения дано еще Эвклидом ("Начала", кн. 8, предл. 2), которому и принадлежит так наз. способ последовательного Д. для нахождения общего наибольшего Д. Если δ есть общий наибольший делитель чисел А и В, то всегда могут быть найдены два целых числа (^>