정수론 6장 - 선형방정식과 최대공약수를 파헤쳐보자!

이상준 교수님의 강의영상을 참고하였습니다.

 

목표 1 정수 a, b, c 가 주어졌을때, ax + by = c의 정수해 (x, y)를 찾아보자.

 

이때 정수해가 무엇을 말하는 것일까?

1. 하나의 정수해
2. 모든 정수해

 

우리는 하나의 정수해부터 구한다.

 

목표 2 : 정수 a, b가 주어졌을때, ax + by의 값으로 만들수 있는 정수를 모두 찾아보자.

 

관찰: 42x + 30y의 값들

 

 

규칙성을 찾아보니, 모두 42와 30의 최대공약수인 6의 배수였고, 

그 최대공약수가 표에 있었다!

ax + by 의 값에 대해

1. gcd(a, b)로 나누어진다
2. gcd(a, b) = ax + by의 정수해가 존재한다

 

1-증명

 

gcd(a, b) = g라 두면, a = gn, b = gm으로 나타낼수 있고,

ax + by = g(nx + my)이므로 모든 값은 g로 나누어진다.

 

2-증명 

a, b의 gcd를 유클리드 호제법을 통해 구하는 과정을 자세하게 서술해보면

 

a = q1b + r1   r1 = a - q1*b

b = q2r1+ r2  r2 = b- q2*r1 = b - q2(a- q1b)

r1= q3r2+  r3r3 = (a- q1b)- q3* r2 = r2 - q3*(b - q2(a- q1b))

…

 

이런식으로 나타내어서 a와 b에대한 식으로 묶어 나타낼수 있고, 그러니 해가 있다.

 

마찬가지로, 이렇게 해가 있음을 증명하였으니, 이 방법을 그대로 따라가주기만 해도 ax + by = gcd(a, b) 의 해를 구할 수 있을것이다. 자세한 설명은 불필요할것같으니 궁금하면 해보고 아니면 말아라.

 

예로64와 22일때 (64x + 22y = 2)

64 = 2 * 22 + 20 

22 = 1* 20 + 2

20 = 10 * 2 + 0 - 종료

나머지에 대한 식으로 바꾸어보자

2 = 22- 20 * 1

20 = 64- 22*2

아래거를 위에꺼에다 대입해주면

2 = 22 - (64 - 22 *2) *1이고

2 = -1*64 + 3*22 으로 나타낼수있다.

이제 64x + 22y = 2k의 모든 해는

(-1*k, 3*k)의 꼴로 나타낼수 있는것이다.

 

위 방정식의 한 해가 ( x0,  y0)이고, g = gcd(a, b), g | c 라면

 

ax0+ by0= c가 성립하고

 

여기에 다양한해를 얻고 싶다면 ax0, by0 각각에 같은수를 더하고 빼주면 된다. 그 더하고 빼지는 수를 n이라고 두면, 

 

ax0+n + by0-n = c이다.

 

하지만 방정식의 해로 나타내야 하니 각각을 a와 b로 묶어 나타내면 

 

a(x0+n/a) + b(y0-n/b) = c이다.

 

이때 (x, y)는 정수의 순서쌍이니 a|n, b|n이다. 그러니 n은 a와 b의 공배수일것이다.

 

lcm(a, b) = ab/g이므로 n =abk/g으로 나타낼수 있다.

 

그러면 식은 

 

a(x0+bk/g) + b(y0-ak/g) = c이다.

 

해는 (x0+bk/g, y0-ak/g)이다 .

이렇게 모든해를 구할수 있다.

위 내용은 강의의 전부는 아니지만, 제가 생각하기에 중요한 내용을 간추려 정리한것입니다.