Наибольший общий делитель
G = gcd(A,B)[G,U,V] = gcd(A,B)G = gcd(A,B) A и B. Элементы в G являются всегда неотрицательными, и gcd(0,0) возвращает 0. Этот синтаксис поддерживает входные параметры любого числового типа.
[G,U,V] = gcd(A,B) U и V, которые удовлетворяют: A.*U + B.*V = G. Коэффициенты Bézout полезны для решения диофантовых уравнений. Этот синтаксис поддерживает двойные, единственные входные параметры, и целого числа со знаком.
A = [-5 17; 10 0]; B = [-15 3; 100 0]; G = gcd(A,B)
G = 2×2
5 1
10 0
gcd возвращает положительные значения, даже когда входные параметры отрицательны.
A = uint16([255 511 15]); B = uint16([15 127 1023]); G = gcd(A,B)
G = 1x3 uint16 row vector
15 1 3
Решите диофантовое уравнение,
для
и
.
Найдите наибольший общий делитель и пару коэффициентов Bézout для 30 и 56.
[g,u,v] = gcd(30,56)
g = 2
u = -13
v = 7
u и v удовлетворяют идентичность Безута, (30*u) + (56*v) = g.
Перепишите идентичность Безута так, чтобы она больше походила на исходное уравнение. Сделайте это путем умножения 4. Используйте ==, чтобы проверить, что обе стороны уравнения равны.
(30*u*4) + (56*v*4) == g*4
ans = logical
1
Вычислите значения
и
которые решают проблему.
x = u*4
x = -52
y = v*4
y = 28
g = gcd(A,B) вычисляется с помощью Алгоритма Евклида. [1]
[g,u,v] = gcd(A,B) вычисляется с помощью расширенного Алгоритма Евклида. [1]
[1] Knuth, D. “Алгоритмы A и X.” Искусство программирования, издания 2, разделяют 4.5.2. Чтение, MA: Аддисон-Уэсли, 1973.