Алгоритъм за изчисляване на най-голям общ делител (ГРУ) е открит и гръцки математик алгоритъм, известен като "взаимно изваждане." Въпреки, че се споменава за този алгоритъм все още Аристотел, по-късно той стана известен като алгоритъм на Евклид. Какво е най-общ делител, неговите свойства и методи за изчисление са обсъдени в [1].
Спомнете си, че НОД на две числа може да бъде изчислен в съответствие със следната повторение:
С процедура език за изчисляване на ГРУ е:
Int GCD (междинно съединение А, междинно съединение б)
ако (б == 0) върне;
върне GCD (В,% б);
алгоритъм на Евклид може да бъде разширена, за да определите намирането на А и Б от цели числа х и у. че брадва + с = г. където г - най-големият общ делител на а и б.
След това стойностите на х и у. са разтвори на уравнение брадва + с = г. са отношенията
X = Y ', Y = Х' - Y '· (2)
След тук, означава цялата част на / б.
Доказателство. Като мод б = а - · б. на
г = X '· б + у' · (а - · б) = Y '· а + (х' - Y '·) · б = х + у · на · б,
където е посочено от х = Y ', Y = Х' - Y '·.
gcdext функция (Int а. Int б. Int * г. Int * х. Int * у), по-долу, от въвеждане на числа А и В е D = GCD (а. б) и такива х. Y че D = а · х + у б ·. За неизвестните х и у трябва да работи рекурсивно gcdext функция (б. Мод б. Г. X. Y) и преизчисляване на стойностите х и у на по-горе посочената формула. Рекурсията прекратява, когато б = 0. Ако б = 0 GCD (а. 0) = A и = на · 1 + 0 · 0, така се предположи, х = 1, у = 0.
невалидни gcdext (Int а, Int б, Int * г, Int * х, Int * у)
За да се извърши ръчно удължен Euclidean алгоритъм е удобно да се използва маса с четири колони (както е показано в примера по-долу), съответната стойност на. б. х. у. Процесът на изчисление е разделен на три етапа:
а) Първо се изчислява НОД (а. б), като се използват първите две колони на таблицата и отношението (1). Последният ред в колоната и ще бъде стойността на г = GCD (а. В).
б) Запишете стойностите 1 и 0, съответно в х и у колона на последния ред.
в) Ние постоянно запълване линия за колони х и у от дъното към върха. Стойностите на х и у в последния ред вече въведени в етап Ь). Ако приемем, че на текущия ред вече са напълнени стойности (X ', Y'), ние използваме формула (2) се преизчисляват и напиши стойности (х. Y) в съответната клетъчна линия стои горе.
1. Advanced Алгоритъм на Евклид. Намираме разтвор на 5х + 3Y = 1. Изчисляване на GCD (5, 3) и намирането на подходящ х. Y е произведен в таблицата по-долу:
Поръчка и посоката изчисления са отбелязани със стрелки и букви.
От таблицата ние откриваме, че GCD (5, 3) = 5 х (-1) + 3 · 2 = 1, т.е., х = 1, у = 2.
Да разгледаме например стойностите на (х. Y) за първия ред. От втория ред вземат стойности (х ', у') = (1, 1). Според формули (2), ние получаваме:
Y = X '- Y' · = 1 - (-1) + = 1 + 1 = 2
Сравнявайки нарича линейно уравнение на форма брадва = В (мод п). Той има решение, ако и само ако б е неделими от г = GCD (с. N). Ако D> 1, уравнението може да бъде опростена, като го заменя с "х = б" (мод п '), където А' = а / г. Ь '= б / г. п '= п / г. След това преобразуване на "и п" са взаимно-председателят.
Алгоритъм за решаване на уравнение "х = б" (мод п ') с относително прости за "и п" се състои от две части:
1. решаване на уравнението на "х = 1 (мод п '). За да направите това с помощта на удължен евклидовата алгоритъм търси решение (x0. Y0) уравнение на "х + N 'у = 1. Като модул енд миналата равенство ние получаваме" x0 = 1 (мод н ").
Пример. Решаване на уравнение 18x = 6 (мод 8).
Стойността на D = GCD (18, 8) = 2 делител 6, обаче има решение. След опростяване уравнение получаваме 9х = 3 (Mod 4). С Лема еквивалент 3 х = 1 (Mod 4). Решаването на уравнение 3x + 4Y = 1 при използване на разширен Euclidean алгоритъм, ние получаваме х = 1, у = 1. Когато х = -1 (Mod 4) = 3. Това означава, х = 3 ще бъде като разтвор на 3 х = 1 (Mod 4 ) и 18х = 6 (мод 8).
Наречен Diophantine уравнения на формата
В този раздел се разгледа алгоритъм за намиране на решения на линейно уравнение Diophantine с две неизвестни на форма А · х + б · Y = С (оттук нататък за простота, ние ще пропусне умножение признаци и напиши прото брадва + с = С).
ТЕОРЕМА 1. уравнение брадва + с = С има разтвор число, ако и само ако в се дели на GCD (а. В).
Теорема 2. Ако двойката (x0. Y0) е разтворът на уравнение брадва + с = с. целия набор от неговите разтвори (х г.), описани с формулата:
За частични решения уравнение брадва + с = с първо трябва да намери решение (х ', у') на уравнение ос + с = г (г - най-голям общ делител на а и б) (Х0 Y0.) Като се използва разширен Euclidean алгоритъм, при което това се умножава по C / D. това е
Пример. Виж разтвора определя от уравнението 5х + 3Y = 7.
1. уравнение има решение, тъй 7 е разделен на GCD (5, 3) = 1.
2. Виж разтвор на 5х '+ 3Y' = 1, като се използва разширен Euclidean алгоритъм: (х ', у') = (1, 2).
3. Намерете решението започне Diophantine уравнение (x0 y0.):
Според теорема 2, комплектът на разтвори изходни диофантово уравнение има формата:
Свързани статии