[친절한 수론 길라잡이] 6장. 선형방정식과 최대공약수

두 개의 정수 a, b가 주어졌을 때, a의 배수와 b의 배수로 만들 수 있는 수를 모두 찾아보자.

다시말해, ax + by에서 x와 y에 대입해 만들 수 있는 수를 찾아보자.

 

a=42, b = 30으로 해보자.

	x = -3	x = -2	x = -1	x = 0	x = 1	x = 2	x = 3
y = -3	-216	-174	-132	-90	-48	-6	36
y = -2	-186	-144	-102	-60	-18	24	66
y = -1	-156	-114	-72	-30	12	54	96
0	-126	-84	-42	0	42	84	126
y = 1	-96	-54	-12	30	72	114	156
y = 2	-66	-24	18	60	102	144	186
y = 3	-36	6	48	90	132	174	216

 

 

표의 수들이 모두 6으로 나누어짐을 확인할 수 있다.

43와 30이 모두 6으로 나누어지기 떄문에, 모두 6의 배수인 것은 놀랍지 않다.

 

일반적으로, 임의의 a, b가 gcd(a, b)에 의해 나누어지므로, ax + by로 표현되는 수 역시 gcd(a, b)로 나누어지는 것은 명확하다.

심지어, gcd(42, 30)인 6은 표에서 찾을 수 있다!

 

ax + by로 표현되는 가장 작은 양의 정수는 gcd(a, b)이다.

 

그럼, ax + by = gcd(a, b)의 정수해는 어떻게 구할 수 있을까?

간단한 수라면, 대입 후 암산을 해볼 수 있겠지만, 조금만 커져도 부담스러워진다.

 

22x + 60y = gcd(22, 60)이라고 해보자.

우선, gcd를 구한다. 유클리드 호제법에 의해

60 = 2 * 22 + 16

22 = 1 * 16 + 6

16 = 2 * 6 + 4

6 = 1 * 4 + 2

4 = 2 * 2 + 0

gcd(22, 60) = 2이다.

 

이 계산 과정에 등장하는 몫과 나머지를 이용하여 방정식 22x + 60y = 2를 풀어보자.

16 = 60 - 2 * 22 = a - 2b (여기서 a가 60, b가 22이다.)

이 결과를 두 번째 식에 나오는 16에 대입한다.

b = 1 * 16 + 6 = 1 * (a-2b) + 6

이 결과를 세 번째 식 16 = 2 * 67 + 4의 6과 16에 대입하면

a-2b = 16 = 2 * 6 + 4 = 2(-a + 3b) + 4

이다.

다시 한번, 나머지 4에 대해 식을 전개하면

4 = (a-2b) -2(-a + 3b) = 3a - 8b

이다.

마지막 식 6 = 1 * 4 + 2에 위 결과를 대입하여

 

-a+3b = 6 = 1 * 4 + 2 = 1 * (3a - 8b) + 2를 얻는다.

이를 정리하면,

-4a + 11b = 2

 

실제로, a=60, b = 22를 대입하면 맞는 걸 확인할 수 있다!

 

a = q_1b + r_1	r_1 = a = q_1b
b = q_2r_1 + r2	r_2 = b - q_2r_1       = b - q_2(a - q_1b)       = -q_2a + (1q_1q_2)b
...	...

한줄 한줄 내려갈 때, 다음과 같은 형태로 변환될 수 있다.

  다음 식의 나머지 = a의 배수 + b의 배수

 

마침내 0이 아닌 마지막 나머지에 이르게 되면, gcd(a, b) = ax + by의 정수해를 얻는다.

 

서로소인 두 수 a = 12453, b = 2347에 대한 계산을 보자.

x, y = (304, -1613)이 방정식 12453x + 2347y = 1의 해임을 알 수 있다.

 

ax + by = gcd(a, b)가 언제나 해를 가짐을 알았다.

 

---

이제, 얼마나 많은 해를 가질 수 있는지, 모든 해를 어떻게 표현하는지 알아보자.

 a와 b가 서로소인 경우부터 확인하자.

 

ax + by = 1에서 (x1, y1)이 해라고 가정하자.

 

그러면 x1에 b의 배수를 더하고, y1에 a의 같은 배수를 뺴서 새로운 해를 찾을 수 있다.

다시말해, 임의의 정수 k에 대해 (x1 + kb, y1 - ka)가 주어진 방정식의 새로운 해가 된다.

 

여전히 gcd(a, b) = 1조건 아래에서, 위와 같은 과정을 통해 모든 가능한 해를 구할 수 있음을 증명하려 한다.

(x1, y1)과 (x2, y2)가 서로 다른 해라고 가정하자.

 

 

첫 번째 식에 y2를 곱하고, 두 번째 식에는 y1을 곱한 뒤, 이 두 식의 차를 구해보자.

 

비슷하게, 첫 번째 식에 x2를 곱하고, 두 번째 식에는 x1을 곱한 뒤, 두 식의 차를 구해보자.

 

 

이제 k = x2y1 - x1y2라 하면, 다음 결과를 얻는다:

 

즉, 두 번째 해는 첫 번째 해에서 x1에 b의 배수를 더하고, y1에 a의 배수를 빼서 얻을 수 있다.

 

따라서 방정식 ax + by = 1의 모든 정수해는 처음 방정식의 해 (x1, y1)부터 시작하여 식

(x_1 + kb, y_1 - ka)에 적당한 정수 k를 대입하여 얻을 수 있다.

 

gcd > 1인 경우에는?

ax + by = g. 양변을 나누면 (a/g)x + (b/g)y = 1이 된다.

앞에서 ax + by = 1인 꼴은 증명되었으므로, 적어도 하나의 정수해를 갖는다.

 

이 방정식의 모든 정수해는

에서 k를 대입하여 찾을 수 있다.

 

 

선형방정식 정리
a와 b가 0이 아닌 정수이고, g = gcd(a, b)라고 하자.
선형방정식 ax + by = g는 항상 정수해 (x1, y1)을 가지며, 이는 유클리드 호제법으로 구할 수 있다.
주어진 방정식의 모든 정수해는 다음 공식에 정수값 K를 대입하여 찾을 수 있다.

 

이 방정식 ax + by = 1은 소인수분해 이론, 암호 등에서도 자주 쓰인다.