정수론 #3-2 :: 선형 합동 방정식

Linear congruence equation

$\begin{gather*}a\equiv b\mod m \end{gather*}$

 

위를 만족하는 x를 구하기 위해선

 

$\begin{gather*}\Leftrightarrow ax-c=my \ \ \ \ for \ \ some \ \ y\in\mathbb{Z} \\ \Rightarrow ax-my=c \end{gather*}$

 

위의 선형 디오판토스 방정식을 풀면 된다.

음수의 최대공약수 찾기는 양수로 생각해도 된다. (-m ⇒ m)

 

$\begin{gather*}g:=\gcd(a,m) \end{gather*}$

 

1. g가 c를 나누지 않으면 해가 없다.
2. g가 c를 나눈다면 Special Solution(x0, y0)이 존재.

$\begin{gather*}ax-my=c \\ ax_0-my_0=c \\ \Rightarrow a(x-x_0)-m(y-y_0)=0 \\ \Rightarrow \frac{a}{g}(x-x_0)=\frac{m}{g}(y-y_0), \ \ \ \ \gcd(\frac{a}{g}, \frac{m}{g})=1 \end{gather*}$

 

사실)
a|bc이고 gcd(a,b)=1 이면 a|c이다.

증명)
a와 b를 각각 소인수 분해하면 gcd = 1이기 때문에 공통 인수가 없다.
그렇다면 결국 a의 인수는 전부 c에 들어있어야 한다. 따라서 a|c.

$\begin{gather*}\frac{a}{g}|\frac{m}{g}(y-y_0)\Rightarrow\frac{a}{g}|(y-y_0) \end{gather*}$

 

사실에 의하여 a/g는 m/g와 서로소이기 때문에 y-y0를 나눌 수 있다.

 

$\begin{gather*}y=y_0+\frac{a}{g}k, \ \ \ \ x=x_0+\frac{m}{g}k, \ \ \ \ (k\in\mathbb{Z}) \end{gather*}$

 

위에서 y는 필요없고 x만 필요하다.

 

$\begin{gather*}\therefore x=x_0+\frac{m}{g}k, \ \ \ \ (k\in\mathbb{Z}) \end{gather*}$

 

k에 0부터 g-1까지의 값을 넣으면 x와 합동인 값을 찾을 수 있다. 이때 k의 계수는 m의 약수로 나온다.

 

합동인 값P가 음수(P<0)인 경우엔 아래식을 통해 양수P’으로 변경해준다.

 

$\begin{gather*}m+P=P' \end{gather*}$

$\begin{gather*}\therefore x\equiv x_0,x_0+\frac{m}{g},x_0+\frac{2m}{g},...,x_0+\frac{(g-1)m}{g}\mod m \end{gather*}$

 

합동인 x값은 g개 존재한다. (k=0 ~ k=g-1)

만약 k ≥ g라면 이전에 나온 합동 x값들과 중복되게 된다. (x0 ≡ x0 + m mod m)

 

따라서 mod m관점에서는 답인 x값은 총 g개이다.

정수 전체에서의 답은 x의 식으로 만들 수 있는 무한개이다.

 

$\begin{gather*}\therefore x=x_0+\frac{m}{g}k, \ \ \ \ (k\in\mathbb{Z}) \end{gather*}$