Алгоритм Евклида<div class=\"info_element\">\r\n<div
class=\"info_header\">Утверждение</div>\r\n<div class=\"info_content\">\r\n<p
class=\"MsoNormal\">Для любых двух натуральных чисел $a
&gt; b$ верно следующее равенство: $\\mbox{НОД} (a; b) =
\\mbox{НОД} (a - b; b)$.</p>\r\n<div class=\"toggle_element\">\r\n<h3 class=\"toggle_header\">ДОКАЗАТЕЛЬСТВО</h3>\r\n<div
class=\"toggle_content\">\r\n<p>$n=\\mbox{НОД} (a; b)$ -- наибольший
среди всех общих делителей чисел $a$ и $b$, тогда
$a\\;\\vdots\\;n$ и $b\\;\\vdots\\;n$. Отсюда $a-b\\;\\vdots\\; n$, значит,
 $n$ -- делитель $a-b$ и $b$, он не превосходит наибольшего
из всех общих делителей чисел $a-b$ и $b$, т.е. $n\\leqslant
m=\\textrm{НОД}(a; b)$. Аналогично, рассуждая получаем,
 что $a-b\\;\\vdots\\; m$ и $b\\;\\vdots\\; m=\\textrm{НОД}(a; b)$. Отсюда
$a=(a-b)+b \\;\\vdots\\;&nbsp;m$, значит, $m$ -- делитель $a$ и $b$,
 он не превосходит наибольшего и всех общих делителей
