[정수론](23)[펠 방정식 & 디오판토스 근사]

펠 방정식

D가 양의 정수이고 제곱수가 아닐 때,
x^2 - Dy^2 = 1 인 디오판토스 방정식

해 얻기
    펠 방정식의 어떤 해를 x1, y1이라 하자.
    1 = (x1^2 - Dy1^2) = ($x_1-y_1\sqrt{D}$)($x_1+y_1\sqrt{D}$)
    1^2 = ($x_1-y_1\sqrt{D}$)^2($x_1+y_1\sqrt{D}$)^2 = (x1^2 + y1^2D)^2 - (2x1y1)^2 D
    즉, (x1, y1)으로부터 새로운 해 (x1^2 + y1^2*D, (2x1y1)^2)를 얻어낼 수 있다.

    -> k배를 해서 해를 얻을 수 있다

 

펠 방정식 정리

• 항상 양의 정수해를 가짐
• 해 (x1, y1)이 가장 작은 정수해라면?
  모든 해 (xk, yk)를 $x_k+y_k\sqrt{D} \ = (x_1+y_1\sqrt{D})^k$ 로 구할 수 있다.

증명은 (정수론 24), (정수론 25) 참고

 

비둘기 집의 원리

비둘기 m마리, 비둘기 집 n개가 있을 때
m>n이라면, 적어도 하나의 비둘기 집에는 비둘기가 2마리 이상이다.

 

디오판토스 근사

무리수 $\sqrt{D}$를 유리수 x/y로 근사하는 방법
즉, $x-y\sqrt{D}$가 작을수록 더 정확한 근사이므로, 절댓값을 작게 만드는게 목표!

$y\sqrt{D}$와 가까운 정수 하나를 잡아 차이를 구한다 생각해보자.
1칸마다 정수가 있으므로 차이의 최대는 1/2보다는 작거나 같을 것이다
|$x-y\sqrt{D} \ |<= \frac{1}{2}$
여기서 1/2보다 더 작게 만들어 보자.

디리클레의 디오판토스 근사정리 - 제 1형식
D가 완전제곱수가 아닌 양의 정수일 때,
|$x-y\sqrt{D} \ |< \frac{1}{y}$ 을 만족하는 무한한 순서쌍 (x, y)가 존재

• 증명
  적당히 큰 수 Y에 대해 0$\sqrt{D}$, 1$\sqrt{D}$, ..., Y$\sqrt{D}$가 있다 하자.
  이떄 정수부와 소수부로 나누고 F를 비둘기라 생각하자.
  0$\sqrt{D}$ = N0 + F0, 1$\sqrt{D}$ = N1 + F1, ..., Y$\sqrt{D}$ = NY + FY
  (N = 정수, F = 소수부 {0<= F < 1})
  즉, F0, F1, ..., FY 총 Y+1마리의 비둘기가 있다
  그리고 비둘기 집을 만들기 위해 0~1 사이 구간을 Y등분하자
  집1: 0<=t<1/Y, 집2: 1/Y<=t<2/Y, ...., 집Y: (Y-1)/Y<=t<1
  비둘기집의 정리에 의해 어떤 Fm, Fn은 같은 집(구간)에 있다.
  즉, |Fm - Fn| < 1/Y (m<n이라 하자)
  |Fm - Fn|= |(m$\sqrt{D}$ - Nm)- (n$\sqrt{D}$ - Nn)| = |(Nm-Nn) - (m-n)$\sqrt{D}$| < 1/Y
  x = Nm-Nn, y = m-n은 정수이고,
  0<= m < n <= Y이므로 0 < m-n <= Y
  따라서 |$x-y\sqrt{D} \ |< \frac{1}{Y} < \frac{1}{y}$인 무한히 많은 정수쌍 존재
• 디리클레의 디오판토스 근사정리 - 제 2형식
  $ \alpha > 0 $ 이 무리수라면 |$x-y\alpha \ |< \frac{1}{y}$인
  무한히 많은 정수 순서쌍 (x, y)가 존재
  [[x번외) 디리클레의 디오판토스 근사형식 - 제 2형식]] 참고