x^2+y^2をxyで割った商と余りに関する不等式

問題

かなり綺麗な主張の整数問題です。以下証明。
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…

証明

$x^2+y^2=qxy+r,~~xy+1 < q+r,~~$$0 \leq r< xy ,~~x,y,q>0$となる整数の組$(x,y,q,r)$の集合を$ S$とする。$ S$が空集合でないと仮定して矛盾を示す。$ S$の要素のうち$x+y$が最小となる組を$(x_0,y_0,q_0,r_0)$とする。$x_0=y_0=1$では無いので$x_0y_0>1$である。また、$x,y$は対称であるから$ x_0 \geq y_0$として良い。ここで$(x',y',q',r')=(y_0,(q_0+1)y_0-x_0,q_0-t,(1+t)x'y'-x_0y_0+r_0)$
とし、$x',y'>0$ であることをまず示す。$x'>0$は自明である。
$x_0^2+y_0^2=q_0x_0y_0+r_0$から
$y'=(q_0+1)y_0-x_0=\dfrac{y_0^2+x_0y_0-r_0}{x_0}$
が分かり$y_0^2>0,x_0y_0-r_0>0$より$y'>0$ であり、$x',y'>0$ が示された。ここで$t$を$0 \leq r'< x'y'$となる整数とする。$r'$において$t$の係数は$x'y'$ であるから$t$は存在する。$(x',y',q',r')\in S$かつ$x_0+y_0>x'+y'$であることを示せば最小性に矛盾するのでそれらを示す。示すべきことは
・$x'^2+y'^2=q'x'y'+r'\quad\cdots \boldsymbol{(A)} $
・$x'y'+1 < q'+r'\qquad~~~\cdots \boldsymbol{(B)}$
・$0 \leq r'< x'y'\qquad\qquad ~ ~ ~ \cdots \boldsymbol{(C)}$
・$x',y',q'>0\qquad\qquad\quad\cdots \boldsymbol{(D)}$
・$x_0+y_0>x'+y'\qquad~~~\cdots \boldsymbol{(E)}$
である。$ \boldsymbol{(C)}$は$t$の取り方から自明であるからそれ以外を示す。

$\boldsymbol{(A)}$の証明

$x'^2+y'^2=q'x'y'+r'$
$ \Longleftrightarrow y_0^2+((q_0+1)y_0-x_0)^2=(q_0-t)y_0((q_0+1)y_0-x_0)+(1+t)y_0((q_0+1)y_0-x_0)-x_0y_0+r_0$
$ \Longleftrightarrow x_0^2+(1+(q_0+1)^2-q_0(q_0+1)-(q_0+1))y_0^2=(2(q_0+1)-q_0-2)x_0y_0+r_0$
$ \Longleftrightarrow x_0^2+y_0^2=q_0x_0y_0+r_0$

$\boldsymbol{(B)}$の証明

まず$t \geq 0$を示す。
$t \leq -1$と仮定すると$x'y'>0$だから
$0 \leq r'=(1+t)x'y'-x_0y_0+r_0 \leq -x_0y_0+r_0<0$となり矛盾。
$x'y'+1< q'+r'$
$ \Longleftrightarrow x'y'+1< q_0-t+(t+1)x'y'-x_0y_0+r_0$
$ \Longleftrightarrow x_0y_0+1< q_0+r_0+t(x'y'-1)$
この同値が成り立つが$x_0y_0+1< q_0+r_0$かつ$0 \leq t(x'y'-1)$より$ x_0y_0+1< q_0+r_0+t(x'y'-1)$が成り立つから$x'y'+1< q'+r'$が成り立つ。

$\boldsymbol{(D)}$の証明

$x',y'>0$は先ほど示したので$q'>0$を示す。$\boldsymbol{(A),(C)}$より$x'^2+y'^2=q'x'y'+r'<(q'+1)x'y'$であるが有名な不等式より$ 2x'y'\leq x'^2+y'^2$で$2x'y'<(q'+1)x'y'$となる。$x',y'>0$であるから$1< q'$である。特に$q'>0$となる。

$\boldsymbol{(E)}$の証明

$x_0>y'$を示せばよいが$y'=\dfrac{y_0^2+x_0y_0-r_0}{x_0}$であるから$x_0^2>y_0^2+x_0y_0-r_0$を示せばよい。
$x_0^2=(x_0^2+y_0^2)-y_0^2=(q_0x_0y_0+r_0)-y_0^2$
$>(q_0+1)x_0y_0-q_0+1-y_0^2\qquad\because r_0>x_0y_0+1-q_0$
$=(q_0-1)(x_0y_0-1)+2x_0y_0-y_0^2$
$ \geq q_0-1+y_0^2\qquad \because x_0y_0>1,x_0y_0 \geq y_0^2$
$>y_0^2+x_0y_0-r_0\qquad\because q_0>x_0y_0+1-r_0$
より示せた。

よって上より矛盾。$ S$は空集合より題意は満たされた。

最後に

vieta jumpingという方法を用いた証明でした。