정수론

[정수론](4)[선형방정식과 최대공약수]

황올뱀 2025. 4. 15. 17:09

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

  • 증명
    gcd(a, b) | ax+by이므로 참

유클리드 호제법으로 ax+by=gcd(a, b) 해 구하기

  • 방법&증명
    a = b*q1+r1
    b = r1*q2+r2
    r1= r2*q3+r3
    ...
    r(n-3) = r(n-2)*q(n-1)+r(n-1)
    r(n-2) = r(n-1)*q(n)+r(n)
    r(n-1) = r(n)*q(n+1)+0
    라고 유클리드 호제법을 한 뒤,
    r1 = a - b*q1 처럼 정리하고 다음 식에 대입하면,
    결국 r(n) = a(...) + b(...) 꼴로 정리되므로
    이 방법으로 구하면 된다.
  • 예) 22x+60y=2 (단, gcd(22, 60) = 2)
    22 = a, 60 = b라 두고,
    60 = 22*2 + 16 -> 16 = b - 2a
    22 = 16*1 + 6 -> 6 = a - 16 = a - (b-2a) = 3a - b
    16 = 6*2 + 4 -> 4 = 16 - 2*6 = (b-2a) - 2(3a - b) = -8a + 3b
    6 = 4*1 + 2 -> 2 = 6 - 4 = (2a) - (3b-8a) = 11a - 4b
    4 = 2*2 + 0
    따라서 11*22 + (-4)*60 = 2이므로 해는 (11, -4)

ax+by=gcd(a, b)는 항상 정수해 (x, y) 를 가지는가? -> 참

  • 증명
    만약 ax+by꼴을 모은 집합 S가 있을 때, (단, ax+by>0, 각 숫자는 정수)
    S에 원소가 1개 이상 있고
    S의 원소 중 가장 작은게 gcd(a, b)라면 참
    • S 원소가 1개 이상인가?
      조건을 만족하는 수 중 S에
      적어도 (a+0, 0+b, -a+0, 0-b) 중 1개는 들어가므로 원소는 1개 이상임.
    • S 원소 중 가장 작은게 gcd(a, b)인가? (즉, S안에 gcd(a, b)가 있는가?)
      가장 작은 수를 d라고 가정할 때 d = gcd(a, b) 는
      d|gcd(a, b)이고 gcd(a, b)|d인 것과 동치이다.
      gcd(a, b)|d=ax+by이므로 참.
      d|gcd(a, b)에서
      d가 a를 나누지 않는다면 a = dq+r (0<r<d)이다.
      따라서 r = a - dq = a(1-xq) - byq <- S의 원소
      r<d 이므로 S의 가장 작은 원소가 d라는 거에 모순
      따라서 d|a
      b에 대해서도 동일하게 증명하면 d|a, d|b => d|gcd(a, b)
      따라서 ax+by=gcd(a, b)는 항상 정수해 (x, y) 를 가진다.

선형방정식 정리

a, b는 0이 아닌 정수, g = gcd(a, b)일때,
ax+by=g는 항상 정수해 (x, y)을 가지며, 유클리드 호제법으로 찾을 수 있다.
이때 모든 정수해는 (x+(bk/g), y-(ak/g)) (k는 임의의 정수)

  • 증명
    • gcd(a, b) = 1
      (x1, y1), (x2, y2)가 다른 해라 한다면,
      ax1 + by1 = g ... (1번 식)
      ax2 + by2 = g ... (2번 식)
      y2(1번식) - y1(2번식) => a(x1y2 - x2y1) = y2-y1
      x2(1번식) - x1(2번식) => b(x2y1 - x1y2) = x2-x1
      복잡한 x1y2 - x2y1를 그냥 k로 둔다면,
      x2 = x1-bk, y2 = y1+ak
    • gcd(a, b) = g
      ax+by=g => (a/g)x + (b/g) = 1로 바꿔 앞의 경우로 동일하게 계산하면,
      x2 = x1+(bk/g), y2 = y1-(ak/g)
728x90
반응형