整数の割り算と互除法

存在：$S:=\{a-bk\mid k\in\mathbb{Z},\ a-bk\ge0\}$ とおく。$k=-|a|$ とすると $a-bk=a+b|a|\ge a+|a|\ge0$ なので、$S$ は空でない $0$ 以上の整数の集合である。整列性により $S$ には最小元があり、それを $r=a-bq$ とする。$r\ge0$ である。もし $r\ge b$ なら、$r-b=a-b(q+1)$ も $0$ 以上なので $S$ に属し、$r$ より小さい。これは $r$ の最小性に反するので $r< b$ である。
一意性：$a=bq+r=bq'+r'$、$0\le r,r'< b$ とする。$b(q-q')=r'-r$ であり、右辺の絶対値は $b$ より小さい。$q\ne q'$ なら左辺の絶対値は $b$ 以上なので矛盾する。よって $q=q'$、したがって $r=r'$ である。$\square$

$d\mid a$、$d\mid b$ なら $d\mid a-qb$ である。逆に $d\mid b$、$d\mid a-qb$ なら $d\mid(a-qb)+qb=a$ である。公約数全体が一致するので、その最大のものも一致する（$a=b=0$ のときは $a-qb=0$ で、両辺とも $0$ である）。$\square$

停止：余りの列は $b=r_1>r_2>r_3>\cdots\ge0$ と真に減少する $0$ 以上の整数の列である。$r_1=b$ から $1$ ずつ減っても $b$ 段で $0$ に達するので、$r_{n+1}=0$ となる $n\le b$ がある。
正しさ：各段で $r_{i+1}=r_{i-1}-q_ir_i$ なので、lem-dea-gcd-shift により
$$ \gcd(a,b)=\gcd(r_0,r_1)=\gcd(r_1,r_2)=\cdots=\gcd(r_n,r_{n+1})=\gcd(r_n,0)=r_n $$
である（$r_n>0$）。$\square$

$I=\{0\}$ なら $d=0$ でよい。$I\ne\{0\}$ とし、$0$ でない $u\in I$ をとると $-u=(-1)u\in I$ なので、$I$ は正の整数を含む。整列性により、$I$ に属する最小の正の整数 $d$ がある。イデアルの条件 3 により $d\mathbb{Z}\subset I$ である。
逆に $u\in I$ とし、thm-dea-division により $u=dq+r$、$0\le r< d$ と書く。$r=u+(-q)d$ はイデアルの条件 2・3 により $I$ に属する。$r>0$ なら $d$ の最小性に反するので $r=0$、すなわち $u=dq\in d\mathbb{Z}$ である。よって $I=d\mathbb{Z}$ である。
一意性：$d\mathbb{Z}=d'\mathbb{Z}$（$d,d'\ge0$）なら、$d\in d'\mathbb{Z}$、$d'\in d\mathbb{Z}$ なので $d'\mid d$ かつ $d\mid d'$（一方が $0$ なら他方も $0$）であり、$d,d'\ge0$ から $d=d'$ である。$\square$

$a\mathbb{Z}+b\mathbb{Z}$ はイデアルなので、thm-dea-principal により $a\mathbb{Z}+b\mathbb{Z}=d\mathbb{Z}$ となる $d\ge0$ がある。この $d$ が $g$ に等しいことを示す。
$a=a\cdot1+b\cdot0$、$b=a\cdot0+b\cdot1$ は $d\mathbb{Z}$ に属するので、$d$ は $a,b$ の公約数である（$d=0$ のときは $a=b=0$ を意味する）。また $d\in a\mathbb{Z}+b\mathbb{Z}$ なので $d=ax_0+by_0$ と書け、$a,b$ の任意の公約数 $c$ は $d$ を割り切る。
$a=b=0$ なら $a\mathbb{Z}+b\mathbb{Z}=\{0\}$ で $d=0=g$ である。そうでなければ $a\mathbb{Z}+b\mathbb{Z}$ は $0$ でない元を含むので $d>0$ であり、公約数 $c$ は $c\mid d$ から $c\le|c|\le d$ を満たす。$d$ 自身も公約数なので、$d$ は最大の公約数、すなわち $d=g$ である。以上で (i)(ii)(iii) が示された。$\square$

