Saturday, January 4, 2014

Number Theory - 2

1. 일차부정방정식의 해
(1) 일차부정방정식 ax+by=c에서 d=(a,b)라 할 때, 이 방정식이 정수해를 갖기 위한(A) 필요충분조건은 d|c인 것(B)이다.

i) A이기 위한 충분조건 증명
ax+by=c가 정수해 x=x0, y=y0를 가진다면 ax0+by0 = c이다.
그런데 d|a이고 d|b이어서 d|ax0+by0 = c 즉 d|c이다.

ii) A이기 위한 필요조건 증명
(a, b) = d이면 d = as +bt를 만족하는 정수 s, t가 존재하고 d|c이므로 c=dk이다.(k는 정수)
c=kd=aks+bkt에서 x=ks,y=kt는 주어진 방정식의 정수해이다.
따라서 d|c이면 정수해를 가진다.

(2) 일차부정방정식 ax+by=c에서 d=(a,b)이고 d|c이면 x=x0, y=y0가 이 방정식의 한 정수해일 때, 이 방정식의 정수해 전체는 x=x0+(b/d)k, y=y0-(a/d)k(k∈Z)이다.

(증명)
d|c일 때, x=x0, y=y0를 주어진 방정식의 특수해라고 하면
ax+by=c=ax0+by0에서 a(x-x0)=-b(y-y0) → a(x-x0)/d = -b(y-y0)/d
→ (b/d)|(a(x-x0)/d)이고 (a/d, b/d) = 1이므로 (b/d)|(x-x0)이다.
x-x0=(b/d)k이므로 y-y0 = -(a/d)k이다.
∴x=x0+(b/d)k, y=y0-(a/d)k

(3) 정수 a1, a2, ... , an, c에 대하여 d = (a1, a2, ... , an)일 때 일차부정방정식 a1x1+a2x2+...+anxn=c가 정수해를 가질 필요충분조건은 d|c이다.

No comments:

Post a Comment