📚 목차

요약

1. 확장 유클리드 호제법의 핵심 이론

1. 확장 유클리드 호제법

• 확장 유클리드 호제법에서는 두 수의 최대 공약수를 구하는 것이 목적이 아닌, 방정식의 해를 구하는 것이다.
• $ax +by = c$ 에서 c는 a와 b의 최대 공약수의 배수라는 것을 이용한다.
  • 자세한 수학 공식은 생략함

2. 확장 유클리드 호제법 예시

$5x + 9y = 2$의 해 찾기

1. GCD(5, 9) 구하기

1. x = 이전 y, y = 이전 x - (이전 y * 몫) 으로 두어서 역순 계산하기

• 초기의 x, y 값은 1, 0으로 지정한다.