足跡-sokuseki-

りかの日進月歩の記録

証明を書いていたら循環論法になってしまいましたよという話

簡単なはずの証明問題にやたら時間がかかっていたことの弁明をしたいと思います(弁明にはならない)。

今日の夕方に投稿した記事の証明問題の話です。

「aのn乗がpの倍数であること」と「aがpの倍数であること」は同値である - 足跡-sokuseki-


これの⑵の証明の際に、対偶を帰納法ではなくそのまま証明できないかと奮闘していました。

以下がその証明部分です。

 a^n  p の倍数  \Longrightarrow   a  p の倍数 』を示すために、その対偶である

 a  p の倍数でない \Longrightarrow  a^n  p の倍数でない 』を示すことにします。


 t,qを正の整数として、 a=pt+q とおきます。

ただし、 q  については  0 < q < p とします。

このとき

 a^n = (pt+q)^n

となりますが、ここで二項定理を使います。二項定理は

 (x+y)^n = \sum_{k=0}^{n} {}_n C _{k} x^k y^{n-k}

というものです。これを利用すると

 (pt+q)^n = \sum_{k=0}^{n} {}_n C _{k} (pt)^k q^{n-k} = \sum_{k=1}^{n} {}_n C _{k} p^k t^k q^{n-k} + q^n

となります。ここで、  k>0 のとき   {}_n C _{k} p^k t^k q^{n-k}  p の倍数であり、

 p の倍数を足し合わせたものである  \sum_{k=1}^{n} {}_n C _{k} p^k t^k q^{n-k}

 p の倍数になります。

また、 0 < q < p より、 q  p の倍数ではないので、

 q^n  p の倍数ではありません。

よって、 a^n = (pt+q)^n  p の倍数ではありません。

以上より、対偶を示すことができたので、十分条件が成り立つことがわかりました。

色を変えたところが循環論法になっています。

これをどうしようか……と悩んでいて時間が経ってしまったわけです。

なお、当該記事では帰納法を使っていますが、これは、どうしてもうまくいかなくて、数学の先生に

「『 a  p の倍数でない \Longrightarrow  a^n  p の倍数でない』はどうやって示せばいいですか」

と質問したところ、帰納法を使えばいいよというアドバイスをいただいたので、帰納法でやってみた次第です。

私が自力で思いついたわけではないです。はい。

(帰納法ということを教えてもらっただけで中身の証明は自分で考えたのですが、そのせいで無駄に長い証明になってしまいました……)

なお、さきほど短いver.を追記しました。


以上、弁明にもならない弁解でした。