Закрыть

Алгоритм Евклида

Автор: Васин Алексей
Опубликовано 08.02.2008 в 13:04
Раздел: Теория чисел
Теги:

Рассмотрим классический алгоритм Эвклида для нахождения общего наибольшего делителя двух целых чисел методом последовательного деления. Приэтом будем вести изложение так, чтобы одновременно установить существование числе, обладающего свойствами наибольшего общего делителя. Для этой цели рассмотрим следующие леммы.

Лемма 1. Если α есть делимое, β - делитель и τ - остаток, так что

α=βq+τ,

 то из делимости двух каких либо чисел α,β,τ на число δ вытекает делимость оставшегося третьего числа не то же число δ.

Доказательство очевидно.

Обозначая, вообще, через {a,b} совокупность всех общих делттелей чисел a и b, мы можем, таким образом, написать {α,β}={β,τ}={τ,α}.

Лемма 2. Если в условиях предудущей леммы числа α и β выражаются линейно с целыми коэффициентами через какие либо числа a и b, то в таком же виде можно представить и остаток τ.

Для доказательства достатьчно заменить в равенстве α-βq=τ числа α и β их линейными выражениями через a и b и сделать затем приведение подобных членов, выделяя коэффициенты a и b.

Приступим теперь к нахождению общего наибольшего делителя натуральных чисел a и b<a способом последовательного деления.

Разделив a и b и обозначая остаток через $b_1$, заключаем на основании леммы 1, что

$\{a,b\}=\{b,b_1\}$

Деля вновь $b$ на $b_1$ и обозначая остаток через $b_2$ найдем

$\{b,b_1\}=\{b_1,b_2\}$

Продолжая так далее и замечая, что

$b>b_1>b_2>b_3>...≥0$

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

Обозначая этот последний остаток через $b_{n+1}$, мы будем стало быть, иметь

$b_{n-1}=b_{n}q_{n}+b_{n+1}=b_{n}q_{n}$

и, значит,

$\{b_{n-1},b_{n}\}=\{b_{n},0\}.

Так как последняя совокупность есть не что иное, как совокупность всех делителей числе $b_n$, то из соотношений

$\{a,b\}=\{b,b_1\}=...=\{b_{n-1},b_n\}=\{b_n,0\}$.     (1)

вытекает, что совокупность всех общих делителей чисел a и b совпадает с совокупностью всех делителей числа $b_n$. Последний отличный от нуля остаток $b_n$ является, таким образом, наибольшим общим делителем чисел a и b

$b_n=(a,b)$

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

Кроме того, мы можем, очевидно, написать

$(a,b)=(b,b_1)=...=(b_{n-1},b_n)=b_n$.      (2)

Заметим, что доказательство следует вести, оперируя символом {a,b}, а не символом (a,b), так как иначе придется заново доказывать только что отмеченное основное свойство числа $b_n$ - делиться на всякий общий делитель чисел a и b.

Применяя последовательно лемму 2, убеждаемся, кроме то, что первый остаток $b_1$ линейно выражается через a и b, стало быть второй остаток $b_2$ линейно выражается через те же числа, стало быть, и третий и т.д., вплоть до n-го остатка $b_n$.

Комментарии (1)

  • Дмитрий 2010-11-18  [ ответить ]

    С точки зрения математики все верно, но вот с точки зрения понимания материала весьма сложно написано. Рекомендую обратить внимание на книгу Коутинхо про RSA, там этот алгоритм весьма шикарно объяснен и доказан!

Комментировать могут только зарегистрированные пользователи

Подразделы
Новые статьи
Aрхив статей