無限降下法

1：$S\neq\emptyset$ と仮定する。像 $h(S)$ は $\mathbb{N}$ の空でない部分集合なので最小元 $m$ をもつ（$\mathbb{N}$ の整列性。数学的帰納法と整列性 の定理「帰納法・強い帰納法・整列性の同値性」）。$m=h(s)$ となる $s\in S$ をとると、仮定から $h(t)< h(s)=m$ を満たす $t\in S$ がある。$h(t)$ は $h(S)$ の元で $m$ より小さいので、$m$ の最小性に反する。よって $S=\emptyset$ である。
2：そのような列があったとすると、$\{h(s_n)\mid n\in\mathbb{N}\}$ は $\mathbb{N}$ の空でない部分集合なので最小元 $h(s_k)$ をもつ。ところが $h(s_{k+1})< h(s_k)$ なので、これは最小元であることに反する。$\square$

$m\ge1$ と $(0,0,0)$ でない整数の組 $(x,y,z)$ で $x^2+y^2+z^2=2^mxyz$ を満たすものについて、組 $(m,x,y,z)$ 全体を $S$ とし、高さを $h(m,x,y,z):=|x|+|y|+|z|$ とする（$S$ の元では $h\ge1$）。
$(m,x,y,z)\in S$ とする。整数の平方は、偶数の平方なら $4$ の倍数、奇数の平方なら $4$ で割って $1$ 余る。右辺は偶数なので左辺も偶数であり、$x,y,z$ のうち奇数は $0$ 個か $2$ 個である。$2$ 個だとすると、左辺は $4$ で割って $2$ 余る。一方、残りの 1 つは偶数なので右辺 $2^mxyz$ は $2^{m+1}$ で割り切れ、$m\ge1$ より $4$ の倍数である。これは矛盾なので、$x,y,z$ はすべて偶数である。$x=2a$、$y=2b$、$z=2c$ とおくと $4(a^2+b^2+c^2)=2^{m+3}abc$、すなわち
$$ a^2+b^2+c^2=2^{m+1}abc $$
である。$(a,b,c)\neq(0,0,0)$ なので $(m+1,a,b,c)\in S$ であり、その高さは $h(m,x,y,z)/2$ で、もとの高さより真に小さい。thm-desc-principle の 1 により $S=\emptyset$ である。$\square$

1：$f(t):=t^2-kxy\,t+(x^2+y^2)$ とおくと、$(x,y,z)$ が解であることは $f(z)=0$ と同じである。$f(kxy-t)=(kxy-t)^2-kxy(kxy-t)+x^2+y^2=t^2-kxy\,t+x^2+y^2=f(t)$ なので $f(z')=f(z)=0$ であり、$(x,y,z')$ も $(\mathrm{M}_k)$ を満たす。また $f(z)=0$ から $z(kxy-z)=x^2+y^2$、すなわち $zz'=x^2+y^2$ である。$x^2+y^2>0$、$z>0$ なので $z'>0$ であり、$z'=kxy-z$ は整数である。最後に $kxy-z'=z$ である。2：$zz'=x^2+y^2< z^2$ を $z>0$ で割ればよい。$\square$

段 1（降下）。正の整数解 $(x,y,z)$ を $x\le y\le z$ と並べたとき、$z^2\le x^2+y^2$ となるものを 基本解 と呼ぶ。基本解でない解に、最大の座標 $z$ を取り替える Vieta 移動を施すと、lem-desc-vieta により正の整数解が得られ、座標の和は真に減る。並べ替えて同じことを繰り返すと、座標の和は真に減り続けるので、thm-desc-principle の 2 により無限には続かない。続けられなくなった解は基本解なので、どの正の整数解からも、並べ替えと Vieta 移動を有限回施して基本解に達する。
段 2（基本解）。$(x,y,z)$ を基本解とする。$z^2\le x^2+y^2$ と $x\le y\le z$ から
$$ kxyz=x^2+y^2+z^2\le2(x^2+y^2)\le4y^2\le4yz $$
なので、両辺を $yz$ で割って $kx\le4$ である。

• $k\ge5$ のとき：$kx\ge5$ となるので基本解はない。
• $k=4$ のとき：$x=1$ であり、$4y^2\le4yz\le2(1+y^2)$ から $y=1$ である。すると方程式は $z^2-4z+2=0$ となるが、その根 $2\pm\sqrt2$ は整数でない。基本解はない。
• $k=3$ のとき：$x=1$ であり、$3y^2\le3yz\le2(1+y^2)$ から $y=1$ である。方程式 $z^2-3z+2=0$ から $z=1$ または $z=2$ で、$z^2\le x^2+y^2=2$ から $z=1$ である。基本解は $(1,1,1)$ だけである。
• $k=2$ のとき：prop-desc-two-power（$m=1$）により、正の整数解そのものがない。
  段 3（$k\neq1$ の場合の結論）。$k\ne1$ とし、正の整数解があるとする。段 1 によりそこから基本解に達するので、段 2 により $k=3$ であり、達する基本解は $(1,1,1)$ である。並べ替えは逆にたどれ、Vieta 移動は同じ座標にもう一度施すと元に戻る（lem-desc-vieta の 1）。したがって段 1 の手順を逆にたどれば、$(1,1,1)$ からもとの解が得られる。これで 2 と、1 のうち $k\ne1$ の部分が示された。
  段 4（$k=1$）。$x^2+y^2+z^2=xyz$ とする。平方数を $3$ で割った余りは $0$ か $1$ で、$0$ になるのは $3$ の倍数の平方のときに限る。$x,y,z$ のうち $3$ の倍数でないものの個数を $j$ とすると、左辺を $3$ で割った余りは $j$ を $3$ で割った余りに等しい。$j=3$ なら右辺は $3$ の倍数でないのに左辺は $3$ の倍数であり、$j=1,2$ なら右辺は $3$ の倍数なのに左辺は $3$ の倍数でない。どちらも矛盾なので $j=0$ である。$x=3a$、$y=3b$、$z=3c$ とおくと $9(a^2+b^2+c^2)=27abc$、すなわち $a^2+b^2+c^2=3abc$ である。逆に $(a,b,c)$ が Markov 方程式の正の整数解なら、同じ計算を逆にたどって $(3a,3b,3c)$ は $(\mathrm{M}_1)$ の正の整数解である。これで 3 が示され、$(3,3,3)$ が $(\mathrm{M}_1)$ の解なので 1 も示された。$\square$

無限個あること：解 $(x,y,z)$ を $x\le y\le z$ と並べ、最小の座標 $x$ を取り替える移動を施すと、新しい座標 $3yz-x$ は $y\ge1$、$x\le z$ から $3yz-x\ge3z-z=2z>z$ を満たす。よって新しい解の最大の座標はもとの解の最大の座標より真に大きい。$(1,1,1)$ から始めてこれを繰り返せば、最大の座標が互いに異なる解が無限に得られる。
互いに素であること：素数 $p$ がある解の 2 つの座標、たとえば $x,y$ を割るとすると、$z^2=3xyz-x^2-y^2$ は $p$ で割り切れ、$p\mid z$ となる。「$p$ が 3 つの座標をすべて割る」という性質は、並べ替えでも Vieta 移動でも保たれる（$p\mid x,y,z$ なら $p\mid 3xy-z$）。thm-desc-markov の 2 の手順でこの解から $(1,1,1)$ に達するので、$p$ は $1$ を割ることになり矛盾する。$\square$