나머지 계산을 확장하기
보통의 유클리드 호제법은 나눗셈의 나머지를 반복하여 최대공약수를 구한다. 확장 방법은 각 나머지가 처음 두 수의 어떤 정수 계수 합인지를 함께 추적한다. 최대공약수에서 멈추지 않고 표현식의 계수까지 얻는다는 점이 다르다.
직접 계산한 예
61=2×26+9, 26=2×9+8, 9=1×8+1이므로 최대공약수는 1이다. 나머지 1에서 거꾸로 대입하면 1=9−8=3×9−26=3×61−7×26이 된다. 따라서 계수 한 쌍은 3과 −7이다.
계수도 같은 연산으로 갱신
나머지를 r이전−q×r현재로 계산할 때 두 수의 계수에도 같은 빼기 연산을 적용한다. 처음의 a와 b는 각각 1a+0b와 0a+1b로 시작한다. 이 관계를 유지하면 마지막 0이 아닌 나머지의 계수가 베주 표현을 준다.
역원으로 사용하기
앞의 결과 3×61−7×26=1에서 3×61≡1 (mod 26)이다. 따라서 법 26에서 61의 역원은 3이다. 최대공약수가 1이 아니라면 같은 결과에서 곧바로 곱이 1인 역원을 얻을 수는 없다.