확장 유클리드 알고리즘(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} ..

​중국인의 나머지 정리(CRT; Chinese Remainder Theorem)연립 합동식의 유일한 해를 찾는 정리이다. 예를 들면서 설명과 함께 전개하는 게 가장 이해하기 쉽다. 개념 이해를 위해 연립 합동식이 2개일 때만 생각해보자.$$ \begin{cases} x \equiv 3 ~ (mod~ 5)~\dashrightarrow~ (a) \\ x \equiv 4~ (mod~ 7)~\dashrightarrow ~(b) \end{cases} $$위 두 합동식 (a), (b)를 모두 만족하는 어떤 정수 \(x\)는 어떻게 찾을 수 있을까?어떤 수 \(x\)는 위 두 합동식을 모두 만족하기 위해 (a), (b)의 해를 각각 \(A_1\), \(A_2\)라고 하면 아래의 형태가 된다.$$ x \equiv A_..