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

問題

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

証明

$x^2+y^2=qxy+r,xy+1<q+r,$$0\le 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_0{y}_0>1$である。また、$x,y$は対称であるから$x_0\ge y_0$として良い。ここで$(x^{\prime },y^{\prime },q^{\prime },r^{\prime })=(y_0,(q_0+1)y_0-x_0,q_0-t,(1+t)x^{\prime }{y}^{\prime }-x_0{y}_0+r_0)$
とし、$x^{\prime },y^{\prime }>0$ であることをまず示す。$x^{\prime }>0$は自明である。
$x_0^2+y_0^2=q_0{x}_0{y}_0+r_0$から
$y^{\prime }=(q_0+1)y_0-x_0={\displaystyle \frac{y_0^2+x_0{y}_0-r_0}{x_0}}$
が分かり$y_0^2>0,x_0{y}_0-r_0>0$より$y^{\prime }>0$ であり、$x^{\prime },y^{\prime }>0$ が示された。ここで$t$を$0\le r^{\prime }<x^{\prime }{y}^{\prime }$となる整数とする。$r^{\prime }$において$t$の係数は$x^{\prime }{y}^{\prime }$ であるから$t$は存在する。$(x^{\prime },y^{\prime },q^{\prime },r^{\prime })\in S$かつ$x_0+y_0>x^{\prime }+y^{\prime }$であることを示せば最小性に矛盾するのでそれらを示す。示すべきことは
・$x^{\prime 2}+y^{\prime 2}=q^{\prime }{x}^{\prime }{y}^{\prime }+r^{\prime }\cdots \mathbf{(}\mathit{A}\mathbf{)}$
・$x^{\prime }{y}^{\prime }+1<q^{\prime }+r^{\prime }\cdots \mathbf{(}\mathit{B}\mathbf{)}$
・$0\le r^{\prime }<x^{\prime }{y}^{\prime }\cdots \mathbf{(}\mathit{C}\mathbf{)}$
・$x^{\prime },y^{\prime },q^{\prime }>0\cdots \mathbf{(}\mathit{D}\mathbf{)}$
・$x_0+y_0>x^{\prime }+y^{\prime }\cdots \mathbf{(}\mathit{E}\mathbf{)}$
である。$\mathbf{(}\mathit{C}\mathbf{)}$は$t$の取り方から自明であるからそれ以外を示す。

$\mathbf{(}\mathit{A}\mathbf{)}$の証明

$x^{\prime 2}+y^{\prime 2}=q^{\prime }{x}^{\prime }{y}^{\prime }+r^{\prime }$
$⟺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_0{y}_0+r_0$
$⟺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_0{y}_0+r_0$
$⟺x_0^2+y_0^2=q_0{x}_0{y}_0+r_0$

$\mathbf{(}\mathit{B}\mathbf{)}$の証明

まず$t\ge 0$を示す。
$t\le -1$と仮定すると$x^{\prime }{y}^{\prime }>0$だから
$0\le r^{\prime }=(1+t)x^{\prime }{y}^{\prime }-x_0{y}_0+r_0\le -x_0{y}_0+r_0<0$となり矛盾。
$x^{\prime }{y}^{\prime }+1<q^{\prime }+r^{\prime }$
$⟺x^{\prime }{y}^{\prime }+1<q_0-t+(t+1)x^{\prime }{y}^{\prime }-x_0{y}_0+r_0$
$⟺x_0{y}_0+1<q_0+r_0+t(x^{\prime }{y}^{\prime }-1)$
この同値が成り立つが$x_0{y}_0+1<q_0+r_0$かつ$0\le t(x^{\prime }{y}^{\prime }-1)$より$x_0{y}_0+1<q_0+r_0+t(x^{\prime }{y}^{\prime }-1)$が成り立つから$x^{\prime }{y}^{\prime }+1<q^{\prime }+r^{\prime }$が成り立つ。

$\mathbf{(}\mathit{D}\mathbf{)}$の証明

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

$\mathbf{(}\mathit{E}\mathbf{)}$の証明

$x_0>y^{\prime }$を示せばよいが$y^{\prime }={\displaystyle \frac{y_0^2+x_0{y}_0-r_0}{x_0}}$であるから$x_0^2>y_0^2+x_0{y}_0-r_0$を示せばよい。
$x_0^2=(x_0^2+y_0^2)-y_0^2=(q_0{x}_0{y}_0+r_0)-y_0^2$
$>(q_0+1)x_0{y}_0-q_0+1-y_0^2\because r_0>x_0{y}_0+1-q_0$
$=(q_0-1)(x_0{y}_0-1)+2x_0{y}_0-y_0^2$
$\ge q_0-1+y_0^2\because x_0{y}_0>1,x_0{y}_0\ge y_0^2$
$>y_0^2+x_0{y}_0-r_0\because q_0>x_0{y}_0+1-r_0$
より示せた。

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

最後に

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