Exponenta Banner

gcd

Наибольший общий делитель

Свернуть все на странице

Синтаксис

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. Коэффициенты Безута полезны для решения диофантовых уравнений. Этот синтаксис поддерживает двойные, одинарные и знаковые целочисленные входы.

Примеры

свернуть все

Открыть Live Script
A = [-5 17; 10 0];
B = [-15 3; 100 0];
G = gcd(A,B)
G = 2×2

     5     1
    10     0

gcd возвращает положительные значения, даже когда входы отрицательные.

Открыть Live Script
A = uint16([255 511 15]);
B = uint16([15 127 1023]);
G = gcd(A,B)
G = 1x3 uint16 row vector

   15    1    3
Открыть Live Script

Решить диофантово уравнение, 30x+56y=8 для x и y.

Найдите наибольший общий делитель и пару коэффициентов Безута для 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 и y что решает проблему. 

x = u*4
x = -52

y = v*4
y = 28

Входные параметры

свернуть все

Входные значения, заданные как скаляры, векторы или массивы вещественных целочисленных значений. A и B могут быть любым числовым типом, и они могут быть разных типов в пределах определенных ограничений:

  • Если A или B имеет тип singleдругой может иметь тип single или double.

  • Если A или B принадлежит целочисленному классу, тогда другой должен принадлежать тому же классу или должен быть double скалярное значение.

A и B должен быть того же размера, или должен быть скаляром.

Пример: [20 -3 13],[10 6 7]

Пример: int16([100 -30 200]),int16([20 15 9])

Пример: int16([100 -30 200]),20

Типы данных: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64

Выходные аргументы

свернуть все

Наибольший общий делитель, возвращенный как массив действительных неотрицательных целочисленных значений. G - тот же размер, что и A и B, и значения в G всегда действительны и неотрицательны. G возвращается так же, как и A и B. Если A и B имеют различные типы, тогда G возвращается как тип nondouble.

Коэффициенты Безута, возвращенные как массивы действительных целочисленных значений, которые удовлетворяют уравнению, A.*U + B.*V = G. Тип данных U и V - тот же тип, что и у A и B. Если A и B имеют различные типы, тогда U и V возвращаются как типы nondouble.

Алгоритмы

g = gcd(A,B) вычисляется с помощью алгоритма Евклида. [1]

[g,u,v] = gcd(A,B) вычисляется с помощью расширенного алгоритма Евклида. [1]

Ссылки

[1] Knuth, D. «Algorithms A and X». Искусство компьютерного программирования, том 2, раздел 4.5.2. Reading, MA: Addison-Wesley, 1973.

Расширенные возможности

Генерация кода C/C + +
Сгенерируйте код C и C++ с помощью Coder™ MATLAB ®

.

См. также

Представлено до R2006a

Документация MATLAB

Поддержка