https://www.youtube.com/watch?v=Whl9317jAOA&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=26

📌 유클리드 호제법

• 두 수의 최대 공약수를 구하는 알고리즘
• MOD 연산을 이해하고 있어야 함

◾ 유클리드 호제법의 핵심 이론

연산	기능	예제
MOD	두 값을 나눈 나머지 연산을 구하는 연산	10 MOD 4 = 2 → 10 % 4 = 2

◾ 유클리드 호제법의 원리

• 큰 수를 작은 수로 나누는 MOD 연산 수행
• 앞 단계에서의 작은 수와 MOD 연산 결과 값(나머지)로 MOD연산 수행
• 나머지가 0이 되는 순간 작은 수를 최대 공약수로 선택