최대공약수 편집하기

{{진지}}
{{착한문서}}
{{괜찮은데?}}
{{논문}}

* 상위 문서: [[약수와 배수]]

==개요==
공약수 중 가장 큰 수.

정수 a, b, c, d에 대하여 c|a, c|b 인 ∀c 중 최대인 수를 d라 할 때, d를 a, b의 최대공약수라고 한다.

최대공약수는 다음과 같이 나타낼 수 있다.

<pre>gcd(a,b) 또는 (a,b)</pre>

정수론에서 이거 모르면 벌레 취급받는다.

여담으로, 두 수의 곱은 그 두 수의 최대공약수와 [[최소공배수]]의 곱과 같다.

두 수 a b의 선형결합으로 나타낸 양수 중 가장 작은거로도 정의된다

==구하는 방법==

존나 많다.

===유클리드 호제법===

이게 은근히 유명한 방법인데, 두 수를 ㄴ자로 나타내어진 공간에 놓고 작은 수에서 최대 배수로 큰 수를 빼 가는 방법이다.

이렇게 하면 되게 쉽다. 정수론에서는 꼭 써먹어야 하는 것.

===소인수분해===
이건 소인수분해만 하면 쉬운데, 소인수분해가 존나 힘든 경우도 있다.

===초딩새끼들 방법===
{{극혐}}
{{귀차니즘}}

좆같은 방법이다. 그냥 하나하나 나눈다. 장인정신이 돋보이는데, 이렇게 할 바에는 차라리 [[요들송]] 가사를 정확히 적겠다.

===니 머리===

암산하는 방법. 의외로 쉽다.

==관련 문서==
* [[최소공배수]]

* [[소인수분해]]

* [[정수론]]