확장된 유클리드 알고리즘이란? '확장된' 이라는 말이 붙었습니다. 그렇다면 유클리드 알고리즘이란 무엇일까요? 많은 분들이 알고 계신 것처럼, 유클리드 알고리즘은 최대공약수 (GCD) 를 구할 때 사용합니다. 만약 375와 275의 최대공약수를 구하고 싶다면 아래와 같이 유클리드 알고리즘을 적용할 것입니다. GCD(375, 275) → 25 여기에 덧붙여, 확장된 유클리드 알고리즘은 두 개의 숫자 375, 275에 대해서, 각각에 어떤 값을 곱하고 더해야 최대공약수인 25가 되는지도 알려줍니다. 즉, 아래와 같이 알려준다는 것입니다. xGCD(375, 275) → GCD = 25, S = 3, T = -4 여기에서 구해진 S와 T의 값을 이용하면, 375 * (3) + 275 * (-4) = 25 가 됨을..