정수론 #2 :: 선형 디오판토스 방정식

Diophantine Equations

정수 계수 방정식 ⇒ 정수해 구하기

 

용어 정리

• m|n : m이 n을 나눈다. m divides n, or n is divided by m.
• gcd(a, b) : greatest common divisor (최대 공약수)
• prime : 1과 자기 자신으로만 나눠지는 수

 

---

 

유클리드 알고리즘 - 최대 공약수 구하는 방법

소인수분해는 너무 오래걸림!

 

$\begin{gather*}a = bq +r \end{gather*}$

 

• q = a를 b로 나눴을 때 몫
• r = a를 b로 나눴을 때 나머지 (0 ≤ r ≤ b)

 

---

 

ex) gcd(432, 132) 구하기

$\begin{gather*}432 = 132*3 + 36 \\ 132 = 36*3 + 24 \\ 36 = 24*1 + 12 \\ 24 = 12*2 \end{gather*}$

 

나머지가 사라질 때 까지 반복 한다.

그러면 마지막 나머지 = 최대 공약수

 

$\begin{gather*}\gcd(432, 132)=12 \end{gather*}$

 

---

 

증명(보완 필요)

$\begin{gather*}d|a, \ \ \ \ d|b \\ \Rightarrow d|(ax+by) \end{gather*}$

 

위는 사실이다. d가 정수 a와 b를 나눌 수 있다면 그것의 일차결합 역시 나눌 수 있다.

 

$\begin{gather*}d|a, \ \ \ \ d|b \\ d=\gcd(a, b) \end{gather*}$

 

위를 증명하고 싶다면 d’ < d 라고 했을 때

 

$\begin{gather*}d'|a, \ \ \ \ d'|b \\ \Rightarrow d'|d \end{gather*}$

 

임을 보이면 된다.

이때 유클리 알고리즘 예시에서 위를 만족하는 d’은 12이다.

그리고 이 12는 24, 36을 모두 나눌 수 있다.

 

---

확장된 유클리드 알고리즘

유클리드 알고리즘

$\begin{gather*}432 = 132*3 + 36 \\ 132 = 36*3 + 24 \\ 36 = 24*1 + 12 \\ \end{gather*}$

 

---

 

확장된 유클리드 알고리즘 - 역연산 : d = ax + by의 형태로.

팁 : 위 알고리즘에서 나머지 부분만 계속 큰 값으로 바꿔주면 된다.

⇒ 위의 식에서 나머지 12, 24, 36 만 남기고 넘긴 식을 대입해주자.

 

$\begin{gather*}12 = 36-24*1 \\ =36-(132-36*3) \\ =4*(432-132*3)-132\\ =4*432-13*132 \end{gather*}$

$\begin{gather*}\therefore 12=4*432-13*132 \end{gather*}$

 

d = ax + by의 일차결합 꼴로 나온다.

 

$\begin{gather*}\gcd(a,b)=ax+by, \ \ \ \ a,b\in\mathbb{Z} \end{gather*}$

 

일차결합으로 얻을 수 있는 가장 작은 양수 = gcd(a, b)

 

---

선형 디오판토스 방정식 풀이법

$\begin{gather*}ax+by=c \end{gather*}$

 

1. 정수 해의 조건

해가 있다면 gcd(a, b)|c 가 가능해야 한다.

gcd(a, b)|(ax + by)가 가능하기 때문이다.

 

gcd(a, b)|c 이기만 하면 해가 있다.

ax + by 일차결합으로 얻을 수 있는 가장 작은 양수가 gcd(a,b)이기 때문이다.

즉, c = k * gcd(a,b)

 

---

 

2. 정수 해 구하기

1. 유클리드 알고리즘으로 gcd를 구한다.

2. c가 gcd로 나눠지면 해가 존재한다.

3. 유클리드 알고리즘을 거꾸로 돌려서 일차결합 형태로 만든다.

 

$\begin{gather*}\gcd(a,b)=ax+by, \ \ \ \ a,b\in\mathbb{Z} \end{gather*}$

 

4. 이때의 x, y가 정수해중 하나이다. ⇒ 특수해

 

---

Prime Divisor Property

prime p에 대하여

 

$\begin{gather*}p|ab \Rightarrow p|a, \ \ or \ \ p|b \end{gather*}$

 

증명

만약 p|a인 경우는 p|ab ⇒ p|a 이므로 자명하다.

만약 p|a가 아닌 경우엔 p|b여야 하므로 이것은 증명이 필요하다. 이때 아래와 같이 쓸 수 있다.

 

$\begin{gather*}\gcd(a,p)=1 \end{gather*}$

 

유클리드 알고리즘에 의하여

 

$\begin{gather*}\gcd(a,p)=ax+py=1 \\ \Rightarrow bax+bpy=b \end{gather*}$

 

이때 왼쪽변은 p로 나눌 수 있다. p|ab가 가능하고 p|bp도 가능하기 때문이다.

따라서 오른쪽 변의 b도 p로 나눌 수 있다. (왼쪽이 정수이면 오른쪽도 정수)

즉, p|a가 아닌 경우엔 p|b이다. 

 

$\begin{gather*}\therefore p|ab \Rightarrow p|a, \ \ or \ \ p|b \end{gather*}$

 

---

특수해 (Particular Solution)

유클리드 알고리즘 역연산으로 구한 해.

 

일반해 (General Solution)

• 요약 : 원래식에서 유클리드 알고리즘 역연산 식을 빼고 정리한다.

$\begin{gather*}ax+by=c \end{gather*}$

$\begin{gather*}d:=\gcd(a,b)|c \\ \Rightarrow ax_0+by_0=d \end{gather*}$

 

d가 a와 b의 최대 공약수이고, c를 나눌 수 있어서 해가 존재한다면

유클리드 알고리즘에 의해서 ax+by=d의 특수해(x0, y0)을 구할 수 있다.

 

$\begin{gather*}c=kd \\ a(kx_0)+b(ky_0)=kd=c \end{gather*}$

 

c = kd라고 한다면 특수해 식을 원래식의 형태로 고칠 수 있다.

 

$\begin{gather*}x_1=kx_0, \ \ \ \ y_1=ky_0 \end{gather*}$

 

위는 원래 방정식 ax + by = c의 특수해(x1, y1)이다.

 

$\begin{gather*}ax+by=c \\ -(ax_1 + by_1=c) \\ \Rightarrow a(x-x_1)+b(y-y_1)=0 \end{gather*}$

 

원래 방정식과 특수해를 넣은 방정식을 뺀다.

 

$\begin{gather*}a(x-x_1)=-b(y-y_1) \\ \Rightarrow \frac{a}{d}(x-x_1)=-\frac{b}{d}(y-y_1) \end{gather*}$

 

정리를 하되, d로 나눠준다. d는 a와 b의 최대 공약수이므로 a/d와 b/d는 서로소 관계이다.

정수해를 만들어야 하므로 계수를 나눠줘야 한다.

그러나 서로소 관계이기에 (a/d)|(b/d)는 불가능하다. 따라서 a/d는 y-y1을 나눠야 한다.

 

$\begin{gather*}y-y_1=t\frac{a}{d}, \ \ \ \ (t\in\mathbb{Z}) \end{gather*}$

 

나눌 수 있으므로 위와 같이 쓸 수 있고, 정리를 하면

 

$\begin{gather*}x=-t\frac{b}{d}+x_1, \ \ \ \ y=t\frac{a}{d}+y_1, \ \ \ \ (t\in\mathbb{Z}) \end{gather*}$

 

라는 일반해를 구할 수있다.