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

Метод выведения наибольшего значения называемого общим делителем, для 2 целых чисел и большей величины для 2 отрезков - называется алгоритм Евклида. В первом случае, который является самым простым, он обращен к двум положительным целым числам и создает две новые величины. Состоящие из наименьшего числа и разницы относительно наибольшего. До тех пор пока цифры не приравниваются.

Для нахождения большего общего делителя, на два целые положительные числа, мы:

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

Запишем алгоритм Евклида в цепочку, в которой обозначения а и b будут исходными числами, r₁,r₂, ...., r_n положительными остатками, получившиеся от деления с ними, g₁, g₂, ....., g_n+1 неполными частными от них.
a = bg₁ + r₁
b = r₁g₂+r₂
__________
r_n-2 = r_n-1g_n +r_n

Дано : а = 777, b = 629.
Значит: 777 = 629 * 1 +148, 629 = 148 * 4 + 37, 148 = 37 *4
Ответ: Нулевым остатком для двух чисел 777 и 629 является 37.

В поиске большей величины для двух отрезков действуем так же. Но деление с остатками меняют на геометрический аналог, то есть заменяем остатки на меньший остаток. Получаем: наименьшим отрезком отмеряем расстояние на наибольшем возможное количество раз. Остаток от наибольшего отрезка является остатком деления. отмеряем на наименьшем отрезке так же доходим до нулевого остатка.
Когда отрезки a и b являются соизмеримыми, тогда общей большей мерой в отрезках будет нулевой остаток. Но когда они не соизмеримы нулевые остатки будут бесконечны.

Рассмотрим для наглядности:

Дано: Начальные отрезки, сторона AB и AC треугольника ABC. В нем углы A = C = 72 градуса, а угол В = 36 градусам.
Значит: отрезок AD будет первым остатком (биссектрисой от С - будет СD), из чего можно сделать вывод, что по очередность бесконечна, следовательно, и отрезки AB и АС будут несоизмеримыми.

Позже методом подсчетов с помощью алгоритма Евклида пользовались и для других объектов в алгебре. Вообще данный алгоритм имеет большое применение. Так как его равенство делает возможным записать общий больший делитель d от a и b, как d=ax=by . Где х и у являются целыми числами. Что дает нам решать диофантовые уравнения имеющие первую степень и две неизвестные. Кстати и электро - вычислительные машины так же пользуются данным алгоритмом.

Заметка: Сколько тайн и загадок находится в космосе. Очень много интересного Вы сможете прочитать про Черную материю (http://rebiznes.ru/space/76575645.html) перейдя по ссылке.