정수론 6장 - 선형방정식과 최대공약수를 파헤쳐보자!
이상준 교수님의 강의영상을 참고하였습니다. 목표 1 정수 a, b, c 가 주어졌을때, ax + by = c의 정수해 (x, y)를 찾아보자. 이때 정수해가 무엇을 말하는 것일까? 하나의 정수해 모든 정수해 우리는 하나의 정수해부터 구한다. 목표 2 : 정수 a, b가 주어졌을때, ax + by의 값으로 만들수 있는 정수를 모두 찾아보자. 관찰: 42x + 30y의 값들 규칙성을 찾아보니, 모두 42와 30의 최대공약수인 6의 배수였고, 그 최대공약수가 표에 있었다! ax + by 의 값에 대해 gcd(a, b)로 나누어진다 gcd(a, b) = ax + by의 정수해가 존재한다 1-증명 gcd(a, b) = g라 두면, a = gn, b = gm으로 나타낼수 있고, ax + by = g(nx + my)..
