алгоритъм на Евклид
алгоритъм на Евклид - метод за намиране на най-голям общ делител на две цели числа и две полиноми в една променлива. Au първоначално е описано в "елементи" Евклид геометрична форма, като начин за намиране на обща мярка два сегмента. Au за намиране на най-голям общ делител в пръстена от цели числа, и полином пръстен на една променлива е специален случай на обща Euclidean алгоритъм пръстени.
Au за числа е както следва. Да, и. Споделяме с остатъка по - получаваме частичния частното, а останалата част, така че. След това разделете на - вземете частичен коефициент, а останалата част. Сега разделете нататък и така се получи следната верига от равенства ..:
в която определен брой стъпки, получени от друг остатък на нула, тъй като последователността на остатъците е намаляваща последователност от числа:
и, следователно, трябва краен брой стъпки, за да сложи край на нула. След това, най-голям общ делител на цифрите и равна на последната ненулева остатъка в Схема следващ участък (*).
Пример. Намерете най-голям общ делител на 1981 г. и 378 прави поредица разделение:
Последно, различна от 0 остатък 7 е най-големият общ делител на 1981 г. и 378.
Au за намиране на най-голям общ делител на две полиноми и също така се състои от последователно разделяне с остатък, след първия остатък, и след това на втория остатък и така нататък. г.
Тъй като степента на останалата част е естественото намаляване на номера, а след това след краен брой стъпки, които пристигат на останалата част от нула. Последният ненулева остатъка и е най-общ делител на и.
Свързани статии