Linear equation theorem

 

정리1

$a, b \in \mathbb{Z} \setminus \left\{\mathbf{0} \right\}$, Let $g=gcd(a,b)$.

Then there exist $x, y \in \mathbb{Z}$ s.t. $ax+by=g$

 

이는 유클리디안 알고리즘을 사용하여 한 해를 찾을 수 있다.

Euclidean algorithm

 

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

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

$\vdots$

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

$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$    $\Rightarrow$    $gcd(a,b)=r_{n+1}$

---

위의 유클리디안 알고리즘으로 밑에 식을 만들 수 있고 이를 이용해 첫번째 식에 그 다음식들을 차례로 대입해나가면 결국 $r_{n+1}$은 $a, b$의 식으로서 표현된다.

$ r_{n+1} = r_{n-1} - r_{n}q_{n+1}$

$r_{n} = r_{n-2} - r_{n-1}q_{n}$

$r_{n-1} = r_{n-3} - r_{n-2}q_{n-1}$

$\vdots$

$r_{2} = b - r_{1}q_{2}$

$r_{1} = a - bq_{1}$

 

 

 

따름정리

1. Let $m=ax+by$ for some $x,y \in \mathbb{Z}$. Then $gcd(a,b)|m$

2. For $n \in \mathbb{Z}$, there are exist $x', y' \in \mathbb{Z}$ s.t. $ax'+by' = ng$.

3. $gcd(a,b)=1$

$\Rightarrow$ $ax+by=1$ for some $x,y \in \mathbb{Z}$.

 

 

 

How to find all solutions $(x, y)$ for $ax+by = g \;\;  (g =gcd(a,b))$?

 

Case 1 : $g =1$

위의 정리1에 의해 $\exists x_{0}, y_{0} \in \mathbb{Z}$ s.t. $ax_{0} + by_{0} = 1$

 

C1 - Suppose 1 : $ax + by = 1$ for some $x,y \in \mathbb{Z}$

$\left\{\begin{matrix}
ax_{0} + by_{0} = 1 \\
ax + by = 1\end{matrix}\right.$

위 연립방정식을 $x,y$에 대하여 풀면

$x = x_{0} + b(xy_{0} - x_{0}y)$, $y = y_{0} - a(xy_{0} - x_{0}y)$

 

이때 $xy_{0} - x_{0}y = k \in \mathbb{Z}$라 하자. 즉,

$x = x_{0} + bk$, $y = y_{0} - ak$ for some $k \in \mathbb{Z}$ 형태를 띤다.

 

C1 - Suppose 2 : For $k \in \mathbb{Z}$, $x = x_{0} + bk$, $y = y_{0} - ak$ 

then $ax + by = a(x_{0}+bk) + b(y_{0}-ak) = ax_{0} + by_{0} = 1$

 

C1 - Conclusion

Let $ax_{0} + by_{0} = 1$.

$ax + by = 1$ $\Leftrightarrow$ $(x, y) = (x_{0}+bk, y_{0}-ak)$ for some $k \in \mathbb{Z}$

 

Case 2 : general case

$g|a, \; g|b$이므로 $ax+by = g$는 다음과 같이 바꿀 수 있다.

$$(\frac{a}{g})x + (\frac{b}{g})y = 1$$

이때 $\frac{a}{g}, \frac{b}{g} \in \mathbb{Z}$ and $gcd(\frac{a}{g}, \frac{b}{g}) = 1$

 

따라서 Case 1을 적용할 수 있다. 즉,

$\exists x_{0}, y_{0} \in \mathbb{Z}$   s.t.   $\frac{a}{g}x_{0} + \frac{b}{g}y_{0} = 1$

$ax + by = g$  $\Leftrightarrow$  $(x, y) = (x_{0}+\frac{b}{g}k, y_{0}-\frac{a}{g}k)$ for some $k \in \mathbb{Z}$