Страница:VeberVellshtejn t1 1906ru.djvu/62

Изъ сказаннаго попутно вытекаетъ слѣдующiй выводъ.

Каждый общiй дѣлитель двухъ чиселъ есть также дѣлитель общаго наибольшаго дѣлителя ихъ. Это слѣдуетъ непосредственно изъ соотношенiя β).

Приведемъ еще слѣдующiй примѣръ для выясненiя этого алгориѳма.

${\begin{aligned}6552&=14.448+280,\\448&=1.280+168,\\280&=1.168+112,\\168&=1.112+56,\\112&=2.56.\\\end{aligned}}$

Итакъ, $56$ есть общiй наибольшiй дѣлитель чиселъ $6552$ и $448$.

3. Вмѣсто равенства

$a=qb+r$

можно при разысканiи общаго наибольшаго дѣлителя пользоваться также равенствомъ

$a=(q+1)b-(b-r)$;

что представляетъ собой преимущество въ томъ случаѣ, если $b-r$ меньше, нежели $r$, т. е. если $2r$ больше, нежели $b$. Въ этомъ случаѣ, отрицательное число $-(b-r)$ называютъ абсолютно наименьшимъ остаткомъ отъ дѣленiя числа $a$ на число $b$. Пользуясь въ алгориѳмѣ общаго наибольшаго дѣлителя абсолютно наименьшими остатками, мы скорѣе придемъ къ цѣли.

Въ нашемъ примѣре вычисленiе можно было бы вести такъ:

${\begin{aligned}6552&=15.448-168\\448&=3.168-56\\168&=3.56,\\\end{aligned}}$

что даетъ значительное сокращенiе.

4. Точно такъ же, какъ и для двухъ чиселъ, можно поставить вопросъ о разысканiи общаго наибольшаго дѣлителя для нѣсколькихъ чиселъ, т. е. самаго большого числа, которое дѣлитъ всѣ данныя числа. Но эту задачу можно привести къ предыдущей, основываясь на слѣдующемъ замѣчанiи:

(третье отъ конца) обнаруживаетъ, что $a_{n-3}$ дѣлится на $a_{n}$. Восходя такимъ образомъ къ первымъ равенствамъ въ ряду (1), мы получимъ, что числа $a$ и $a_{1}$ дѣлятся на $a_{n}$.

β) Пусть $b$ будетъ общiй дѣлитель чиселъ $a$ и $a_{1}$. Если мы представимъ первое изъ равенствъ (1) въ видѣ

$a_{2}=a-qa_{1}$,

то, въ силу предложенiя § 14, 8, оно обнаруживаетъ, что $a_{2}$, дѣлится на $b$. Пользуясь этимъ, мы такимъ же образомъ при помощи второго изъ равенствъ (1) покажемъ, что $a_{3}$ дѣлится на $a_{n}$. Продолжая тотъ-же рядъ разсужденiй, мы докажемъ при помощи предпослѣдняго равенства (1), что число $a_{n}$ дѣлится на $b$.

Тот же текст в современной орфографии

Из сказанного попутно вытекает следующий вывод.

Каждый общий делитель двух чисел есть также делитель общего наибольшего делителя их. Это следует непосредственно из соотношения β).

Приведём ещё следующий пример для выяснения этого алгоритма.

${\begin{aligned}6552&=14.448+280,\\448&=1.280+168,\\280&=1.168+112,\\168&=1.112+56,\\112&=2.56.\\\end{aligned}}$

Итак, $56$ есть общий наибольший делитель чисел $6552$ и $448$.

3. Вместо равенства

$a=qb+r$

можно при разыскании общего наибольшего делителя пользоваться также равенством

$a=(q+1)b-(b-r)$;

что представляет собой преимущество в том случае, если $b-r$ меньше, нежели $r$, т. е. если $2r$ больше, нежели $b$. В этом случае, отрицательное число $-(b-r)$ называют абсолютно наименьшим остатком от деления числа $a$ на число $b$. Пользуясь в алгоритме общего наибольшего делителя абсолютно наименьшими остатками, мы скорее придём к цели.

В нашем примере вычисление можно было бы вести так:

${\begin{aligned}6552&=15.448-168\\448&=3.168-56\\168&=3.56,\\\end{aligned}}$

что даёт значительное сокращение.

4. Точно так же, как и для двух чисел, можно поставить вопрос о разыскании общего наибольшего делителя для нескольких чисел, т. е. самого большого числа, которое делит все данные числа. Но эту задачу можно привести к предыдущей, основываясь на следующем замечании:

(третье от конца) обнаруживает, что $a_{n-3}$ делится на $a_{n}$. Восходя таким образом к первым равенствам в ряду (1), мы получим, что числа $a$ и $a_{1}$ делятся на $a_{n}$.

β) Пусть $b$ будет общий делитель чисел $a$ и $a_{1}$. Если мы представим первое из равенств (1) в виде

$a_{2}=a-qa_{1}$,

то, в силу предложения § 14, 8, оно обнаруживает, что $a_{2}$, делится на $b$. Пользуясь этим, мы таким же образом при помощи второго из равенств (1) покажем, что $a_{3}$ делится на $a_{n}$. Продолжая тот же ряд рассуждений, мы докажем при помощи предпоследнего равенства (1), что число $a_{n}$ делится на $b$.