일차방정식의 정수해 알아보기

일차방정식의 정수해

$a,b,c$가 정수이고 $a$와 $b$ 중에 적어도 하나는 0이 아니라 하자.

두 정수 $s, t$에 대해 $as+bt=c$일 때, 방정식 $ax+by=c$의 모든 정수해는

$x=s+\frac{bk}{d}, y=t-\frac{ak}{d}$ 이다.

이때 $d=gcd(a,b)$이고 $k$는 임의의 정수이다.

 

증명하기

$as+bt=c$ 이고 $\frac{a}{d}, \frac{b}{d}$ 는 모두 정수이므로 임의의 정수 $k$에 대하여 $x=s+\frac{bk}{d}$, $y=t-\frac{ak}{d}$ 가 주어진 방정식의 정수해가 된다.

 

$x', y'$을 주어진 방정식의 임의의 정수해라 하자.

$as+bt = c=ax'+by'$에서 $a(x'-s)=b(t-y')$이다.

$d=gcd(a,b)$이므로 $a=a'd$, $b=b'd$ 라 하면 $a'$, $b'$은 서로소이다.

$a'(x'-s)=b'(t-y')$ 으로부터 $a' | b' (t-y')$이다. 따라서 $a' | (t-y')$ 이다.

즉, 적당한 정수 $k$에 대해 $y'=t-a'k = t-\frac{ak}{d}$ 이고, 이를 $a'(x'-s)=b'(t-y')$을 대입하면,

$x' = s+b'k=s+\frac{bk}{d}$ 이다. 따라서 모든 정수해는 $x=s+\frac{bk}{d}$, $y=t-\frac{ak}{d}$ 이다.

 

$a$, $b$가 서로소이면 계수가 정수인 방정식 $ax+by=c$는 항상 해를 가진다.

임의로 주어진 계수가 정수인 방정식 $ax+by=c$의 정수해를 모두 구하려면, $gcd(a,b)=d$일때, $d | c$를 확인한다.

$d \not\mid c$ 이면 주어진 일차방정식은 해가 없다.

$d \mid c$ 이면 유클리드 호제법을 이용하여 $as'+bt'=d$인 $s', t'$을 구한다.

$s=\frac{s'c}{d}, t=\frac{t'c}{d}$가 주어진 방정식의 한 정수해이고, 일차방정식의 정수에 대한 정리를 이용하면 모든 정수해를 구할 수 있다.