"최대공약수"의 두 판 사이의 차이

1,713 바이트 제거됨 ,  3년 전
편집 요약 없음
잔글
[[수론]]에서, [[정수]]들의 '''공약수'''(公約數, {{llang|en|common divisor}})는 동시에 그들 모두의 [[약수]]인 정수다. 적어도 하나가 0이 아닌 정수들의 '''최대공약수'''(最大公約數, {{문화어|련속나눔셈}}; {{llang|en|greatest common divisor}}, 약자 GCD)는 공약수 가운데 가장 큰 하나다. [[다항식]]이나 [[환 (수학)|환]]의 원소에 대해서도 정의할 수 있다.
 
== 정의 ==
두 [[정수]] <math>n,m\in\mathbb Z</math>의 '''공약수'''는 <math>n</math>의 약수이자 <math>m</math>의 약수인 정수이다. 모두 0이지는 않은 두 정수 <math>n,m\in\mathbb Z</math>의 '''최대공약수'''는 다음과 같은 여러 정의가 있으며, 이들은 서로 [[동치]]이다.
* <math>n</math>, <math>m</math>의 가장 큰 공약수
* <math>n</math>, <math>m</math>의 공약수이자, <math>n</math>, <math>m</math>의 모든 공약수의 [[배수]]인 양의 정수
* <math>n</math>, <math>m</math>의 정수 계수 선형 결합인 최소 양의 정수
모두 0이지는 않은 두 정수의 최대공약수는 항상 존재하며, 항상 유일하다. 기호는 <math>\gcd\{n,m\}</math> 또는 <math>(n,m)</math>.
 
비슷하게, 여러 정수 <math>n_1,n_2,\dots,n_k\in\mathbb Z</math>의 '''공약수'''는 공통 약수이며, 모두 0이지는 않은 여러 정수 <math>n_1,n_2,\dots,n_k\in\mathbb Z</math>의 '''최대공약수''' <math>\gcd\{n_1,n_2,\dots,n_k\}</math>는 다음과 같은 서로 [[동치]]인 정의가 있다. 이는 항상 유일하게 존재한다.
* 가장 큰 공약수
* 공약수이자, 모든 공약수의 배수인 양의 정수
* 정수 계수 선형 결합인 최소 양의 정수
* (재귀적 정의) <math>\gcd\{\gcd\{\gcd\{\cdots\gcd\{\gcd\{n_1,n_2\},n_3\}\cdots\},n_{k-1}\}n_k\}</math>
 
익명 사용자