чисел $a$ и $b$, т.е. $m\\leqslant n=\\textrm{НОД}(a; b)$. Таким образом
получаем $m\\leqslant n\\leqslant m$, т.е. $\\mbox{НОД} (a; b) =n=m=
\\mbox{НОД} (a - b; b)$. Утверждение доказано.</p>\r\n</div>\r\n<div
class=\"toggle_line\">\r\n<div class=\"toggle_arrow\">&nbsp;</div>\r\n</div>\r\n</div>\r\n</div>\r\n</div>\r\n<p
class=\"MsoNormal\">Теперь перейдем к описанию&nbsp;<em>алгоритма
Евклида</em>&nbsp;для нахождения наибольшего общего
делителя двух чисел.</p>\r\n<p class=\"MsoNormal\">Пусть $a\\geqslant&nbsp;b$,
 тогда мы можем поделить $a$ на $b$ cостатком $a=kb+r_1$,
 где $0\\leqslant r_1\\leqslant&nbsp;b-1$. Тогда, пользуясь утверждением,
 мы получаем: $$\\textrm{НОД}(a; b)=\\textrm{НОД}(a-b; b)=\\textrm{НОД}(a-2b;b)=\\dots=\\textrm{НОД}(a-kb;
b)=\\textrm{НОД}(r_1; b)$$ Если оказалось, что $r_1=0$, то $\\textrm{НОД}(a;b)=\\textrm{НОД}(0;
b)=b$. Если же $r_1&gt;0$, тогда мы вновь делим $b$ c остатком
на $r_1$: $b=k_1r_1+r_2$, где $0\\leqslant&nbsp;r_2\\leqslant&nbsp;r_1-1$. Тогда
вновь мы получаем, что $$\\textrm{НОД}(r_1; b)=\\textrm{НОД}(r_1;
b-k_1r_1)=\\textrm{НОД}(r_1;&nbsp;r_2).$$ Если $r_2=0$, то $$\\textrm{НОД}(a;
b)=\\textrm{НОД}(r_1; b)= \\textrm{НОД}(r_1; r_2)= \\textrm{НОД}(r_1; 0)=r_1.$$
Если же $r_2\\ne0$, то мы продолжаем действовать аналогично.
В итоге однажды мы получим $0$ в качестве одного
из остатков, т.к. остатки постоянно уменьшаются,
 а уменьшаться бесконечно они не могут (это целые
неотрицательные числа).</p>\r\n<p class=\"MsoNormal\">Обычно
поиск НОД с помощью алгоритма Евклида&nbsp;схематично&nbsp;записывают
следующим образом:</p>\r\n<table style=\"width: 638px; height: 224px;\"
border=\"0\">\r\n<tbody>\r\n<tr>\r\n<td>$a=kb+r_1$, где $0&lt;r_1\\leqslant b-1$</td>\r\n<td>$\\textrm{НОД}(a;
b)=\\textrm{НОД}(b; r_1)$</td>\r\n</tr>\r\n<tr>\r\n<td>&nbsp;$b=k_1r_1+r_2$, где
$0&lt;r_2\\leqslant r_1-1$</td>\r\n<td>&nbsp;$\\textrm{НОД}(r_1; b)=\\textrm{НОД}(r_1;
r_2)$</td>\r\n</tr>\r\n<tr>\r\n<td>&nbsp;&nbsp;$r_1=k_2r_2+r_3$, где $0&lt;r_3\\leqslant
r_2-1$</td>\r\n<td>&nbsp;$\\textrm{НОД}(r_1; r_2)=\\textrm{НОД}(r_2; r_3)$&nbsp;</td>\r\n</tr>\r\n<tr>\r\n<td
style=\"text-align: center;\">&nbsp;$\\dots$</td>\r\n<td style=\"text-align: center;\">$\\dots$&nbsp;</td>\r\n</tr>\r\n<tr>\r\n<td>&nbsp;$r_{n-1}=k_nr_n+r_{n+1}$,
 где $0&lt;r_{n+1}\\leqslant r_n-1$</td>\r\n<td>&nbsp;$\\textrm{НОД}(r_{n-1};
r_{n})=\\textrm{НОД}(r_{n}; r_{n+1})$&nbsp;</td>\r\n</tr>\r\n<tr>\r\n<td>$r_{n}=k_{n+1}r_{n+1}$&nbsp;</td>\r\n<td>$\\textrm{НОД}(r_{n};
r_{n+1})=\\textrm{НОД} (r_{n+1},0)=r_{n+1}$&nbsp;</td>\r\n</tr>\r\n</tbody>\r\n</table>\r\n<p
class=\"MsoNormal\">С помощью алгоритма Евклида можно
доказать следующую теорему.</p>\r\n<div class=\"info_element\">\r\n<div
class=\"info_header\">Теорема</div>\r\n<div class=\"info_content\">\r\n<p>Для
любых натуральных $a$ и $b$ найдутся такие целые
$x$ и $y$, что $$xa+yb=\\textrm{НОД}(a; b).$$</p>\r\n<div class=\"toggle_element\">\r\n<h3
class=\"toggle_header\">ПЛАН ДОКАЗАТЕЛЬСТВА</h3>\r\n<div class=\"toggle_content\">\r\n<p>Доказательство
данного утверждения основано на таблице, написанной
выше для алгоритма Евклида. Оно будет проходить
по индукции, но мы не будем формально доказывать
это утверждение.</p>\r\n<p>Вначале заметим, что для
$\\textrm{НОД} (r_{n-1}, r_n)=r_{n+1}=r_{n-1}-k_nr_n=x_{n-1}r_{n-1}+y_{n-1}r_n.$
Здесь $x_{n-1}$ и $y_{n-1}$ -- целые числа. Далее мы подставляем
в это выражение запись для $r_{n}$ через&nbsp;&nbsp;$r_{n-2}$
и&nbsp;$r_{n-1}$ (в таблице эта запись не приведена,
но можно догадаться, что она должна быть именно
такой): $r_n=r_{n-2}-k_{n-1}r_{n-1}.$ Тогда мы несложно получаем,
&nbsp;что $$\\textrm{НОД}(r_{n-2}, r_{n-1})=\\textrm{НОД} (r_{n-1}, r_n)=r_{n+1}=$$$$=x_{n-1}r_{n-1}+y_{n-1}r_n=x_{n-1}r_{n-1}+k_n(r_{n-2}-k_{n-1}r_{n-1})=$$$$=k_nr_{n-2}+
(x_{n-1}-k_nk_{n-1})r_{n-1}=x_{n-2}r_{n-2}+y_{n-2}r_{n-1}.$$ Здесь $x_{n-2}$
и $y_{n-2}$ -- некоторые целые числа.</p>\r\n<p>Далее мы
продолжаем в том же самом русле (именно здесь
мы опускаем индукционное рассуждение): подставляем
запись для $r_{n-1}$ через $r_{n-3}$ и $r_{n-2}$, получаем
целые числа $x_{n-3}$ и $y_{n-3}$, потом подставляем запись
для $r_{n-2}$ через $r_{n-4}$ и&nbsp;$r_{n-3}$ и т.д., в конце подставить
запись $r_1$ через $a$ и $b$ и получаем нужные нам целые
$x$ и $y$.</p>\r\n</div>\r\n<div class=\"toggle_line\">\r\n<div class=\"toggle_arrow\">&nbsp;</div>\r\n</div>\r\n</div>\r\n</div>\r\n</div><br><div
class=\"info_element\" style=\"text-align: left;\">\r\n<div class=\"info_header\">\r\n<div
class=\"info_element\" style=\"text-align: left;\">\r\n<div class=\"info_header\">Утверждение</div>\r\n<div
class=\"info_content\">\r\n<p>Для любых двух натуральных чисел
$a &gt; b$ верно с ледующее равенство: $\\mbox{НОД} (a;
b) = \\mbox{НОД} (a - b; b)$.</p>\r\n</div>\r\n</div>\r\n<p style=\"text-align:
left;\">На этом утверждении основан простой способ
отыскания наибольшего общего делителя двух чисел.
Он называется алгоритм Евклида и заключается
в следующем. Для нахождения наибольшего общего
делителя двух чисел нужно заменить большее из
чисел на остаток от деления его на меньшее и для
полученной пары повторять эту процедуру, пока
одно из чисел не станет равно нулю. Тогда второе число будет
равно наибольшему общему делителю исходных чисел.&nbsp;</p>\r\n<p
style=\"text-align: left;\">Например, $\\mbox{НОД} (175; 90) = \\mbox{НОД}
(85; 90) = \\mbox{НОД} (85; 5) = \\mbox{НОД} (0; 5) = 5$.</p>\r\n</div>\r\n</div>