【証明問題】(a,b)=1 ならば (a+b,a-b,ab)=1

【NT24】(a,b)=1 ⇒ (a+b,a-b,ab)=1 の証明

 整数 $a,\:b$ の最大公約数が $g$ であることを $(a,\:b)=g$ のように表し、$a,\:b,\:c$ の最大公約数が $h$ であることを $(a,\:b,\:c)=h$ と表記します。$(a,\:b)=1$ であるときに、
(1) $(a+b,\:a-b)\leq 2$ を示してください。
(2) $(a+b,\:a-b,\:ab)=1$ を示してください。

【解答の準備】たとえば $(9,\ 4)$ というペアで試してみると
 
\[(9 + 4,\ 9 – 4,\ 9\cdot 4) = (13,\ 5,\ 36)\]
となって確かに最大公約数は $1$ です。$9$ の約数 $3$ と $4$ の約数 $2$ はどちらも $9+4,\ 9-4$ のいずれの約数にもなりえないからです。一見して当たり前の事実ですが丁寧に一般論を証明してみましょう。

【解答】(1) $(a+b,\:a-b)=g$ とおくと、
 
\[a+b=kg,\;a-b=lg\quad (k\gt l)\]
のように表すことができるので、
 
\[2a=(k+l)g,\;2b=(k-l)g\]
となって、$g$ は $2a$ と $2b$ の公約数であることがわかります。したがって
 
\[(2a,\:2b)=2(a,\:b)\]
は $g$ を約数にもつので、$(a,\:b)=1$ より、$2$ が $g$ を約数にもつことになるので、$g\leq 2$ となります 。[証明終]

(2) $a+b,\:a-b,\:ab$ の最大公約数を $h$ とします。すなわち
 
\[(a+b,\:a-b,\:ab)=h\]
とおきます。(1) の結果より、$(a,\:b)=1$ のとき、$h$ は $1$ または $2$ のどちらかです。仮に $h=2$ であるなら、$ab$ が素数 $2$ を約数にもつので、

 ① $a$ が $2$ を約数にもつ ② $b$ が $2$ を約数にもつ

のどちらかであり、両方が成立することはありえません。ここで仮定により $a+b$ も $2$ を約数にもっているので、
 
\[a+b=2k\]
とおいてみます。すると $a$ が $2$ を約数にもつとき $a=2l$ として
 
\[b=2(k-l)\]
のようになりますから $b$ もまた $2$ を約数にもつことになります。同様に $b$ が $2$ を約数にもつならば $a$ も $2$ で割り切れなくてはなりません。これは $(a,\:b)=1$ に矛盾するので、$h=1$ であることがわかります。よって
 
\[(a+b,\:a-b,\:ab)=1\]
となります。[証明終]

【NT-25】a^3+b^3=p^3をみたす素数 p と正整数 a, b は存在しないことの証明

 $a^3+b^3=p^3$ を満たす素数 $p$ と正の整数 $a,\:b$ が存在しないことを示してください。(早大一部改)

【ヒント】実際の入試問題では小問 (1) と (2) がありましたが、(1) が大きなヒントになっていて、あまり難しくない問題だったので、思いきってカットしてみました。

暗号技術のすべて

中古価格
¥3,097から
(2019/8/6 21:56時点)


【解答】とりあえず
 
\[a^3+b^3=p^3 \tag{1}\]
が成り立つと仮定して左辺を因数分解します。
 
\[(a+b)(a^2-ab+b^2)=p^3 \tag{2}\]
 $a+b$ と $a^2-ab+b^2$ の大小関係によって上手く $a,\:b$ を絞り込んでゆくことを考えます。やや突飛な発想に思えるかもしれませんが、整数問題では自身で不等式を設定するという手法が有効な場合があるのです。

[case 1] $a+b \geq a^2-ab+b^2$ の場合

 両辺を見比べると、この不等式が成り立つのはレアケースであると予測できます。これは絞り込みやすいはずだと期待しながら式を $a$ について整理しましょう。
 
\[a^2-(b+1)a+b^2-b \leq 0 \tag{3}\]
 この不等式が成立するためには、判別式によって
 
\[(b+1)^2-4(b^2-b) \geq 0\]
を満たすことが条件となります ($a$ についての 2 次関数グラフが $a$ 軸と交点をもつ条件です)。すなわち
 
\[(b-1)^2 \leq \frac{4}{3}\]
となります。この不等式をみたす $b$ は $b=1,\:2$ だけです。

[case 1-a] $b=1$ のとき (3) より
 
\[a(a-2) \leq 0\]
となって、$a=1,\:2$ だけがこの不等式を満たします。

[case 1-b] $b=2$ のときは
 
\[(a-1)(a-2) \leq 0\]
となり、$a=1,\:2$。

 [case 1-a], [case 1-b] を合わせると
 
\[(a,\:b)=(1,\:1),\quad (1,\:2),\quad (2,\:1),\quad (2,\:2)\]
が候補となりますが、これを (1) に代入すると
 
\[p^3=2,\:9,\:16\]
となって、この式を満たす素数 $p$ は存在しません。

[case 2] $a+b \lt a^2-ab+b^2$ の場合

 $a,\:b$ は正の整数なので $a+b \geq 2$。つまり $a+b$ は 1 ではないので (1) は
 
\[a+b=p,\quad a^2-ab+b^2=p^2\]
という分け方しかありません。右の式を変形すると
 
\[(a+b)^2-3ab=p^2\]
 $a+b=p$ を代入すると $ab=0$ となりますが、これは $a,\:b$ が正の整数であるという条件に反します。

 以上より (1) を満たす $a,\:b,\:p$ は存在しないことが示されました。

コメント

  1. さらさら より:

    gが合成数の場合(a,bが互いに素なら結局はgは1にしかならないが証明途中の話)、gの約数のうちの一つはaの約数で別の一つはbの約数ということもあり得るのでgは素数としておいたほうが良いのではないかとと思ったのですがgがa+bとa-bの公約数でもある時点でgはbの約数で決まりだと思ったり。いずれにしてもbは素数としておいたほうが無難だと思います。

    • Blog Cat より:

       御指摘の通り、当記事の解答は完全に誤りでした。急いで検証したところ、この定理は最初に (a+b,a-b)≦2 を示さなくてはならないようです。問題文・解答ともに明日までに修正します。誠に申し訳ありませんでした。

タイトルとURLをコピーしました