gcd

최대공약수(Greatest Common Divisor)

구문

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)는 다음을 충족하는 베주 계수(Bézout Coefficient) U와 V를 반환합니다. A.*U + B.*V = G. 베주 계수(Bézout Coefficient)는 디오판투스 방정식(Diophantine Equation)을 푸는 데 유용합니다. 이 구문은 double형, single형 및 부호 있는 정수 입력값을 지원합니다.

예제

double형 값의 최대공약수

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

디오판투스 방정식(Diophantine Equation)의 해

$$x$$와 $$y$$에 대한 디오판투스 방정식 $$30x+56y=8$$을 풉니다.

30과 56의 최대공약수와 베주 계수(Bézout Coefficient) 쌍을 구합니다.

[g,u,v] = gcd(30,56)

g = 
2

u = 
-13

v = 
7

u와 v는 베주의 항등식(Bézout's Identity) (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는 숫자 형식일 수 있으며, 특정 제한 사항 내에서 서로 다른 유형이 될 수 있습니다.

• 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 — 최대공약수(Greatest Common Divisor)

음이 아닌 실수형 정수 값

최대공약수로, 음수가 아닌 실수형 정수 값으로 구성된 배열로 반환됩니다. G는 A 및 B와 크기가 같으며, G의 값은 항상 음이 아닌 실수입니다. G는 A 및 B와 동일한 유형으로 반환됩니다. A와 B의 데이터형이 다르면 G는 비double형으로 반환됩니다.

U,V — 베주 계수(Bézout Coefficient)

실수형 정수 값

베주 계수(Bézout Coefficient)로, 방정식 A.*U + B.*V = G를 충족하는 실수형 정수 값으로 구성된 배열로 반환됩니다. U와 V의 데이터형은 A와 B의 데이터형과 동일합니다. A와 B가 다른 유형인 경우 U와 V는 비double형으로 반환됩니다.

알고리즘

g = gcd(A,B)는 유클리드 알고리즘을 사용하여 계산됩니다.[1]

[g,u,v] = gcd(A,B)는 확장된 유클리드 알고리즘을 사용하여 계산됩니다.[1]

참고 문헌

[1] Knuth, D. “Algorithms A and X.” The Art of Computer Programming, Vol. 2, Section 4.5.2. Reading, MA: Addison-Wesley, 1973.

확장 기능

C/C++ 코드 생성
MATLAB® Coder™를 사용하여 C 코드나 C++ 코드를 생성할 수 있습니다.

스레드 기반 환경

MATLAB®의 backgroundPool을 사용해 백그라운드에서 코드를 실행하거나 Parallel Computing Toolbox™의 ThreadPool을 사용해 코드 실행 속도를 높일 수 있습니다.

이 함수는 스레드 기반 환경을 완전히 지원합니다. 자세한 내용은 스레드 기반 환경에서 MATLAB 함수 실행하기 항목을 참조하십시오.

버전 내역

R2006a 이전에 개발됨

참고 항목

lcm