ユークリッドの互除法と約数の考察～京大理系後期1989

$a = Ad$，$b = Bd$ とおく。（$A,B$ は互いに素な奇数の整数）

$$\begin{aligned} m &= (11A+B)d\\ n &= (3A+B)d \end{aligned}$$ より $m,n$ は $d$ を公約数に持つ。

$11A+B$ と $3A+B$ の最大公約数を求める。 $$11A+B - (3A+B) = 8A$$

より $$\mathrm{gcd} \ (11A+B,3A+B) = \mathrm{gcd} \ (3A+B,8A)$$ である。よって $11A+B$ と $3A+B$ の最大公約数は $8A$ の約数である。特に $A,B$ は互いに素であるため，$8$ の約数である。

よって，$m,n$ の最大公約数は $8d$ の約数である。

さて，$a,b$ は奇数であるため $m,n$ は偶数である。よって $m,n$ の最大公約数は偶数である。ここで $d$ は奇数であるため，$m,n$ の最大公約数として $d$ は不適である。。

以上より，最大公約数の候補は $2d,4d,8d$ である。

$m,n$ がどちらも平方数であると仮定する。

このとき $m,n$ の最大公約数もまた平方数となる。

1番より最大公約数は $2d,4d,8d$（$d$ は奇数）のいずれかであった。このうち $2d,8d$ は $2$ で奇数回しか割ることができないため，平方数にならない。よって $m,n$ の最大公約数は $4d$ である。

こうして $m,n$ は $4$ で割り切れる平方数となるため，$m = 4M^2$，$n=4N^2$（$M,N$ は整数）とおくことができる。

$m-n = 8a$ に代入すると $$4M^2-4N^2 = 8a$$ 辺々を $4$ で割ることで $$M^2-N^2 = 2a$$ を得る。

今，$M,N$ の偶奇が異なるとすると $M^2-N^2$ は奇数である。一方右辺の $2a$ は偶数であるため矛盾する。ゆえに $M,N$ の偶奇は一致するとしてよい。

• $M,N$ がどちらも偶数の場合
  このとき，$m,n$ の最大公約数は $16$ で割り切れることになる。これは1の結果と矛盾する。

• $M,N$ がどちらも奇数の場合
  $M^2, N^2$ を $4$ で割った余りはどちらも $1$ になる。ゆえに左辺の $M^2-N^2$ は $4$ の倍数である。
  一方，$a$ は奇数であることから，右辺の $2a$ は $4$ で割り切ることができず矛盾する。

こうして $M,N$ の偶奇がどちらの場合も矛盾が生じるため，最初の過程は誤りである。

こうして $M,N$ が両方平方数になることはない。