확장 유클리드 알고리즘(Extended Euclidian Algorithm)은 유클리드 호제법을 확장한 것이다. $as + bt = gcd(a,b)$을 만족하는 정수 $s$, $t$ 짝을 찾아낼 수 있다. 증명은 생략하고 어떻게 사용하는가를 적어볼까 한다. 초기 조건 $s_0 = 1, s_1 = 0, ~~t_0 = 0, t_1 = 1, ~~r_0 = a, r_1 = b$ 진행 $$ \begin{align} q_i \leftarrow & \lfloor~r_{i-1}~/~r_i~\rfloor & (i \ge 1)\\ r_i \leftarrow & ~r_{i-2} - r_{i-1} \cdot q_{i-1} & (i \ge 2)\\ s_i \leftarrow & ~s_{i-2} - s_{i-1} ..