유클리디안 알고리즘(Euclidean algorithm)

 

정리1

Let $a, b, q, r \in \mathbb{Z}$

If $a = bq+r$, then $gcd(a,b) = gcd(b, r)$

 

  Let $ d= gcd(a,b)$,  $d' = gcd(b,r)$

  $d|a$ and $d|b$ 

  $\Rightarrow$ $d|a-bq$

  $\Rightarrow$ $d|r$

  So $d|b$ and $d|r$ $\Rightarrow$ $d \leq d'$

 

  $d'|b$ and $d'|r$ 

  $\Rightarrow$ $d'|bq+r$ 

  $\Rightarrow$ $d'|a$

  So $d'|b$ and $d'|a$ $\Rightarrow$ $d' \leq d$

  $\therefore$  $d=d'$

 

 

 

<Eclidean algorithm : finding  $gcd(a,b)$>

Let $a, b \in \mathbb{N}$ and $a>b$

$a = bq_{1} + r_{1}$        $0 \leq r_{1} < b$

$b = r_{1}q_{2} + r_{2}$        $0 \leq r_{2} < r_{1}$

$r_{1} = r_{2}q_{3} + r_{3}$        $0 \leq r_{3} < r_{2}$

$\vdots$

$r_{n-1} = r_{n}q_{n+1} + r_{n+1}$        $0 \leq r_{n+1} < r_{n}$

$r_{n} = r_{n+1}q_{n+2} + 0$                                         

$(b = r_{0} > r_{1} > r_{2} > \cdots > r_{n+1} > r_{n+2} = 0)$

 

$\Rightarrow$ $gcd(a,b) = gcd(b,r_{1}) = gcd(r_{1}, r_{2}) = \cdots = gcd(r_{n}, r_{n+1}) = r_{n+1}$