## 유클리드 호제법
> **a를 b로 나눈 나머지가 r일 때,**
> **a, b의 최대공약수는 b와 r의 최대공약수와 같다.**
두 양의 정수의 최대 공약수를 구하는 알고리즘
두 양의 정수 a, b에 대하여 (a > b)
a = bq + r (0 <= r < b) 이라 하면,
a, b의 최대 공약수는 b, r의 최대 공약수와 같다. 즉,
`gcd(a, b) = gcd(b, r)`
r = 0이라면 a, b의 최대 공약수는 b가 된다.
## 활용
두 양의 정수의 최대 공약수를 구할 때
큰 수를 작은 수로 나눈 나머지를 구한 뒤,
작은 수와 나머지를 새로운 싸으로 해서 같은 일을 반복한다.
나머지가 0이 되는 순간의 작은 수가 두 수의 최대공약수가 된다.
## 코드
```javascript
function Euclidean (a, b) {
if (b === 0) {
return a;
}
return Euclidean(b, a % b);
}
```
> [!NOTE]- 노트 (+증명)
> ![[f7b4bbf1-e52e-47a9-a571-019c53fde257.png]]