thm-dea-bezout により $ax+by=1$ となる整数 $x,y$ がある。両辺に $c$ を掛けると $c=a(cx)+(bc)y$ であり、$a\mid a(cx)$、$a\mid bc$ なので $a\mid c$ である。
$p$ が素数のとき、$\gcd(p,b)$ は $p$ の正の約数なので $1$ か $p$ である。$p$ なら $p\mid b$ であり、$1$ なら前半により $p\mid c$ である。$\square$

1：整数解があれば、$c=ax+by\in a\mathbb{Z}+b\mathbb{Z}=g\mathbb{Z}$（thm-dea-bezout）なので $g\mid c$ である。逆に $c=gk$ なら、thm-dea-bezout の $ax_1+by_1=g$ を $k$ 倍して $(x,y)=(kx_1,ky_1)$ が解になる。
2：$a':=a/g$、$b':=b/g$ とおく。$ax_1+by_1=g$ を $g$ で割ると $a'x_1+b'y_1=1$ なので、$a'$ と $b'$ の公約数は $1$ を割り切り、$\gcd(a',b')=1$ である。示された形の組が解であることは、$a\bigl(x_0+b't\bigr)+b\bigl(y_0-a't\bigr)=c+(ab'-ba')t=c$（$ab'=ab/g=ba'$）から分かる。逆に $(x,y)$ を解とすると、$a(x-x_0)+b(y-y_0)=0$ を $g$ で割って
$$ a'(x-x_0)=-b'(y-y_0) $$
である。$b'\mid a'(x-x_0)$ かつ $\gcd(b',a')=1$ なので、cor-dea-coprime-divides により $b'\mid x-x_0$、すなわち $x-x_0=b't$ となる整数 $t$ がある。代入して $a'b't=-b'(y-y_0)$、$b'\ne0$ で割って $y-y_0=-a't$ である。$\square$

$1\le i\le n$ について $r_{i-1}>r_i$ である（$i=1$ では $a>b$、$i\ge2$ では $r_i$ が $r_{i-1}$ で割った余りだから）。したがって商 $q_i=(r_{i-1}-r_{i+1})/r_i$ は正である。さらに最後の段 $r_{n-1}=q_nr_n$ では $r_{n-1}>r_n$ なので $q_n\ge2$ である。
$j=0$：$r_n\ge1=F_2$。$j=1$：$r_{n-1}=q_nr_n\ge2=F_3$。$j\ge2$ で $j-1,\,j-2$ について主張が成り立てば、$i=n-j+1$ の段 $r_{n-j}=q_{i}r_{n-j+1}+r_{n-j+2}$ と $q_i\ge1$ から
$$ r_{n-j}\ge r_{n-j+1}+r_{n-j+2}\ge F_{j+1}+F_j=F_{j+2} $$
である。$j=n-1,n$ とすると $b=r_1\ge F_{n+1}$、$a=r_0\ge F_{n+2}$ を得る。$\square$

まず $m\ge1$ について $F_m\ge\varphi^{m-2}$ を示す。$F_1=1>\varphi^{-1}$、$F_2=1=\varphi^0$ であり、$\varphi^2=\varphi+1$ なので、$F_m\ge\varphi^{m-2}$、$F_{m+1}\ge\varphi^{m-1}$ なら
$$ F_{m+2}=F_{m+1}+F_m\ge\varphi^{m-1}+\varphi^{m-2}=\varphi^{m-2}(\varphi+1)=\varphi^m $$
となる（数学的帰納法）。lem-dea-lame-fibonacci により $b\ge F_{n+1}\ge\varphi^{n-1}$ なので、対数をとって $n-1\le\log b/\log\varphi$ である。
次に、$\varphi^2=\varphi+1$ を繰り返し使うと $\varphi^3=2\varphi+1$、$\varphi^4=3\varphi+2$、$\varphi^5=5\varphi+3=\frac{11+5\sqrt5}2$ であり、$5\sqrt5>9$（$125>81$）なので $\varphi^5>10$ である。$b$ は $k$ 桁なので $b<10^k<\varphi^{5k}$ であり、$\varphi^{n-1}\le b<\varphi^{5k}$ から $n-1<5k$、すなわち $n\le5k$ である。$\square$

