[정수론](24)[펠 방정식 정리 증명 - 1]

 

|$x-y\sqrt{D} \ |< \frac{1}{y}$ 을 만족하는 무한한 순서쌍 (x, y)가 존재한다고 디오판토스 근사에서 보였다.
이를 이용해서 펠 방정식 정리를 증명해보자.

• 펠 방정식 정리
  D가 제곱수가 아닌 양의 정수일 때 펠 방정식 x^2-Dy^2 = 1에 대해,
  1. 항상 양의 정수해를 가짐
  2. 해 (x1, y1)이 가장 작은 정수해라면?
     모든 해 (xk, yk)를 $x_k+y_k\sqrt{D} \ = (x_1+y_1\sqrt{D})^k$ 로 구할 수 있다.

 

1. 양의 정수해를 가짐의 증명

 

디리클레의 디오판토스 근사정리 제 1형식에 따르면
|$x-y\sqrt{D} \ |< \frac{1}{y}$ 을 만족하는 무한한 순서쌍 (x, y)가 존재한다.
즉, $-\frac{1}{y} < x-y\sqrt{D} \ < \frac{1}{y}$ 이고 이항하면 x < 1/y + y$\sqrt{D}$ 라는 소리다.
양변에 y$\sqrt{D}$를 더하면 x + y$\sqrt{D}$ < 1/y + 2y$\sqrt{D}$ 이고, y가 정수이므로 3y$\sqrt{D}$ 보다 작다.
정리하자면, x + y$\sqrt{D}$ < 1/y + 2y$\sqrt{D}$ < 3y$\sqrt{D}$
양변에 x-y$\sqrt{D}$를 곱하고, 근사정리 제 1형식을 이용하면,
x^2 - Dy^2 < 3y$\sqrt{D}$*(x-y$\sqrt{D}$) < 1/y*3y$\sqrt{D}$ = 3$\sqrt{D}$ 이다.
즉, 양의 정수해 (x, y)는 |x^2 - Dy^2| < 3$\sqrt{D}$ 를 만족한다.

 

이제 비둘기집의 원리를 이용해보자.
비둘기: 양의 정수해 (x, y)                     <- 무한히 많음
비둘기 집: 해가 존재하는 구간의 정수    <- 유한함
    해는 $-\lfloor{3\sqrt{D}}\rfloor$ 부터 $\lfloor{3\sqrt{D}}\rfloor$ 사이에 존재할 것이다.
그리고 비둘기를 집에 대입해보자.
    단순히 x^2 - Dy^2의 값과 일치하는 구간의 정수 집에 대응시킬 것이다.
     즉, x1^2 - Dy1^2 = k 이고 $-\lfloor{3\sqrt{D}}\rfloor$ < k < $\lfloor{3\sqrt{D}}\rfloor$ 라면 (x1, y1)을 비둘기집 k에 넣는다.
이때, 비둘기는 무한히 많은데 집은 유한하므로,
'어떤' 집에는 비둘기가 무한히 많이 있을 것이고, 그 집을 m이라고 하겠다
(이때 m이 양수라고 하자. 음수일때도 어짜피 동일한 방법으로 증명될테니...)

 

즉, 어떤 m에 대해 x^2 - Dy^2 = m인 (x, y)가 무한히 있다.
이때의 해 (x, y)를 (X1, Y1), (X2, Y2), ...라고 하자.
또 비둘기 집 정리를 이용할 것이다.
비둘기: (X1, Y1), (X2, Y2), ...                             <- 무한히 많음
비둘기 집: (A, B) {A, B는 정수, 0 <= A, B < m}   <- m^2 개로 유한함
그리고 대응은
     X ≡ A (mod m) 이고, Y ≡ B (mod m) 이면 (X, Y)를 집 (A, B)에 넣는다.
이것 또한 비둘기는 무한히 넘쳐나는데 집은 유한하므로,
어떤 집에는 비둘기가 무한히 많이 있을 것이다. 그리고 당연히 어떤 집에선 같은 집에 2마리 이상 있을 수 있다.
이때 같은 집에 있는 서로 다른 두 해를 (Xk, Yk), (Xj, Yj)라고 하자.
같은 집에 있으므로, 다음 성질을 만족한다.
     Xk ≡ Xj (mod m), Yk ≡ Yj (mod m)
     (Xk)^2 - D(Yk)^2 = m = (Xj)^2 - D(Yj)^2

 

(Xk, Yk), (Xj, Yj)를 이용해 펠 방정식의 해를 구해보자.
u+y$\sqrt{D}$ = $\frac{X_j - Y_j\sqrt{D}}{X_k - Y_k\sqrt{D}}$ 라고 해보자.
$$\frac{X_j - Y_j\sqrt{D}}{X_k - Y_k\sqrt{D}} = \frac{(X_j X_k - Y_jY_kD)+(X_jY_k-X_kY_j)\sqrt{D}}{X_k^2 - D {Y_k}^2} = \frac{(X_j X_k - Y_jY_kD)}{m} + \frac{(X_jY_k-X_kY_j)}{m}\sqrt{D}$$
즉, u = $\frac{(X_j X_k - Y_jY_kD)}{m}$, v = $\frac{(X_jY_k-X_kY_j)}{m}$ 라는 소리이다.
실제로 노가다로 대입하면 식 정리에 의해 u, v가 펠 방정식 x^2 - Dy^2 = 1의 해가 된다.

 

이때 우리가 보이고 싶은 건
     u, v가 정수이다
     u, v가 양수이다
정수 증명
u, v의 분자가 m의 배수여야 한다.

• u
  Xk ≡ Xj (mod m), Yk ≡ Yj (mod m) 이므로
  XkXj ≡ (Xk)^2 (mod m), YkYj ≡ (Yk)^2 (mod m)
  XjXk - YjYkD ≡ (Xk)^2 - D (Yk)^2 ≡ m ≡ 0 (mod m)이므로,
  정수 맞음
• v
  Xk ≡ Xj (mod m), Yk ≡ Yj (mod m) 이므로
  XjYk - XkYj ≡ XjYj - XjYj ≡ 0 (mod m)
  따라서 정수 맞음

양수 증명

• u
  u = 1 + Dv^2 이므로
  u >= 1 이므로 양수인건 자명함
• v
  어짜피 u^2 - Dv^2 = 1 방정식에서 제곱이라서
  v가 음수가 나와도 +로 바꿔주면 되니까 v가 0만 아니면 양수라고 볼 수 있다.
  만약 v = 0 이라면?
      XjYk - XkYj = 0 즉 ,XjYk = XkYj
      (Yk)^2 \* m = (Yk)^2 \* (Xj^2 - DYj^2) = (XjYk)^2 - D(YjYk)^2
      = Yj^2 \* (Xk^2 - DYk^2) = Yj^2 \* m
      즉, Yk = Yj가 된다.
      이때 맨 처음 X, Y를 정의할 때 서로 다른 해라 했으므로, 모순된다.
      따라서 v = 0 이 아니다.

따라서 우리는 모든 펠 방정식이 양의 정수해를 가진다는걸 증명했다.