存在：$f$ の次数についての帰納法で示す。$f=0$ または $\deg f<\deg g$ なら $q=0$、$r=f$ でよい。$\deg f=m\ge n=\deg g$ とし、$f,g$ の最高次の係数を $\alpha,\beta$（$\beta\ne0$）とする。$f_1:=f-\frac\alpha\beta x^{m-n}g$ は $x^m$ の項が消えるので、$f_1=0$ または $\deg f_1< m$ である。帰納法の仮定により $f_1=gq_1+r$（$r=0$ または $\deg r< n$）と書けるので、$f=g\bigl(q_1+\frac\alpha\beta x^{m-n}\bigr)+r$ である。
一意性：$gq+r=gq'+r'$ なら $g(q-q')=r'-r$ である。$q\ne q'$ なら左辺の次数は $\deg g$ 以上だが、右辺は $0$ か次数が $\deg g$ 未満なので矛盾する。よって $q=q'$、$r=r'$ である。$\square$

$fK[x]+gK[x]$ は $0$ でない元を含むので、次数が最小の $0$ でない元 $h_0$ がある（整列性を次数に使う）。その最高次の係数で割ったものを $h$ とすると、$h$ も $fK[x]+gK[x]$ に属し、次数は最小である。$p=fu+gv$ を任意の元とし、thm-dea-poly-division で $p=hq+r$ と割ると、$r=p-hq$ も $fK[x]+gK[x]$ に属し、$r\ne0$ なら $\deg r<\deg h$ となって最小性に反する。よって $r=0$、$p\in hK[x]$ である。逆の包含は明らかなので $fK[x]+gK[x]=hK[x]$ である。$f,g$ はこの集合に属するので $h$ で割り切れ、$h=fu_0+gv_0$ と書けるので $f,g$ の公約多項式は $h$ を割り切る。最高次の係数が $1$ で次数最小の元が 2 つ $h,h'$ あれば、$h-h'$ は $0$ か次数がより小さい元なので $h=h'$ である。$\square$

互除法を $n$ を含んだまま実行する。
$$ 21n+4=1\cdot(14n+3)+(7n+1),\qquad 14n+3=2\,(7n+1)+1 $$
なので、lem-dea-gcd-shift により
$$ \gcd(21n+4,\,14n+3)=\gcd(14n+3,\,7n+1)=\gcd(7n+1,\,1)=1 $$
である。逆にたどると $3\,(14n+3)-2\,(21n+4)=1$ であり、これを示すだけでも答になる（公約数は左辺を割り切るので $1$ を割り切る）。$\square$

$Q(m,n):=n^2-mn-m^2$ とおき、条件 $Q(m,n)=\pm1$ を満たす正の整数の組 $(m,n)$ を解と呼ぶ。

• $m=n$ なら $Q=-m^2$ なので $m=n=1$ である。
• $n< m$ なら $Q=n(n-m)-m^2<-m^2\le-1$ となり、解ではない。
• $n>m$ なら、展開して確かめられるように $Q(n-m,\,m)=m^2-m(n-m)-(n-m)^2=-Q(m,n)$ なので、$(n-m,\,m)$ も（正の整数の組で）解であり、成分の和は $n$ に減る。
  したがって $(1,1)$ 以外の解に操作 $(m,n)\mapsto(n-m,\,m)$ を繰り返すと、和が真に減りながら解であり続け、最後は $(1,1)$ に達する。逆向きの操作は $(m,n)\mapsto(n,\,m+n)$ であり、これも $Q$ の符号を変えるだけなので解を解に移す。よって解の全体は $(1,1)$ から逆向きの操作でたどり着ける組、すなわち隣り合う Fibonacci 数の組 $(F_k,F_{k+1})$（$k\ge1$）である。$F_{16}=987$、$F_{17}=1597$、$F_{18}=2584>1981$ であり、$m^3+n^3$ は $k$ について増加するので、最大値は $987^3+1597^3=5034507976$ である。$\square$